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

Prijeđi na navigaciju Prijeđi na pretraživanje
Dodana 4 bajta ,  prije 13 godina
m
Bot: ispravka HTML koda i wiki sintakse
m (+ref)
m (Bot: ispravka HTML koda i wiki sintakse)
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|lambda računu]] isprepleo sa Turingovim u formalnoj teoriji [[izračunljivost|izračunljivosti]] poznatoj kao [[Church-Turingova hipoteza]]. Hipoteza povezuje strogu formalnu definiciju Turingovog stroja i intuitivne notacije ''efektivne izračunljivosti'', te na taj način pruža preciznu definiciju [[algoritam|algoritma]] ili 'mehaničkog postupka'.
 
== Formalna definicija jednotračnog Turingovog stroja ==
 
Sažeti formalni opis Turingovog stroja:
* <math>F \subseteq Q</math> je skup ''prihvatljivih'' ili ''finalnih'' stanja
 
== Reference ==
 
* [[Taylor L. Booth]] (1967), ''Sequential Machines and Automata Theory'', John Wiley and Sons, Inc., New York.
32.865

uređivanja

Navigacijski izbornik