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 $\varphi$ izračunljivih funkcija (kao što su Turingovi opisni brojevi) i funkciju uparivanja $\langle i,x\rangle$, problem zaustavljanja (također zvan i skup zaustavljanja) je problem odluke za skup

$K_{\varphi }^{0}:=\{\langle i,x\rangle |\varphi _{i}(x)\ \mathrm {postoji} \}$

sa $\varphi _{i}$ kao i-tom izračunljivom funkcijom pod Gödelovim pobrojanjem $\varphi$.

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

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

• $\{i\mid \varphi _{i}(0)\ \mathrm {staje} \}$
• $\{i\mid \exists n(\varphi _{i}(n)\ \mathrm {staje} )\}$