Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 ATM 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 ATM a HALTTM

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

La definizione di HALTTM è la seguente:

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

Dimostrazione di indecidibilità per HALTTM

Dimostriamo quindi che HALTTM è indecidibile.
Assumiamo che HALTTM è decidibile e usiamo questa assunzione per dimostrare che ATM è decidibile, contraddicendo quello che abbiamo detto nella lezione precedente.
L’idea chiave è mostrare che ATM è riducibile ad HALTTM.
Supponiamo di avere una TM R che decide HALTTM.
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 ATM).
  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 HALTTM, allora S decide ATM. Poichè ATM è indecidibile, allora anche HALTTM 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 ETM = { (M) | M è una TM e L(M) = Φ}.

Mostriamo con la riduzione che ETM è indecidibile.

Assumiamo per ottenere una contraddizione che ETM è decidibile e in seguito mostriamo che ATM è decidibile. Otteniamo cosi una contraddizione.

Decidere il vuoto per TM è indecidibile(segue)

Consideriamo una TM R che decide ETM. Usiamo R per costruire una TM S che decide ATM.

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 ETM. Si costruisce allora la TM S che decide ATM 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 ETM, allora S è un decisore per ATM. Un decisore per ATM non può esistere, cosi sappiamo che ETM è 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 ETM, si dimostra facilmente che EQTM è indecidibile.
R decisore per EQTM
S decisore per ETM
S = “su ingresso :

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

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

Regular è indecidibile

Si consideri il seguente linguaggio

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

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

Assumiamo per ottenere una contraddizione che REGULARTM è decidibile e in seguito mostriamo che ATM è 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 (0n1n), 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’) = (0n1n) 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-FREETM = {(M) | M è una TM e L(M) è context-free}
  • NOTREGULARTM = {(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 ML una TM che accetta L.

Ridurremo il linguaggio universale Lu a Lp, dimostrando che Lp è indecidibile, dato che Lu 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 Lp.
  • Quindi abbiamo costruito una riduzione da Lu a Lp.
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion