Univerzalni Turingov stroj
Univerzalni računarski stroj Alana Turinga (još i "univerzalni stroj", "U stroj", "U") je ime koje je dao (1936. – 1937.) svom modelu "a-stroja" (od engl. all-purpose) opće namjene koji bi mogao "izvoditi" bilo koji proizvoljni (ali dobro oblikovan) slijed instrukcija nazvanih "petorke". Neki, kao što je Davis (2000.), ovaj model smatraju pretečom "računala pohranjenog programa" koji je John von Neumann koristio 1946. za svoj "elektronički računarski instrument" koji sad nosi njegovo ime: von Neumannova arhitektura.
 |
Ovaj članak ili dio članka nije pokriven izvorima. Pomozite Wikipediji navođenjem odgovarajućih knjiga, članaka u časopisima ili internetskih stranica. |
Ovaj se stroj kao model računanja sad zove univerzalni Turingov stroj.
Univerzalni Turingov stroj i univerzalni jezik. uredi
Univerzalni TS Mu može simulirati rad bilo kojeg TS M s jednom trakom. Univerzalni TS ima 3 trake. Na prvu traku zapisane su funkcije prijelaza TS M i ulazni niz w, <M,w>, na treću se zapisuje stanje TS, dok sadržaj druge trake simulira sadržaj trake proizvoljnog TS M – druga je traka za rad. Univerzalni TS Mu prepiše niz w s prve trake na drugu, simulira rad TS M primjenom prijelaza zapisanih na prvoj traci i zapisuje stanje TS M na treću traku. Ako za stanje zapisano na trećoj traci i za znak na drugoj nema daljnjih prijelaza na prvoj, TS će stati s radom. Ako je stanje na trećoj traci prihvatljivo, onda univerzalni TS Mu prelazi u prihvatljivo stanje.
Univerzalni TS Mu prihvaća niz <M,w> akko TS M prihvaća niz w. Ne stane li nikad TS M za niz w, onda nikad ne stane ni TS Mu za dani niz. Zaustavi li se TS M bez da prihvati niz w, TS Mu stane i ne prihvaća niz <M,w>.
Univerzalni TS Mu prihvaća univerzalni jezik Lu koji se definira na sljedeći način: Lu={<M,w> | TS M prihvaća niz w}, gdje je <M,w> kodirani zapis TS M i niza w. Jezik Lu naziva se univerzalnim jer je pitanje: „Da li TS M prihvaća niz w?“ jednako pitanju: „Da li je niz <M,w> u jeziku Lu</sub>?“.
Kako je za univerzalni jezik Lu moguće izgraditi TS Mu, jezik Lu jest rekurzivno prebrojiv, odnosno izračunljiv.
Univerzalni jezik Lu nije rekurzivan, odnosno nije odlučiv. Svojstvo neodlučivosti Lu pokazuje se na temelju svojstva dijagonalnog jezika Ld i njegovog komplementa Ldc. Ld nije rekurzivno prebrojiv => Ldc sigurno nije rekurzivan.