Mašina koja uvek staje

U teoriji izračunljivosti, mašina koja uvek staje ili odlučivač ili totalna Tjuringova mašina je Tjuringova mašina koja staje za svaki ulaz.

Kako uvek staje, mašina je u stanju da odluči da li data niska pripada formalnom jeziku. Klasa jezika koji mogu da budu odlučeni ovakvim mašinama tačno odgovara skupu rekurzivnih jezika. Međutim, usled halting problema, određivanje da li proizvoljna Tjuringova mašina staje za proizvoljni ulaz je sa svoje strane neodlučiv problem odlučivanja.

Funkcije izračunljive totalnim Tjuringovim mašinama

U praksi su mnoge interesantne funkcije izračunljive na mašinama koje uvek staju. Mašina koja koristi samo konačnu memoriju za svaki pojedinačni ulaz može biti primorana da stane za svaki ulaz ograničavanjem njenih mogućnosti za kontrolu toka tako da nijedan ulaz ne može da natera mašinu da uđe u beskonačnu petlju. Kao trivijalan primer, mašina koja implementira konačno stablo odlučivanja će se uvek zaustaviti.

Ne zahteva se da mašina bude u potpunosti lišena mogućnosti za iteriranje kroz petlje kako bi se garantovalo zaustavljanje. Ako se petlje ograniče na predvidivu konačnu veličinu, one mogu da izraze sve primitivno rekurzivne funkcije .

Moguće je čak definisati programski jezik koji će osigurati da i sofisticiranije funkcije staju. Na primer, Akermanova funkcija, koja nije primitivno rekurzivna, ali je ipak totalno izračunljiva funkcija.

Odnos sa parcijalnim Tjuringovim mašinama

Opšta Tjuringova mašina će izračunati parcijalnu funkciju. Moguće je postaviti dva pitanja o odnosu između parcijalne i totalne Tjuringove mašine:

1. Da li svaka parcijalna funkcija koja je izračunljiva na parcijalnoj Tjuringovoj mašini proširiva (to jest da li joj je moguće proširiti domen) tako da postane totalna izračunljiva funkcija?
2. Da li je moguće promeniti definiciju Tjuringove mašine tako da je moguće naći određenu klasu totalnih Tjuringovih mašina, takvih da mogu da izračunaju sve totalno izračunljive funkcije?

Odgovor na oba ova pitanja je negativan.

Sledeća teorema pokazuje da funkcije izračunljive na mašinama koje uvek staju ne uključuju proširenja svih parcijalno izračunljivih funkcija, što povlači da je odgovor na prvo pitanje negativan. Ova činjenica je u bliskoj vezi sa algoritamskom nerešivošću halting problema.

Teorema. Postoje Tjuring izračunljive parcijalne funkcije koje nemaju proširenje do totalno Tjuring izračunljivih funkcija. Preciznije, parcijalna funkcija f definisana tako da f(n) = m ako i samo ako Tjuringova mašina sa indeksom n staje na ulazu 0 sa izlazom m nema proširenje do totalno izračunljive funkcije.

Ova teorema se dokazuje svođenjem na kontradikciju. Ako bi g bila totalno izračunljiva funkcija koja proširuje f onda bi g bila izračunljiva na nekoj Tjuringovoj mašini; neka je e indeks takve mašine. Ako bi bila napravljena Tjuringova mašina M, korišćenjem Klinijeve teoreme rekurzije, koja za ulaz 0 simulira mašinu sa indeksom e koja radi sa indeksom n_M za M (stoga mašina M može da proizvede svoj indeks; ovo je uloga teoreme rekurzije). Po pretpostavci, ova simulacija bi u nekom trenutku dala odgovor. Ako se definiše M tako da ako g(n_M) = m onda je povratna vrednost mašine M jednaka m + 1. Stoga f(n_M), prava povratna vrednost mašine M za ulaz 0, neće biti jednaka g(n_M). Ovo protivreči pretpostavci da g proširuje f.

Drugo pitanje je u suštini pitanje da li postoji drugi razuman model izračunavanja koji izračunava samo totalne funkcije i izračunava sve totalno izračunljive funkcije. Neformalno, ako bi takav model postojao, svaki od njegovih računara bi bilo moguće simulirati na Tjuringovoj mašini. Stoga ako bi se ovaj novi model računanja sastojao od niza $M_{1},M_{2},\ldots$ mašina, postojalo bi rekurzivno prebrojiv niz $T_{1},\ldots T_{2},\ldots$ Tjuringovih mašina koje računaju totalne funkcije tako da je svaka totalno izračunljiva funkcija izračunljiva jednom od mašina T_i. Ovo je nemoguće, jer bi mašina $T$ mogla da bude konstruisana tako da za ulaz i mašina T vraća $T_{i}(i)+1\,$. Ova mašina ne može da bude ekvivalentna nijednoj mašini T iz liste: Neka je ta mašina u listi na indeksu j. Onda $T_{j}(j)=T_{j}(j)+1\,$, što ne vraća celobrojni rezultat. Stoga ne može da bude totalna, ali funkcija po konstrukciji mora da bude totalna (ako su totalne funkcije rekurzivno prebrojive, onda ova funkcija može da bude konstruisana), i tu se javlja kontradikcija. Ovo pokazuje da i drugo pitanje ima negativan odgovor.

Skup indekasa totalnih Tjuringovih mašina

Problem odlučivanja da li će Tjuringova mašina sa indeksom e stati za svaki ulaz nije odlučiv. Ovaj problem je na nivou $\Pi _{2}^{0}$ aritmetičke hijerarhije. Stoga je ovaj problem strogo teži od halting problema, koji postavlja pitanje da li će mašina sa indeksom e stati za ulaz 0. Intuitivno, ova razlika u neizračunljivosti je posledica činjenice da svaka instanca problema totalne mašine predstavlja beskonačno mnogo instanci halting problema.

Vidi još

• Totalno funkcionalno programiranje

Literatura

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.
• Ohlebusch, E. (2002), Advanced Topics in Term Rewriting, Springer.