Turingov stroj: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
slika |
Nema sažetka uređivanja |
||
Redak 1:
'''Turingovi strojevi''' su iznimno jednostavni apstraktni uređaji za manipulaciju znakovima (simbolima) koji - unatoč jednostavnosti dizajna - mogu biti prilagođeni da simuliraju logiku
▲'''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
== Formalna definicija jednotračnog Turingovog stroja ==
| |||