Razlika između inačica stranice »Turingov stroj«

Obrisana 3 bajta ,  prije 8 godina
bez sažetka
m (r2.6.4) (robot Dodaje: sq:Makina Turing)
'''Turingovi strojevi''' su iznimno jednostavni apstraktni uređaji za manipulaciju znakovima (simbolima) koji - unatoč jednostavnosti dizajna - mogu biti prilagođeni da simuliraju logiku bilo kojeg računalnog algoritma (uz sadašnje poimanje algoritma). Opisao ih je 1936. [[Alan Turing]]. Turingovi strojevi ne koriste se u praktične svrhe, već u misaonim eksperimentima, gdje najvažniju primjenu nalaze u istraživanju granica mogućnosti izračunavanja računalnim algoritmima. Proučavanje njihovih svojstava pruža dalekosežne uvide u pitanja [[računarskaračunalna znanost|računarskeračunalne znanosti]] i [[teorija složenosti|teorije složenosti]].
 
Turingov stroj koji može simulirati bilo koji drugi Turingov stroj se zove [[Univerzalni Turingov stroj]] ('''UTS''' ili jednostavno '''univerzalni stroj'''). Više matematički orijentiranu definiciju sa sličnom "univerzalnom" prirodom je uveo [[Alonzo Church]], čiji se rad na [[lambda račun]]u isprepleo sa Turingovim u formalnoj teoriji [[izračunljivost]]i poznatoj kao [[Church-Turingova hipoteza]]. Hipoteza povezuje strogu formalnu definiciju Turingovog stroja i intuitivne ideje izračunljivosti, te na taj način pruža preciznu definiciju [[algoritam|algoritma]] ili 'mehaničkog postupka'.
:"Turingov stroj je [[konačni automat]] povezan sa vanjskim medijem za pohranu ili memoriranje" (Minsky (1967) p. 117)
 
:"Turingov stroj je esencijalno konačni sekvencijalni stroj koji ima mogućnost komuniciranja sas vanjskim spremištem informacija" (Booth (1967), p. 354)
 
[[Konačni automat]] je predstavljen tablicom stanja i svojim registrom stanja. "Vanjski medij za pohranu" jest traka. Ulaz stroja je pročitani znak sa trake. Izlaz stroja jest znak koji se piše na traku ili naredba za brisanje znaka te naredba za pomicanje trake ulijevo ili udesno.
Anonimni suradnik