2
W jakim stopniu algorytm może przewidzieć złożoność czasową dowolnego programu wejściowego?
Powstrzymanie problemu twierdzi, że niemożliwe jest napisanie programu, który może określić, czy kolejne przystanków programowych dla wszystkich możliwych programów wejściowych . Mogę jednak z pewnością napisać program, który może obliczyć czas działania programu takiego jak: for(i=0; i<N; i++) { x = 1; } i zwróć czasową złożoność , bez uruchamiania …