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>:
- esegui R su ingresso <M, w>
- se R rifiuta → rifiuta (M non termina sull'ingresso w)
- se R accetta (M non va in loop) simula M su ingresso w
- 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>:
- se x ≠ w → rifiuta
- se x = w → esegui M su w e accetta se M accetta."
È ora possibile definire S:
S = "su ingresso <M, w>:
- costruisci M1
- esegui R su ingresso <M1>
- se R accetta → rifiuta (L(M) = 0 → M 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>:
- costruisci M1 come la MdT t.c. L(M1) = 0
- esegui R su ingresso <M, M1>
- 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>
- simula M su w fino a che M termina o fino a che ha effettuato qngn passi
- 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>
- costruisci LBA B da M e w
- esegui R su ingresso <B>
- 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