Utente:Banus/MdT
Da Wikipedia, l'enciclopedia libera.
Consideriamo la macchina di Turing che riconosce il carattere 1 (insieme ricorsivo). Se incontra una casella vuota (blank) termina immediatamente. Una macchina di Turing è data dai seguenti elementi:
- L'insieme degli stati S è dato da {s0, s1, s2}.
- Lo stato iniziale s_0 è s0.
- L'insieme degli stati finali è F = {s1, s2}.
- L'alfabeto è questo: A = {0, 1, b}.
- Il segno di casella vuota è b: β = b.
Consideriamo ora la funzione di tranizione di stato:
Dove s stato di partenza, a carattere in ingresso, b carattere scritto, t stato di arrivo, m avanzamento della testina (-1, 0, 1).
La funzione è:
Ed è totale. La macchina termina sempre in uno stato finale dopo la lettura del primo input, in stato s2 se il carattere letto è 1, altrimenti in stato s1.
