Problem zaustavljanja

Izvor: Wikipedija
Skoči na: orijentacija, traži

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 [1] za pripisivanje problema zaustavljanja Turingu.)

Formalni iskaz[uredi VE | uredi]

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 sa 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})\}

Fusnote[uredi VE | uredi]

  1. 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 Si" (str. 70).
    Davis ne pripisuje nikakve zasluge za ovaj dokaz, tako da čovjek zaključuje da je 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)