Aniello Murano » 4.Macchine di Turing multinastro

Definizione delle TM multinastro

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 δ(q_i,a₁,…, a_k)=(q_j,b₁,…, b_k,L,R,…,L) sta a significare che se la macchina è nello stato q_i e le testine da 1 a k stanno leggendo i simboli a₁ … a_k, la macchina va nello stato q_j, scrive i simboli b₁ … b_k, 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.

Equivalenza tra TM multinastro e TM a singolo nastro

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.

Formalizzazione

Di seguito è descritto il funzionamento della TM S vista nella precedente diapositiva:

S=” Su input w=w₁…w_n: $\# \dot w_1 w_2 ...w_n \#\dot \sqcup#\dot \sqcup\# ... \#$

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.

Teorema

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.

Trasduttori multinastro

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:

Sul primo nastro (nastro di input) è memorizzata la stringa 1ⁿ#1^m, dove le due sequenze non vuote di 1 rappresentano i numeri da moltiplicare in notazione unaria.
Quando la macchina si ferma, sul secondo nastro (nastro di output) verrà memorizzata la stringa 1^nm.