Stroj koji uvijek staje: razlika između inačica

Problem odluke zaustavlja li se Turingov stroj sa indeksom ''e'' za svaki ulaz nije odlučiv. Ustvari, ovaj je problem na razini <math>\Pi^0_2</math> u aritmetičkoj hijerarhiji. Stoga je ovaj problem nešto teži od problema zaustavljanja, koji pita zaustavlja li se stroj sa indeksom ''e'' za ulaz ''0''. Intuitivno ova razlika u nerješivosti postoji pošto svaka instanca problema "totalnog stroja" predstavlja beskonačno mnogo instanci problema zaustavljanja.

 

 

* Brainerd, W.S., Landweber, L.H. (1974), ''Theory of Computation'', Wiley.