8. Riducibilità Pt. 1

In questo articolo introduciamo un altro metodo per dimostrare che un problema non è computazionalmente irrisolvibile, un metodo che comunemente viene chiamato riducibilità. Alla base vi è la riduzione, mediante la quale un problema viene convertito in un altro problema, in modo tale che una soluzione al secondo può essere usata per risolvere il primo. Quindi la riducibilità coinvolge sempre due problemi che comunemente vengono denominati A e B. Se A si riduce a B, possiamo utilizzare una soluzione di B per risolvere A. Una proprietà della riducibilità è che essa non dice niente sulla soluzione dei problemi A o B in maniera individuale, ma soltanto sulla risolubilità del problema A quando abbiamo una soluzione anche per B.

La riducibilità svolge un ruolo importante nella classificazione dei problemi in base alla decidibilità e alla teoria della complessità. Quando A è riducibile a B, trovare la soluzione di A non può essere più difficile di risolvere B perchè una soluzione per B offre una soluzione ad A. Secondo la teoria della computabilità, se A è riducibile a B e B è decidibile, allora anche A è decidibile. Vale anche il caso in cui A è indecidibile e riducibile a B, in questo caso anche B risulta indecidibile. Quindi per dimostrare che un problema è indecidibile, bisognerà dimostrare che qualche altro problema già noto per essere indecidibile si riduce ad esso.

Un esempio di problema è quello relativo all' $HALT_{TM}$, il quale consiste nel determinare se una macchina di Turing si ferma su un dato input. Questo problema prende il nome di problema della fermata. Per dimostrare l'indecidibilità del problema della fermata riducendo $A_{TM}$ a $HALT_{TM}$. Sia quindi $HALT_{TM}= \{ < M, w > |$ M è una TM e M si ferma su input w }.

Teorema HALT indecidibile

$HALT_{TM}$ è indecidibile.

Per dimostrare questo teorema, assumiamo al fine di ottenere una contraddizione che la TM R decide $HALT_{TM}$ Costruiamo la TM S per decidere $HALT_{TM}$. Costruiamo la TM S per decidere $A_{TM}$, che opera come segue. S = " < M, w >, una codifica di una TM M ed una stringa w:

• Esegue la TM R su input < M, w >
• Se R rifiuta, rifiuta
• Se R accetta, simula M su w finchè non si ferma
• Se M ha accettato, accetta; se M ha rifiutato, rifiuta

Quindi se R decide $HALT_{TM}$, allora S decide $A_{TM}$ Poichè $A_{TM}$ è indecidibile, allora anche $HALT_{TM}$ deve essere indecidibile. Questo metodo per dimostrare se un problema è indecidibile, viene utilizzato per molti altri problemi affini al teorema precedente. Prendiamo ad esempio questa TM: $E_{TM} =$ { < M > | M è una TM e L(M) = $\emptyset$ } e definiamo il seguente teorema:

Teorma $E_{TM}$ indecidibile

$E_{TM}$ è indecidibile.

Per dimostrare questo teorema denominiamo per convenzione la macchina del teorema $M_1$ e definiamola come segue: $M_1$ = "Su input x:

• Se $x \ne w$ rifiuta
• Se x = w, esegue M su input w e accetta se M accetta"

Questa macchina ha la stringa w come parte della sua descrizione, Essa verifica se x = w scansionando l'input e confrontandolo carattere per carattere. Assumiamo che la TM R decide $A_{TM}$ nel seguente modo: S = " Su input < M, w > una codifica di una TM M e una stringa w:

• Usa la descrizione di M e w per costruire la TM $M_1$ descritta sopra
• Esegue R su input < $M_1$>
• Se R accetta, rifiuta; se R rifiuta, accetta"

S deve essere effettivamente in grado di calcolare una descrizione di $M_1$ da una descrizione di M e w. Può farlo perchè ha bisogno solo di aggiungere ad M alcuni stati in più che svolgono il test x = w. Se R fosse stato un decisore per $E_{TM}$, S sarebbe un decisore per $A_{TM}$. Un decisore per $A_{TM}$ non può esistere, quindi sappiamo che $E_{TM}$ deve essere indecidibile

