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 uredi

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 s dobro uređenim argumentima (Ohlebusch, 2002, pp.67).

Odnosi s parcijalnim Turingovim strojevima uredi

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 izmijeniti 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 s 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 s indeksom n koji staje na ulazu 0 s 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 s indeksom e pokrenut na indeksu nM 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(nM) = m tada povratna vrijednost stroja M iznosi m + 1. Stoga f(nM), stvarna povratna vrijednost stroja M za ulaz 0 nije jednaka g(nM), što je u kontradikciji s 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  , tada bi postojao rekurzivno prebrojiv slijed Turingovih strojeva   koji izračunavaju svaku totalnu funkciju na način da je svaka totalno izračunljiva funkcija izračunljiva od strane nekog od strojeva Ti. Ovo je nemoguće, pošto bi mogao biti konstruiran stroj   takav da za ulaz i stroj vraća  . Tada bi T bio totalni stroj, pošto je svaki od strojeva Ti 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 uredi

Problem odluke zaustavlja li se Turingov stroj s indeksom e za svaki ulaz nije odlučiv. Ustvari, ovaj je problem na razini   u aritmetičkoj hijerarhiji. Stoga je ovaj problem nešto teži od problema zaustavljanja, koji pita zaustavlja li se stroj s 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 uredi

  • 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.
Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.