Problem zaustavljanja

U teoriji izračunljivosti, problem zaustavljanja je problem odluke koji se neformalno može iskazati na sljedeći način:

Za dani opis programa i konačnog ulaza, odluči završuje li program ili se izvršuje unedogled, za dani ulaz.

Alan Turing je 1936. dokazao da općenit algoritam za rješavanje problema zaustavljanja za sve moguće parove programa-ulaza ne može postojati. Kaže se da je problem zaustavljanja neodlučiv nad Turingovim strojevima. (vidi za pripisivanje problema zaustavljanja Turingu.)

Formalni iskaz

Problem odluke je skup prirodnih brojeva - "problem" je odlučiti je li istaknuti broj element skupa.

Za dano Gödelovo pobrojavanje [math]\displaystyle{ \varphi }[/math] izračunljivih funkcija (kao što su Turingovi opisni brojevi) i funkciju uparivanja [math]\displaystyle{ \langle i, x \rangle }[/math], problem zaustavljanja (također zvan i skup zaustavljanja) je problem odluke za skup

[math]\displaystyle{ K_{\varphi}^{0} := \{ \langle i, x \rangle | \varphi_i(x) \ \mathrm{postoji} \} }[/math]

sa [math]\displaystyle{ \varphi_i }[/math] kao i-tom izračunljivom funkcijom pod Gödelovim pobrojanjem [math]\displaystyle{ \varphi }[/math].

Iako je skup K rekurzivno prebrojiv, problem zaustavljanja nije rješiv izračunljivom funkcijom.

Postoji mnogo istovjetnih formulacija problema zaustavljanja - bilo koji skup sa Turingovim stupnjem istim kao onim problema zaustavljanja se može shvatiti kao takva formulacija. Primjeri takvih skupova uključuju:

• [math]\displaystyle{ \{ i \mid \varphi_i(0) \ \mathrm{staje} \} }[/math]
• [math]\displaystyle{ \{ i \mid \exists n ( \varphi_i(n) \ \mathrm{staje})\} }[/math]