cerca
Informatica Teorica - RiducibilitÓ
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Informatica Teorica - RiducibilitÓ

Torna alla pagina di Informatica Teorica


:: Informatica Teorica - RiducibilitÓ ::

Appunti del 28 Aprile

RiducibilitÓ

La riducibilitÓ Ŕ un metodo per convertire l'istanza di un problema A in un'istanza di un problema B e utilizzare la soluzione di quest'ultimo per ottenere la soluzione di A. La riducibilitÓ Ŕ anche uno dei metodi principali per dimostrare che un problema non Ŕ computazionalmente decidibile.

Quando A Ŕ riducibile a B allora:

  • risolvere A non pu˛ essere pi¨ difficile di risolvere B
  • risolvere B ci permette di ottenere la soluzione di A
  • se B Ŕ decidibile allora lo Ŕ anche A
  • se A non Ŕ decidibile allora anche B non Ŕ decidibile

Non decidibilitÓ di HALTTM

Tramite riducibilitÓ Ŕ possibile dimostrare che il problema HALTTM, ovvero il problema della terminazione di una macchina di turing su un dato ingresso, non Ŕ decidibile:

HALTTM = {<M, w> | M Ŕ una MdT e M termina sull'ingresso w}

Supponiamo che esista una MdT R che decide il nostro problema e proviamo a descrivere la MdT S che decide ATM riducendo il problema di accettazione al nostro problema di terminazione HALTTM:

S = "su ingresso <M, w>:

  1. esegui R su ingresso <M, w>
  2. se R rifiuta → rifiuta (M non termina sull'ingresso w)
  3. se R accetta (M non va in loop) simula M su ingresso w
  4. se M accetta → accetta
    altrimenti → rifiuta

Abbiamo dimostrato che se esistesse R allora saremmo in grado di costruire anche S, ma sappiamo che il problema ATM non Ŕ decidibile e che quindi S non pu˛ esistere, quindi non esiste nemmeno R (dimostrazione per contraddizione).

Non decidibilitÓ di ETM

Il problema ETM consiste nello stabilire se il linguaggio di un automa Ŕ vuoto. Questo problema non Ŕ decidibile e lo si pu˛ dimostrare sempre tramite riducibilitÓ:

ETM = {<M> | M Ŕ una MdT e L(M) = 0}

Come nella precedente dimostrazione riduciamo ATM a ETM:

  • R decisore per ETM
  • S decisore per ATM

Per la dimostrazione Ŕ necessario definire M1 come la MdT che rifiuta tutte le stringhe diverse da w e nel caso l'ingresso sia proprio w allora esegue M sull'ingresso:

M1 = "su ingresso <x>:

  1. se x ≠ w → rifiuta
  2. se x = w → esegui M su w e accetta se M accetta."

╚ ora possibile definire S:

S = "su ingresso <M, w>:

  1. costruisci M1
  2. esegui R su ingresso <M1>
  3. se R accetta → rifiuta (L(M) = 0M non riconosce nessuna stringa e quindi neanche w)
    altrimenti → accetta (L(M1) non vuoto quindi M riconosce w)."

Dato che S non pu˛ esistere (ATM non decidibile) non pu˛ esistere neanche R, quindi ETM non Ŕ decidibile (dimostrazione per contraddizione).

Non decidibilitÓ di EQTM

Il problema EQTM consiste nello stabilire se due macchine di Turing riconoscono lo stesso linguaggio. Questo problema non Ŕ decidibile e lo si pu˛ dimostrare utilizzando la riducibilitÓ di ETM a EQTM:

EQTM = {<M1, M2> | M1 e M2 MdT t.c. L(M1) = L(M2)}

Per ottenere S riduciamo il problema di decidere se un linguaggio Ŕ vuoto (ETM) al problema di dire se una MdT riconosce lo stesso linguaggio (EQTM) di una MdT il cui linguaggio Ŕ vuoto:

Riduciamo ETM a EQTM:

  • R decisore per EQTM
  • S decisore per ETM

S = "su ingresso <M>:

  1. costruisci M1 come la MdT t.c. L(M1) = 0
  2. esegui R su ingresso <M, M1>
  3. se R accetta → accetta (L(M) = L(M1) = 0)
    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).

Computation Histories (CH)

Una CH di una MdT non Ŕ altro che la sequenza di configurazioni che la macchina attraversa per elaborare un ingresso. Ogni CH Ŕ una sequenza finita di configurazioni, in quanto se la macchina di Turing non termina su un ingresso allora non esiste una CH per quel dato ingresso.

Formalmente si pu˛ definire una CH in questo modo:

Sia M una MdT e w un ingresso per M. Una CH accettante per M su w Ŕ una sequenza di configurazioni C1, C2, ..., Cl dove:

  • C1 Ŕ la configurazione di partenza di M su w
  • Cl Ŕ una configurazione accettante
  • ogni Ci segue Ci-1 secondo le regole di M

Una CH non accettante Ŕ simile ad una CH accettante tranne che Cl Ŕ una configurazione non accettante.

Le MdT deterministiche possiedono una sola CH per un dato input, mentre le MdT non deterministiche ne possiedono molte, in corrispondenza ai possibili rami della computazione.

Linear Bounded Automa (LBA)

Un LBA Ŕ una MdT limitata in memoria in cui la testina non pu˛ muoversi oltre il limite destro e sinistro della stringa di input. Lo spazio di memoria utilizzabile Ŕ quindi ristretto alla lunghezza della stringa di input.

Per incrementare la memoria disponibile Ŕ possibile per˛ aumentare l'insieme dei simboli dell'alfabeto rendendolo pi¨ ampio rispetto all'insieme dei simboli dell'alfabeto di ingresso. In questo modo si incrementa la memoria di un fattore costante, quindi la quantitÓ di memoria disponibile Ŕ lineare rispetto alla dimensione dell'input.

╚ possibile dimostrare che un LBA possiede un numero limitato di configurazioni:

Sia M un LBA con:

  • q stati
  • g simboli di ingresso
  • un nastro lungo n

Il numero di configurazioni distinte possibili Ŕ qngn.

DecidibilitÓ di ALBA

Grazie a questa proprietÓ degli LBA Ŕ possibile dimostrare che il problema dell'accettazione di una stringa per un LBA Ŕ decidibile:

ALBA = {<M, w> | M Ŕ un LBA che accetta w}

Costruiamo il decisore L che decide ALBA: L = su ingresso <M, w>

  1. simula M su w fino a che M termina o fino a che ha effettuato qngn passi
  2. se M termina e accetta → accetta
    altrimenti → rifiuta (M non ha accettato o Ŕ finito in loop)

La simulazione di M su w si ferma anche quando si ricade in una configurazione giÓ vista in precedenza: questa situazione indica la presenza di un loop infinito. La simulazione inoltre pu˛ fare al massimo qngn passi: se si arriva ad aver visitato qngn configurazioni distinte, il prossimo passo ci porterÓ in una configurazione sicuramente giÓ vista (perchÚ le configurazioni sono in numero limitato) e quindi in un loop.

Non decidibilitÓ di ELBA

Mentre Ŕ decidibile ALBA, non Ŕ invece decidibile ELBA, ovvero il problema che consiste nel dire se un LBA non accetta alcuna stringa. ╚ possibile dimostrarlo tramite riduzione:

ELBA = {<M> | M Ŕ un LBA e L(M)=0}

Supponiamo che il decisore per ELBA esista e proviamo a ridurre un problema noto a ELBA:
riduciamo ATM a ELBA:

  • R decisore per ELBA
  • S decisore per ATM

Per effettuare la riduzione definiamo l'LBA B tale che L(B)={CH accettanti per una data MdT M e un dato ingresso w}. L'ingresso per B Ŕ una sequenza di configurazioni e per verificare che la sequenza sia una CH accettante devono essere verificate le condizioni giÓ descritte in precedenza.

Se L(B) = 0 vuol dire che non esistono CH che consentono a M di accettare w e quindi ATM dovrÓ rifiutare. Viceversa se il linguaggio di B non Ŕ vuoto allora M accetta w.

Costruiamo il decisore S che decide ATM: S = su ingresso <M, w>

  1. costruisci LBA B da M e w
  2. esegui R su ingresso <B>
  3. se R accetta → rifiuta (L(B) vuoto → M non accetta w)
    altrimenti → accetta

Quindi se esistesse un decisore per ELBA potremmo ottenere un decisore per ATM. Sappiamo per˛ che non Ŕ possibile decidere ATM e quindi non esiste un decisore per ELBA.


Torna alla pagina di Informatica Teorica