Macchina di Turing

Una Macchina di Turing è una macchina a stati finiti con un nastro infinito (memoria illimitata)

Il nastro è diviso in celle (caselle) ognuna delle quali può contenere simboli

Ha una testina che consente di leggere e scrivere simboli ed è in grado di muoversi liberamente sul nastro

Esistono solo due stati che fanno terminare la computazione: accept e reject

Quando la Macchina di Turing raggiunge uno di essi, la computazione si ferma immediatamente

Se non raggiunge uno stato di accettazione o rifiuto, la MdT andrà avanti per sempre, senza mai fermarsi

All’inizio il nastro contiene solo la stringa input, tutto il resto è vuoto, cioè riempito con il simbolo blank $\sqcup$

Inizialmente la testina si trova sulla prima cella del nastro, cioè all’inizio della stringa input

Il simbolo $\sqcup$ segna la fine della stringa input

Ad ogni passo, la testina legge il simbolo puntato, lo lascia inalterato o lo sovrascrive con un altro simbolo, e poi si sposta a destra o a sinistra

Definizione formale

Una Macchina di Turing è una settupla: $(Q, \sum, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

• insieme stati $Q$
• alfabeto di lavoro $\sum$ ($\sqcup \notin \sum$)
• $\Gamma$ alfabeto del nastro ($\sqcup \in \Gamma$, $\sum \subset \Gamma$)
• $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L,R\}$ funzione di transizione
• $q_0$ stato iniziale
• $q_{accept}$ stato accept
• $q_{reject}$ stato reject