Varianti delle MdT

Esistono molte definizioni alternative (varianti) di Macchina di Turing

Tra queste vedremo:

• MdT a più nastri
• MdT non deterministiche

Tutte le varianti “ragionevoli” della definizione originale hanno la stessa capacità computazionale: riconoscono la stessa classe di linguaggi

Stayer

Definizione originale: la funzione di transizione $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ obbliga la testina a spostarsi a destra o a sinistra ad ogni passo

Variante “stayer”: permettiamo alla testina anche la possibilità di restare ferma sulla stessa cella del nastro durante una transizione

La funzione di transizione diventa: $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, S, R\}$ dove $S$ indica che la testina rimane ferma

Potere computazionale di stayer

In generale: diciamo che il potere computazionale di due modelli di calcolo è lo stesso se essi riconoscono la stessa classe di linguaggi

Possiamo provare che la versione originale della MdT, che obbliga ad ogni passo la testina a spostarsi, ha lo stesso potere computazionale di stayer

Ovviamente stayer può facilmente simulare una MdT convenzionale: basta non usare la possibilità di restare sulla stessa cella del nastro

Simuliamo stayer con una MdT convenzionale

Sia $M$ una MdT stayer

Mostriamo che esiste una MdT convenzionale $M'$ che simula $M$, cioè riconosce lo stesso linguaggio

Definiamo $M'$ come $M$, modificando solo la funzione di transizione

Ogni transizione $\delta (q, a) = (q',a', S)$ può essere simulata da due transizioni in $M'$:

1. $\delta_{M'} (q,a) = (\hat{q}, a', R)$: scrive il simbolo $a'$, muove la testina a destra e va nello stato aggiuntivo $\hat{q}$