Macchina di Turing

Note

Una macchina di Turing (MT) è un modello di calcolo basato su gli automi a pila, ma con $k$ nastri di memoria. Per convenzione storica e semplicità di formalizzazione, i nastri sono sequenza infinite di celle di cui:

• Solo una quantità finita è inizializzata con un valore sensato
• Le celle restanti contengono uno spazio vuoto o il valore blank $\text{blank}$

Tutte le testine possono scorrere su nastri o rimanere ferme

La transizione di un MT avviene in funzione di:

• Lettura del carattere sotto la testina del nastro di input
• Lettura dei caratteri sotto le testine dei nastri di memoria
• Stato dell’organo di controllo

E può effettuare come azioni:

• Cambiare lo stato dell’organo di controllo
• Scrivere un carattere su ogni nastro di memoria
• Scrivere un carattere sul nastro di output
• Spostare le testine di memoria e ingresso: una posizione a sinistra $L$, destra $R$ o ferme $S$
• Spostare la testina di output: una posizione a $S$ e $R$, se si sposta si scrive sempre una lettera o un $\text{blank}$.

Per convenzione si etichettano gli archi con formato:

$$⟨i,(A_1,\cdots ,A_k)/w,(A_1^{\prime },\cdots ,A_k^{\prime }),(m_{\text{in}},m_1,\cdots ,m_k,m_{k+1})⟩$$

Con $m_{\text{in}}\in \{\text{L},\text{S},\text{R}\}$ mossa della testina di input, $m_{1\cdots k}\in \{\text{L},\text{S},\text{R}\}$ mosse delle memorie e $m_{k+1}\in \{\text{S},\text{R}\}$ mossa della testina di output. Inoltre consideriamo la pila inizializzata con $Z_0$ per marcare il fondo.

MT riconoscitore

Note

La funzione di transizione di una MT riconoscitore è definita come:

\delta: Q\times(I\cup\set{\blank})\times \Gamma^{k}\to Q\times \Gamma^{k}\times \set{\text{L},\text{S},\text{R}}^{k+1}

Esempio riconoscitore di $L=\{a^n{b}^n{c}^n\mid n>0\}$

MT traduttore

Note

La funzione di traduzione di una MT traduttore è definita come:

\eta: Q\times (I\cup \set{\blank})\times \Gamma^{k}\to (O\cup\set{\blank})\times\set{\text{S},\text{R}}

Configurazione e transizione di una MT

Note

Di base, tutti i nastri di memoria sono pieni di $\text{blank}$, tranne nella posizione iniziale della rispettiva testina, dove c’è $Z_0$. Si ha inoltre come stato iniziale dell’organo di controllo $q_0$, e la strina di ingresso $x$ è scritta a partire della $0^a$ cella del nastro di ingresso, seguita e preceduta da $\text{blank}$. Mentre il nastro di uscita è riempito con $\text{blank}$.

Come per gli FSA e gli AP, gli stati di accettazione sono $F\subseteq Q$. Per convenzione, la $\delta$ e $\eta$ non sono definite a partire dagli stati finali:

$$\forall q\in F\delta (q,\cdots )=\perp \eta (q,\cdots )=\perp$$

Una stringa $x$ in ingresso è accettata se e solo se in un numero finito di transizioni, la macchina si ferma in $q\in F$.

Proprietà di una MT

Note

Si ha che una MT è chiusa a $\cup$, $\cap$, $.$, $\ast$, ma non al complemento.

Modelli equivalenti

Note

È possibile costruire modelli di calcolo equivalenti alla MT, tra cui:

• Una MT con nastro bidimensionale
• Una MT con $k$ testine per nastro
• Un AP con due pile

Se un modello di calcolo può simulare una MT viene detto Turing completo. Una MT è in grado di simulare il comportamento di una macchina di Von Neumann. La differenza principale tra loro è la modalità di accesso alla memoria.

MT a nastro singolo

Una particolare variante della MT è quella a nastro singolo, dove input, output e memoria sono tutti nello stesso nastro. È in grado di emulare una MT a $k$ nastri.