Utente:Banus/MdT

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:

$T=\langle S,s_{0},F,A,\beta ,\delta \rangle \quad {\mbox{dove}}$

• 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:

$\delta (s,a)=\langle b,t,m\rangle$

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 è:

$\delta (s0,b)=\langle b,s1,1\rangle$
$\delta (s0,0)=\langle 0,s1,1\rangle$
$\delta (s0,1)=\langle 1,s2,1\rangle$
$\delta (s1,-)=\langle -,s1,0\rangle$
$\delta (s2,-)=\langle -,s2,0\rangle$

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.