Una macchina di Turing multinastro è paragonabile ad un ordinaria Macchina di Turing a singolo nastro ma con più nastri.
Ogni nastro ha la sua testina per leggere e scrivere.
Inizialmente l’input risiede sul I° nastro e gli altri sono inizializzati con caratteri di blank.
La funzione di transizione cambia per permettere di leggere,scrivere e muovere le testine su alcuni o tutti i nastri simultaneamente. Formalmente è descritta in questo modo:
δ : Q\{accept,reject} · Γk → Q · Σk · {L,R,S}k dove k è il numero di nastri;
L’espressione δ(qi,a1,…, ak)=(qj,b1,…, bk,L,R,…,L) sta a significare che se la macchina è nello stato qi e le testine da 1 a k stanno leggendo i simboli a1 … ak, la macchina va nello stato qj, scrive i simboli b1 … bk, e direziona ogni testina per muoversi a sinistra o destra, o rimanere ferma, in base a quanto specificato dalla relazione di transizione.
Sebbene le Macchine di Turing multinastro sembrano essere più potenti delle classiche TM, possiamo facilmente dimostrare che sono equivalenti.
Ricordiamo che due Macchine di Turing sono equivalenti se riconoscono lo stesso linguaggio.
TEOREMA
Per ogni Macchina di Turing multinastro esiste una macchina di Turing a singolo nastro equivalente.
DIMOSTRAZIONE
Mostriamo come convertire una TM multinastro M in una TM S a singolo nastro. L’idea chiave è quella di mostrare come simulare M con S.
Assumiamo che M abbia k nastri. Allora S simula l’effetto dei k nastri di M memorizzando il loro contenuto sul suo unico nastro. S utilizza il simbolo # come delimitatore per separare i contenuti dei diversi nastri. Inoltre, S deve tener traccia delle posizioni delle varie testine. Per fare questo, per ogni simbolo nella posizione di una testina dei k nastri, S scrive lo stesso simbolo con l’aggiunta di un punto sopra. Questo nuovo simbolo sarà poi aggiunto all’alfabeto del nastro di S. Per maggiore chiarezza a lato è rappresentata una TM a 3 nastri e la sua corrispondente riduzione in una una TM a singolo nastro.
Di seguito è descritto il funzionamento della TM S vista nella precedente diapositiva:
S=” Su input w=w1…wn:
Di seguito è descritto il funzionamento della TM S vista nella precedente diapositiva:
1. S in prima istanza copia il contenuto dei k nastri della TM M sul suo nastro:
2. Per simulare un singolo movimento, S scandisce il nastro dal primo simbolo # il quale indica il limite sinistro, fino al (k+1)-esimo #, il quale indica il limite destro, per individuare il simbolo che rappresenta la testina virtuale. Come secondo passo S aggiorna i nastri, in base a come è definita la funzione di transizione di M.
3. Se in qualche punto S muove una delle testine virtuali a destra di un simbolo #, questa azione indica che M ha mosso la testina corrispondente in una porzione del nastro dov’è presente un simbolo di blank. Cosi S scrive un simbolo blank su questa cella del nastro e trasla di un unità i contenuti del nastro, da questa cella fino al simbolo # più a destra. La simulazione continua poi ciclicamente.
COROLLARIO:
Un linguaggio è Turing-Riconoscibile se e solo se esiste almeno una macchina di Turing Multinastro che lo riconosce.
DIMOSTRAZIONE:
->:
Un linguaggio Turing riconoscibile è riconosciuto da una normale Macchina di Turing (a singolo nastro), la quale è un caso particolare di una Macchina di Turing multinastro.
<-:
Questo si dimostra attraverso il teorema visto nella precedente diapositiva.
Si ricordi che una MdT che calcola una funzione (anche parziale) può essere vista come un Trasduttore.
Questo è ancora più evidente nel caso di una macchine di Turing a più nastri, dove un nastro può essere usato per l’input, uno per l’output ed eventualmente altri nastri possono essere usati per l’esecuzione della macchina
Esercizio: Definire una macchina trasduttrice a due nastri che calcoli la funzione prodotto di due interi positivi in notazione unaria, seconde le seguenti convenzioni:
4. Macchine di Turing multinastro
5. Macchine di Turing non-deterministiche
6. Macchina di Turing universale e problema della fermata
7. Problemi decidibili e non decidibili
8. Problemi non decidibili e riducibilità - prima parte
9. Problemi non decidibili e riducibilità - seconda parte
11. Decidibilità delle teorie logiche
12. Misurazione della Complessità e introduzione alla classe P
14. NP-Completezza - prima parte
15. NP-Completezza - seconda parte
16. Altri problemi NP-Completi
17. Esercitazione su problemi NP-Completi
18. Space Complexity
19. Savitch Theorem