Tjuringove mašine su slične konačnim automatima/mašinama sa konačnim stanjem, ali imaju prednost neograničene memorije … Sposobni su da simuliraju uobičajene računare; problem koji običan kompjuter može riješiti (s obzirom na dovoljno memorije) također će biti rješiv pomoću Turingove mašine, i obrnuto.
Koja je razlika između RAM-a i TM-a?
A Turingova mašina ne može RAM mašina može izvršiti aritmetiku u O(1) (pod određenim ograničenjima). Turingova mašina ne može. Turingove mašine polinomski simuliraju RAM mašine, to jest, za neku konstantu c, bilo koja RAM mašina koja radi u vremenu O(nk) može biti simulirana Turingovom mašinom koja radi u vremenu O(nck).
Da li je traka Turingove mašine neograničena?
Tjuringova mašina (TM) je državna mašina koja se sastoji od dve memorije: neograničene trake i kontrolne tablice konačnog stanja. Traka drži podatke kao simbole. Mašina ima vrlo mali skup ispravnih operacija, ukupno 6 (čitanje, pisanje, pomicanje lijevo, pomicanje desno, promjena stanja, zaustavljanje) na traci.
Zašto je Turingova mašina moćna?
Koliko su moćne Turingove mašine? Turingove mašine mogu prihvatiti bilo koji običan jezik ili jezik bez konteksta. Tjuringove mašine mogu izvoditi osnovna aritmetička izračunavanja … Turingova teza kaže da svako računanje koje se može izvesti „mehaničkim sredstvima” može da izvede Turing mašina (zanemarujući probleme efikasnosti).
Mogu li Turingove mašine vječno vrtiti petlju?
turing(turingDescrip) ne može se zauvek zaustaviti niti petlja; nema smisla u svakom slučaju.
