Teorema 3.16

Posted by On Filed under Calcolabilità e linguaggi formali

(in nero la traduzione del Sipser; in blu gli elementi aggiunti da me)

Ogni macchina di Turing nondeterministica ha una macchina di Turing deterministica equivalente.

Idea

Possiamo simulare ogni macchina nondeterministica N con una macchina deterministica D. L'idea sottostante la simulazione è che D provi ogni possibile ramo della computazione nondeterministica di N. Se D trova uno stato accettato in uno dei rami, D accetta, altrimenti la simulazione di D non termina.

Vediamo la computazione di N di un input w come un albero. Ogni ramo di questo ramo rappresenta uno dei rami del nondeterminismo. Ogni nodo del ramo è una configurazione di N. La radice dell'albero è la configurazione di partenza. La TM D cerca in questo albero qualche configurazione accettata. Condurre questa ricerca con attenzione è cruciale, altrimenti si rischia che D non riesca a visitare l'intero albero. Una tentazione - sbagliata - sarebbe quella di fare una ricerca usando l'algoritmo depth-first. Il depth-fist va a fondo di ogni ramo prima di tornare a esplorarne un altro. Se D esplora l'albero in questa maniera, D potrebbe proseguire per sempre giù per uno dei rami e mancare una configurazione accettabile in uno degli altri rami. Così disegnamo D per splorare l'albero usando la ricerca breadth-first. Questa strategia esplora tutti i rami alla stessa profondità prima di proseguire a esplorare un ramo alla profondità successiva. Questo metodo garantisce che D visiterà ogni nodo nell'albero finché non incontrerà una configurazione accettata.

Prova

Simuliamo una macchina deterministica D con tre nastri. Per il teorema 3.13 questa impostazione è equivalente a una a nastro singolo. La macchina D usa i suoi tre nastri in un modo particolare, come illustrato nella seguente figura. Il nastro 1 contiene sempre la stringa di input e non è mai modificato. Il nastro 2 mantiene una copia del nastro di N in ogni ramo della computazione nondeterministica. Il nastro 3 mantiene traccia della locazione di D nell'albero computazionale nondeterministico di N.

Figura 3.17: La TM deterministica D simula la TM nondeterministica N

Consideriamo per prima cosa i dati rappresentati nel nastro 3. Ogni nodo nell'albero può avere al massimo b figli, dove b è la dimensione dell'insieme più largo di scelte date dalla funzione di transizione di N. Per ogni nodo nell'albero assegnamo un indirizzo che è una stringa nell'alfabeto Σb = {1, 2, ..., b}. Assegnamo l'indirizzo 231 al nodo a cui arriviamo iniziando dalla radice, andando dentro il suo secondo figlio, poi dentro il terzo, poi dentro il primo. Ogni simbolo nella stringa ci dice quale schelta fare al prissimo passaggio, quando simuliamo un passo nin un ramo della computazione nondeterministica di N. A volte un simbolo puà non corrispondere a nessuna scelta se sono disponibili troppo poche scelte nella configurazione. In questo caso l'indirizzo non è valido e non corrisponde a nessun nodo. Il nastro 3 contiene una stringa in Σb. Rappresenta il ramo della computazione di N dalla radice al nodo indirizzato da questa stringa, a meno che l'indirizzo non sia non valido. La stringa vuota è l'indirizzo della radice dell'albero. Ora siamo pronti a descrivede D.

  1. Inizialmente il nastro 1 contiene l'input w e i nastri 2 e 3 sono vuoti.
  2. Copia il nastro 1 nel nastro 2
  3. Usa il nastro 2 per simulare N on l'input w di uno dei rami della computazione nondeterministica. Prima di ogni passo di N consulta il prossimo simbolo nel nastro 3 per determinare quale scelta fare tra quelle permesse dalla funzione di transizione di N. Se non restano più simboli nel nastro 3 o se la scelta nondeterministica non è valida, annullare questo ramo andando al passo 4. Andare al passo 4 anche se si incontra una configurazione rifiutata. Se si trova una configurazione accettata, considerare l'input accettato.
  4. Rimpiazzare la stringa nel nastro 3 con la prossima stringa lessicografica. Simulare il prossimo ramo della computazione di N andando al passo 2.

La simulazione di una TM nondeterministica è estremamente macchinosa e inefficiente (ma le TM non richiedono di essere efficienti), perché consiste in:

  1. calcolare il numero massimo di branch possibili, che nel libro è rappresentato dalla variabile b.
  2. Eseguire i vari passaggi seguendo l'ordine lessicograficamente. Questo significa che se b = 4 l'ordine che seguirò sarà 1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44, 111...
  3. Per ciascuno dei passaggi, copiare il nastro "matrice" nel nastro di "simulazione" ed eseguire DI NUOVO tutto il ramo partendo da zero fino ad arrivare al successivo livello.

Mi sembra di essere Bill Murray nel giorno della Marmotta:

Questa immagine, per motivi di Copyright, non è presente nel libro di Sipser

Corollaio 3.18

Un linguaggio è Turing-riconoscibile sse qualche macchina di Turing nondeterministica lo riconosce.

Prova

Ogni TM deterministica è automaticamente una TM nondeterministica, e così una delle due direzioni segue immediatamente. L'altra direzione segue dal teorema 3.16.

Corollario 3.19

Un linguaggio è decidibile sse una macchina di Turing nondeterministica lo decide.

Prova

La direzione "se" è provata dal fatto che se un linguaggio è decidibile, allora una macchina di Turing deterministica lo decide, e siccome una TM deterministica è equivalente in potenza a una TM nondeterministica (3.16) allora se un linguaggio è decidibile, esiste una macchina di Turing nondeterministica che lo decide.

La direzione "solo se" significa che se una macchina di Turing nondeterministica decide un linguaggio, allora è decidibile.

Rispetto alla TM deterministica costruita per 3.16, per una TM decidibile dobbiamo aggiungere un nuovo passo che dice che se nessuno dei rami si conclude con un'accettazione, avremo uno stato reject.

Discutiamo se questa nuova macchina D2 è un decisore per L. Se N accetta gli input, D2 tutti i rami si fermano e fanno un reject, perché è un decisore. Quindi ogni ramo ha una quantità finita di nodi, dove ogni nodo rappresenta on passaggio della computazione di N lungo il ramo.

Perciò l'intero albero di computazione di N nel suo input è finito, in virtù del teorema sugli alberi dato nel corpo dell'esercizio. Conseguentemente, D si fermerà e farà un reject quantdo questo intero albero sarà stato esplorato.