Stroj koji uvijek staje

U teoriji izračunljivosti, stroj koji uvijek staje — poznat i kao odlučitelj (Sipser, 1996) ili totalni Turingov stroj (Kozen, 1997) — je Turingov stroj koji staje za svaki ulaz.

Budući da uvijek staje, stroj može odlučiti pripada li dani niz znakova formalnom jeziku. Klasa jezika koje takvi strojevi mogu odlučiti je točno klasa rekurzivnih jezika. Međutim, važno je uočiti da je zbog problema zaustavljanja određivanje totalnosti proizvoljnog Turingovog stroja neodlučiv problem odluke.

Funkcije izračunljive totalnim Turingovim strojevima

U praksi je većina zanimljivih funkcija izračunljiva strojevima koji uvijek staju. Stroj može biti prisiljen stati za svaki ulaz ograničavanjem njegovih sposobnosti kontrole toka izvršavanja na način da ga nijedan program ne može natjerati da uđe u beskonačnu petlju. Kao trivijalan primjer, navedimo da će stroj koji implementira konačno decizijsko stablo uvijek stati.

Ne zahtijeva se potpuna odsutnost sposobnosti izvršavanja petlji u stroju da bi se zaustavljanje moglo garantirati. Ako ograničimo petlje na predvidljivo konačnu duljinu (ne npr. poput FOR petlje u BASIC-u), možemo izračunati sve primitivno rekurzivne funkcije (Meyer i Ritchie, 1967). Primjer takvog stroja je omogućen u programskom jeziku stvorenom za mentalnu tjelovježbu PL-{GOTO} Brainerda i Landwebera (1974).

Nadalje, možemo definirati programski jezik u kojem se možemo pobrinuti da i složenije funkcije uvijek stanu. Na primjer, Ackermannova funkcija, koja nije primitivno rekurzivna, je svejedno totalno izračunljiva funkcija izračunljiva koristeći tzv. sustav prepisivanja terma sa dobro uređenim argumentima (Ohlebusch, 2002, pp.67).

Odnosi sa parcijalnim Turingovim strojevima

Općenito Turingov stroj izračunava neku parcijalnu funkciju. Dva se krucijalna pitanja mogu postaviti o odnosu parcijalnih Turingovih strojeva i totalnih Turingovih strojeva:

1. Može li se domena svake funkcije izračunljive na parcijalnom Turingovom stroju proširiti tako da postane totalno izračunljiva funkcija?
2. Može li se definicija Turingovog stroja izmjeniti tako da se može pronaći istaknuta klasa Turingovih strojeva koja izračunava sve totalno izračunljive funkcije?

Odgovor na oba pitanja je negativan.

Sljedeći teorem pokazuje da funkcije izračunljive strojem koji uvijek staje ne uključuju proširenja svih parcijalno izračunljivih funkcija, što u konačnici implicira negativan odgovor na prvo pitanje. Ova činjenica je usko povezana sa algoritamskom nerješivošću problema zaustavljanja.

Teorem. Postoje parcijalne Turing-izračunljive funkcije koje nemaju proširenje na totalne Turing-izračunljive funkcije. Posebice, parcijalna funkcija f definirana tako da f(n) = m ako i samo ako Turingov stroj sa indeksom n koji staje na ulazu 0 sa izlazom m nema proširenja na totalno izračunljivu funkciju.

Dokaz slijedi kontradikcijom iz pretpostavke. Ako bi g bila totalno izračunljiva funkcija koja proširuje f, tada bi g bila izračunljiva nekim Turingovim strojem; fiksirajmo tad e kao indeks takvog stroja. Izgradimo Turingov stroj M, koristeći Kleeneov rekurzijski teorem, koji za ulaz 0 simulira stroj sa indeksom e pokrenut na indeksu n_M za M (stoga stroj M može proizvesti sam svoj indeks; ovo je svrha rekurzijskog teorema). Po pretpostavci, ova simulacija će s vremenom dati odgovor. Definirajmo M tako da ako g(n_M) = m tada povratna vrijednost stroja M iznosi m + 1. Stoga f(n_M), stvarna povratna vrijednost stroja M za ulaz 0 nije jednaka g(n_M), što je u kontradikciji sa pretpostavkom da g proširuje f.

Srž drugog pitanja jest postoji li drugi razuman model izračunljivosti koji izračunava samo totalne funkcije i izračunava sve totalno izračunljive funkcije. Neformalno, kad bi takav model postojao, tada bi svaki od njegovih izračuna mogao biti simuliran Turingovim strojem. Stoga, kad bi se taj novi model izračunljivosti sastojao od slijeda strojeva [math]\displaystyle{ M_1,M_2,\ldots }[/math], tada bi postojao rekurzivno prebrojiv slijed Turingovih strojeva [math]\displaystyle{ T_1,\ldots T_2,\ldots }[/math] koji izračunavaju svaku totalnu funkciju na način da je svaka totalno izračunljiva funkcija izračunljiva od strane nekog od strojeva T_i. Ovo je nemoguće, pošto bi mogao biti konstruiran stroj [math]\displaystyle{ T }[/math] takav da za ulaz i stroj vraća [math]\displaystyle{ T_i(i)+1\, }[/math]. Tada bi T bio totalni stroj, pošto je svaki od strojeva T_i totalan, i funkcija koju T izračunava se ne smije pojaviti u listi. Ovo pokazuje da je odgovor i na drugo pitanje također negativan.

Skup indeksa totalnih Turingovih strojeva

Problem odluke zaustavlja li se Turingov stroj sa indeksom e za svaki ulaz nije odlučiv. Ustvari, ovaj je problem na razini [math]\displaystyle{ \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.

Izvori

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.
• Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.
• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
• Kozen, D.C. (1997), Automata and Computability, Springer.
• Ohlebusch, E. (2002), Advanced Topics in Term Rewriting, Springer.