Vidi kôd stranice Problem zaustavljanja

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

:''Za dani opis [[računalni program|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čivost|neodlučiv]]'' nad [[Turingov stroj|Turingovim strojevima]]. (vidi<ref>U nijednom od svojih radova Turing nije koristio riječ "zaustavljanje" ili "terminacija". Turingov biograf Hodges nema riječ "zaustavljanje" ili riječi "problem zaustavljanja" u svom indeksu. Najranija poznata uporaba riječi "problem zaustavljanja" jest u dokazu Davisa (str. 70-71, Davis 1958).

:: "Teorem 2.2 ''Postoji Turingov stroj čiji je problem zaustavljanja rekurzivno nerješiv''.
: "Srodni je problem ''problem ispisivanja'' za jednostavni Turingov stroj Z s obzirom na simbol S<sub>i</sub>" (str. 70).
Davis ne pripisuje nikakve zasluge za ovaj dokaz, tako da čovjek zaključuje da se radi o izvorniku. Ali Davis naglašava da iskaz dokaza neformalno postoji u Kleene (1952.) na stranici 382. Copeland (2004.) veli da:

: "Problem je zaustavljanja tako imenovan (i kako se čini, po prvi put iskazan) od strane Martina Davisa [usp. Copeland fusnota 61]... (Često se kaže da je Turing iskazao i dokazao teorem o zaustavljanju u 'On Computable Numbers', ali ovo nije strogo istnito)." (str. 40)</ref> 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>\varphi</math> [[izračunljiva funkcija|izračunljivih funkcija]] (kao što su Turingovi [[opisni broj]]evi) i [[funkcija uparivanja|funkciju uparivanja]] <math>\langle i, x \rangle</math>, '''problem zaustavljanja''' (također zvan i '''skup zaustavljanja''') je problem odluke za skup 	
:<math>K_{\varphi}^{0} := \{ \langle i, x \rangle | \varphi_i(x) \ \mathrm{postoji} \}</math>
sa <math>\varphi_i</math> kao ''i''-tom izračunljivom funkcijom pod Gödelovim pobrojanjem <math>\varphi</math>.

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

Postoji mnogo istovjetnih formulacija problema zaustavljanja - bilo koji skup s [[Turingov stupanj|Turingovim stupnjem]] istim kao onim problema zaustavljanja se može shvatiti kao takva formulacija. Primjeri takvih skupova uključuju:
*<math>\{ i \mid \varphi_i(0) \ \mathrm{staje} \}</math>
*<math>\{ i \mid \exists n ( \varphi_i(n) \ \mathrm{staje})\}</math>

== Fusnote ==

{{izvori}}
[[Kategorija:Teorija računanja]]