Aniello Murano » 8.Problemi non decidibili e riducibilità - prima parte

Overview

Nelle lezioni precedenti, abbiamo mostrato alcuni problemi decidibili ed altri indecidibili per le macchine di Turing.
Tra quelli indecidibili, abbiamo mostrato A_TM che rappresenta il problema della membership per le macchine di Turing.
In questa lezione mostreremo un metodo fondamentale per provare che l’indecidibilità dei problemi: La riducibilità.
Con questo metodo, proveremo l’indecidibilità dei seguenti problemi per le macchine di Turing:

• il vuoto;
• l’equivalenza;
• la regolarità.

Riduzione

La riduzione è un modo per convertire un problema A in un altro problema B (A si riduce a B) in modo tale che una soluzione per B può essere usata per risolvere A
Quando A (problema noto) è riducibile a B (nuovo problema), risolvere A non può essere più difficile della risoluzione di B perché una soluzione di B da una soluzione anche ad A. (A ≤ B)
In termini della teoria della calcolabilità, se A è riducibile a B e B è decidibile, anche A è decidibile.
In modo equivalente, se A è indecidibile ed è riducibile a B, B è indecidibile.
Quest’ultima versione è la chiave per dimostrare che molti problemi sono indecidibili.
In breve, il metodo che useremo per dimostrare che un problema A è indecidibile sarà quello di mostrare che altri problemi già noti essere indecidibili sono riducibili ad A.
Notare che la riducibilità dice che non conosciamo una soluzione di A o B considerandoli singolarmente, ma sappiamo solo che una soluzione per A si ottiene da una soluzione di B.
La riducibilità gioca un ruolo fondamentale nella classificazione dei problemi attraverso la decidibilità e conseguentemente nella teoria della complessità.

Riduzione di A_TM a HALT_TM

Abbiamo già stabilito l’indecidibilità di A_TM, il problema di determinare se dato un input una Macchina di Turing accetta.
Consideriamo allora un problema simile, HALT_TM, il problema di determinare se su un certo input la Macchina di Turing si ferma (con accept o reject). Per dimostrare l’indecidibilità di HALT_TM possiamo sfruttare l’indecidibilità di A_TM riducendo A_TM a HALT_TM.

La definizione di HALT_TM è la seguente:

HALT_TM = {(M, w) | M è una TM e M si ferma su input w}.

Dimostrazione di indecidibilità per HALT_TM

Dimostriamo quindi che HALT_TM è indecidibile.
Assumiamo che HALT_TM è decidibile e usiamo questa assunzione per dimostrare che A_TM è decidibile, contraddicendo quello che abbiamo detto nella lezione precedente.
L’idea chiave è mostrare che A_TM è riducibile ad HALT_TM.
Supponiamo di avere una TM R che decide HALT_TM.
Usiamo R per costruire S, una TM che decide ATM nel seguente modo:

S prende in input una codifica di una TM M e una stringa w:

1. Facciamo girare la TM R su input (M, w).
2. Se R rifiuta (cioè M va in reject o su w non si ferma), allora S rifiuta (perché (M,w) non è presente nel linguaggio di A_TM).
3. Se R accetta (cioè M su w o accetta o rifiuta), allora si simula M su w finchè non si ferma.
4. Se M accetta, allora R accetta; se M rifiuta, allora R rifiuta.

Chiaramente, se R decide HALT_TM, allora S decide A_TM. Poichè A_TM è indecidibile, allora anche HALT_TM deve essere indecidibile.

Decidere il vuoto per TM è indecidibile

Nel resto di questa lezione mostriamo altre riduzione per provare l’indecidibilità di vari linguaggi.

Consideriamo E_TM = { (M) | M è una TM e L(M) = Φ}.

Mostriamo con la riduzione che E_TM è indecidibile.

Assumiamo per ottenere una contraddizione che E_TM è decidibile e in seguito mostriamo che A_TM è decidibile. Otteniamo cosi una contraddizione.

Decidere il vuoto per TM è indecidibile(segue)

Consideriamo una TM R che decide E_TM. Usiamo R per costruire una TM S che decide A_TM.

Come si comporterà S quando riceve in input (M, w)?

Un’idea per S è quella di far girare R con input (M) e vedere se accetta.
Se accetta, significa che sappiamo che L(M) è vuoto e di conseguenza M non accetta w. Ma se R rifiuta (M), allora sappiamo che L(M) non è vuoto e che M accetta qualche stringa, ma ancora non sappiamo se M accetta una particolare stringa w.
Abbiamo dunque bisogno di un’idea differente.
Invece di far girare R su , facciamo girare R su una modifica di . Modifichiamo M in modo che garantisca che M rifiuta tutte le stringhe tranne w, tenendo presente che anche su input w la macchina lavora sempre allo stesso modo.
A questo punto usiamo R per determinare se la macchina modificata riconosce il linguaggio vuoto.
Ora l’unica stringa che la macchina accetta è w, in questo modo il suo linguaggio sarà non vuoto se e solo se accetta w.
Se R accetta quando riceve in input una descrizione della macchina modificata, allora sappiamo che la macchina modificata non accetta nulla e che M non accetta w.

