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

Obrisana 24 bajta ,  prije 11 godina
bez sažetka
(slika)
'''Turingovi strojevi''' su iznimno jednostavni apstraktni uređaji za manipulaciju znakovima (simbolima) koji - unatoč jednostavnosti dizajna - mogu biti prilagođeni da simuliraju logiku iza bilo kojeg [[računalo|računala]]računalnog kojealgoritma ikad(uz možesadašnje bitipoimanje konstruiranoalgoritma). Opisao ih je 1936. [[Alan Turing]]. Premda je izvorna namjera bila tehnička ostvarivostizvedba, Turingovi strojevi nisune namijenjenikoriste kaose praktičnau računskapraktične tehnologijasvrhe, već kaou misaonimisaonim eksperimenteksperimentima, ogdje granicamanajvažniju mehaničkihprimjenu izračuna,nalaze teu stogaistraživanju igranica nisumogućnosti stvarnoizračunavanja iračunalnim konstruiranialgoritmima. Proučavanje njihovih apstraktnih svojstava pruža uviddalekosežne uvide u teoretskopitanja [[računarstvo]]rečunarska znanost|računarske znanosti i [[teorija složenosti|teorijuteorije složenosti]].
[[Slika:US-bombe.jpg|thumb|'''Turingov stroj''']]
'''Turingovi strojevi''' su iznimno jednostavni uređaji za manipulaciju znakovima (simbolima) koji - unatoč jednostavnosti dizajna - mogu biti prilagođeni da simuliraju logiku iza bilo kojeg [[računalo|računala]] koje ikad može biti konstruirano. Opisao ih je 1936. [[Alan Turing]]. Premda je izvorna namjera bila tehnička ostvarivost, Turingovi strojevi nisu namijenjeni kao praktična računska tehnologija, već kao misaoni eksperiment o granicama mehaničkih izračuna, te stoga i nisu stvarno i konstruirani. Proučavanje njihovih apstraktnih svojstava pruža uvid u teoretsko [[računarstvo]] i [[teorija složenosti|teoriju 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 notacije ''efektivneideje izračunljivosti'', te na taj način pruža preciznu definiciju [[algoritam|algoritma]] ili 'mehaničkog postupka'.
 
== Formalna definicija jednotračnog Turingovog stroja ==
6

uređivanja