Il metodo mediante storie di computazione è una tecnica per dimostrare che $A_{TM}$ è riducibile a certi linguaggi. Questo metodo è spesso utile quando il problema da mostrare indecidibile comporta la dimostrazione dell'esistenza di qualcosa. Diamo una definizione formale di storia di computazione.

Definizione di storia di computazione accettante

Sia M una macchina di Turing e w una stringa di input, definiamo una storia di computazione accettante per M su w è una sequenza di configurazioni $C_1, C_2, \dots, C_l$ dove $C_1$ è la configurazione iniziale di M su w, $C_l$ è una configurazione di accettazione per M, e ogni $C_i$ segue da $C_{i-1}$ in accordo alle regole di M. Una storia di computazione di rifiuto per M su w è definita in modo analogo, tranne per il fatto che $C_l$ è una configurazione di rifiuto.

Le storie di computazione sono sequenze finite. Se M non si ferma su w, non esiste una storia di computazione accettante o di rifiuto per M su w. Le macchine deterministiche hanno al massimo una storia di computazione su ogni input. Le macchine non deterministiche possono avere molte storie di computazione su un singolo input, corrispondenti ai diversi rami di computazione. Diamo ora una definizione di automa linearmente limitato e dimostriamo se esso è decidibile.

Definizione di automa linearmente limitato

Un automa linearmente limitato è un tipo ristretto di macchina di Turing in cui alla testina del nastro non è permesso di spostarsi fuori dalla parte del nastro che contiene l'input. Se la macchina tenta di spostare la testina al di fuori dell'input, la testina rimane dove si trova.

Un automa linearmente limitato è una macchina di Turing con una quantità limitata di memoria, la quale può risolvere solo problemi che richiedono una quantità di memoria al più pari alla dimensione dell'input. L'uso di un alfabeto di nastro più grande dell'alfabeto degli input consente alla memoria disponibile di essere aumentata di un fattore costante. Nonostante questo vincolo sulla memoria, un automa LBA risulta abbastanza potente.

Il problema che ci poniamo si riferisce al determinare se un LBA accetta il suo input. Questo problema coincide con quello relativo all'indecidibilità di $A_{TM}$, quando quest'ultima è un LBA, possiamo quindi dimostrare che $A_{LBA}$ è decidibile. Denotiamo quindi: $A_{LBA}$ = {<M,w> | M è un LBA che accetta la stringa w }. Denotando con q il numero degli stati e con g il numero dei simboli nell'alfabeto di nastro, esistono esattamente $qng^n$ configurazioni distinte di M per un nastro di lunghezza n. Quindi enunciamo il teorema della decidibilità per $A_{LBA}$ e diamone una dimostrazione.

Teorema dedicibilità di $A_{LBA}$

$A_{LBA}$ è dedicibile

Per dimostrare questo teorema ricordiamo che una configurazione di M è come un'istantanea durante il suo calcolo. La configurazione comprende lo stato del controllo, la posizione della testina e il contenuto del nastro. M ha q stati e il suo nastro è lungo n, per cui la testina può essere in una delle n posizioni, e $g^n$ possibili stringhe di simboli del nastro compaiono su esso. Il prodotto di questi valori rappresenta il numero totale di configurazioni differenti di M con un nastro di lunghezza n. L'algoritmo che decide $A_{LBA}$ computa in questo modo. L = "Su input < M, w >, dove M è un LBA e w è una stringa:

• Simula M su w poer $qng^n$ passi o finchè non si ferma
• Se M si è fermata, accetta se ha accettato e rifiuta se ha rifiutato. Inoltre se non si è fermata, rifiuta."

Se M su w non si è fermata entro $qng^n$ passi, deve ripetere una configurazione, quindi entra in un ciclo e allora rifiuta. Non tutti i problemi che coinvolgono gli LBA sono dedicibili, esistono alcuni che in realtà non lo sono, ad esempio il problema del vuoto che enuncia come segue $E_{LBA}$ = { < M > | M è un LBA dove L(M) = $\emptyset$}.