Dimostrazione

Dimostriamo la correttezza della costruzione fatta nella slide precedente. Chiamiamo M1 la macchina appena costruita, che opera nel modo seguente:

M1= “Su input x:

1. Se x ≠ w, rifiuta.
2. Se x = w, si considera M su input w e accetta se M accetta.

M1 verifica se x = w in modo ovvio: scandisce l’input e lo confronta carattere per carattere con la stringa w per determinare se sono uguali.

Assumiamo che la TM R decide E_TM. Si costruisce allora la TM S che decide A_TM come descritto di seguito:

Dimostrazione (segue)

S=” Su input (M,w), dove M è una codifica di una TM M e w una stringa:

1. Utilizza la descrizione di M e w per costruire la TM M1 appena descritta.
2. Fa girare R su input (M1).
3. Se R accetta, allora rifiuta; Se R rifiuta, allora accetta; “

S deve essere in grado di computare una descrizione di M1 da una descrizione di M e w. Per fare questo basta aggiungere degli stati in più ad M per verificare che x=w.
Se R è un decisore per E_TM, allora S è un decisore per A_TM. Un decisore per A_TM non può esistere, cosi sappiamo che E_TM è indecidibile.

L’Equivalenza di due TM è indecidibile

Usando ragionamenti simili a quelli fatti nelle diapositive precedenti, è possibile dimostrare l’indecidibilità di vari linguaggi.
Per esempio, si consideri il seguente:

EQTM = { (M1,M2) | M1 e M2 sono TM e L(M1)=L(M2)}.

Usando il concetto di riduzione dal problema per E_TM, si dimostra facilmente che EQ_TM è indecidibile.
R decisore per EQ_TM
S decisore per E_TM
S = “su ingresso :

• costruisce M₁ come la MdT t.c. L(M₁) = Ø
• esegui R su ingresso
• se R accetta → S accetta (cioè L(M) = L(M₁) = Ø)altrimenti → rifiuta (L(M) ≠ L(M₁) quindi il linguaggio riconosciuto da M non è vuoto).”

Dato che S non può esistere (E_TM non decidibile) non può esistere neanche R, quindi EQ_TM non è decidibile (dimostrazione per contraddizione).

Regular è indecidibile

Si consideri il seguente linguaggio

REGULAR_TM = {(M)| M è una TM and L(M) è un linguaggio regolare}

Anche in questo caso, usando il concetto di riduzione, si può mostrare che REGULAR_TM è indecidibile.

Assumiamo per ottenere una contraddizione che REGULAR_TM è decidibile e in seguito mostriamo che A_TM è decidibile. Otteniamo cosi una contraddizione.

Per ogni coppia (M,w) costruiamo una MdT M’ che si comporta nel modo seguente su ogni x:

1. Se x è della forma (0ⁿ1ⁿ), allora M’ accetta.
2. altrimenti, simula M su w.
3. Se M accetta w, allora M’ accetta x.
4. Se M rifiuta, allora M’ rifiuta x.

L(M’) = ∑* se M accetta w.

L(M’) = (0ⁿ1ⁿ) se M non accetta w.
Quindi, L(M’) è regolare se e solo se M accetta w.

Esercizi

Provare che i seguenti linguaggi sono indecidibili:

• L={(M) | M è una TM che accetta “000″}
• CONTEXT-FREE_TM = {(M) | M è una TM e L(M) è context-free}
• NOTREGULAR_TM = {(M) | M è una TM e L(M) non è regolare}

Rice’s Theorem

Rice’s Teorem: Ogni proprietà non banale p dei linguaggi RE e’ indecidibile.

Prova: Sia p una proprietà non banale dei linguaggi RE (ovvero una proprietà che non sia sempre vera o sempre falsa). Allora deve esistere un linguaggio RE Lp che abbia la proprietà p. Sia M_L una TM che accetta L.

Ridurremo il linguaggio universale Lu a L_p, dimostrando che L_p è indecidibile, dato che L_u e’ indecidibile.

• Input della riduzione: coppia (M,w).
• Output: una TM M’. M’ e’ tale che L(M’) = ø se M non accetta w, e L(M’) = L se M accetta w.
• M_ simula M su w. Se M non accetta w, M’ non accetta nessuna stringa x in input. Se M accetta w, M’ simula ML su x, percio’ accettera’ esattamente L. Dato che L ha la proprietà p, M’ e’ in L_p.
• Quindi abbiamo costruito una riduzione da L_u a L_p.