Torna alla pagina di Informatica Teorica
:: Informatica Teorica - Decidibilità ::
Appunti & Dimostrazioni del 21 Aprile
Teorema 1 - ADFA è decidibile
Sia dato il problema di verificare se un automa a stati finiti deterministico accetta una stringa. Più formalmente:
ADFA = {<B,w> | B è un DFA che accetta la stringa in ingresso w}
Si dimostri il seguente teorema:
ADFA è un linguaggio decidibile.
Dimostrazione
Dobbiamo trovare una MdT deterministica che lo risolva:
M = "su ingresso <B,w>:
- simula B su w;
- se la simulazione finisce in uno stato finale, allora ACCETTA; altrimenti RIFIUTA."
Anche se abbiamo già dimostrato il teorema, diamo qualche altro dettaglio implementativo. Anzitutto B non è altro che la quintupla che definisce un DFA, e quindi Q, Σ, δ, q0, F. Quindi M come prima cosa verificherà che B sia effettivamente un DFA (altrimenti RIFIUTA subito), quindi simulerà la stringa w direttamente su di lui. Come? Scrivendo ad ogni passo sul nastro lo stato e la posizione corrente di B sull'ingresso w, che sarà inizialmente q0 e dovrà rispettare ad ogni step la funzione di transizione δ. Quando M arriverà a processare l'ultimo simbolo di w, dovrà verificare se è arrivato in uno degli stati finali accettati dal DFA, e accettare o rifiutare la stringa d'ingresso di conseguenza.
Teorema 2 - ANFA è decidibile
ANFA è un linguaggio decidibile.
Dimostrazione
Quello che cambia rispetto al Teorema 1 è che ora abbiamo a che fare con un automa non deterministico. Poco male, sapendo che ogni NFA ha un DFA corrispondente, definiamo la MdT non deterministica che lo risolve:
N = "su ingresso <B,w>:
- converti NFA B in DFA C;
- esegui M sull'ingresso <C,w>;
- se M accetta, allora ACCETTA; altrimenti RIFIUTA."
Teorema 3 - EDFA è decidibile
Il problema Emptiness verifica se un automa a stati finiti non accetta alcuna stringa, ovvero:
EDFA = {<A> | A è un DFA e L(A)=0}
Si dimostri ora il seguente teorema:
EDFA è un linguaggio decidibile.
Dimostrazione
Verificare che un DFA non accetti nessuna stringa significa dimostrare che il suo linguaggio è vuoto, ovvero che nessuna stringa gli appartiene. Viceversa, si ricorda che un DFA accetta una stringa se e solo se è possibile raggiungere uno stato finale utilizzando le sue funzioni di transizione.
Diventa dunque facile definire una MdT deterministica T che risolva EDFA:
T = "su ingresso <A>: (dove A è un DFA)
1. marca lo stato iniziale di A;
2. ripeti finché non trovi nuovi stati marcati:
3. marca un nuovo stato con transizione proveniente da uno stato già marcato
4. se lo stato finale è marcato allora RIFIUTA; altrimenti ACCETTA."
Il punto (4) è ovvio: se si avesse uno stato finale marcato significherebbe che una stringa è accettata dal DFA in ingresso, e quindi T deve rifiutare.
Teorema 4 - EQDFA è decidibile
Il problema Equivalence verifica se due automi a stati finiti riconoscono lo stesso linguaggio, ovvero:
EQDFA = {<A,B> | A e B sono due DFA L(A)=L(B)}
Si dimostri ora il seguente teorema:
EQDFA è un linguaggio decidibile.
Dimostrazione
Per la dimostrazione si procederà a definire un terzo automa a stati finiti C che accetti le stringhe di A o quelle di B, ma non entrambe. Per realizzarlo si potranno usare solo le operazioni di intersezione, unione o complemento, perché sono chiuse rispetto ai linguaggi regolari. In particolare si utilizzerà la formula della differenza simmetrica:
In particolare: L(C)=0 se e solo se L(A)=L(B). Il problema EQDFA su A e B può essere dunque ricondotto a un problema di EDFA su C! Costruiamo allora la MdT deterministica F che risolve EQDFA:
F = "su ingresso <A,B>:
- costruisci C;
- esegui la MdT T su <C>;
- se T accetta, allora ACCETTA; altrimenti RIFIUTA."
Teorema 5 - ACFG è decidibile
Passiamo ora dai problemi decidibili relativi a linguaggi regolari a quelli relativi a linguaggi liberi dal contesto. Cominciamo col problema ACFG che consiste nel determinare se una grammatica libera dal contesto (CFG) genera una particolare stringa, ovvero:
ACFG = {<G,w> | G è una CFG che genera la stringa w}
Dimostriamo il seguente teorema:
ACFG è un linguaggio decidibile.
Dimostrazione
Metterci a fare tutte le derivazioni di G per vedere se una di queste è una derivazione di w sarebbe folle, perché nel caso in cui non fosse vero potremmo andare avanti all'infinito. L'alternativa è usare la grammatica G in forma normale di Chomsky, perché in questo caso le derivazioni di w sarebbero solo 2n-1 (dove n è la lunghezza della stringa), e avremmo la garanzia di trovare una soluzione in un numero finito di passi.
Costruiamo allora la MdT S che risolve ACFG:
S = "su ingresso <G,w>:
- converti G nella forma equivalente di Chomsky;
- fai una lista di tutte le derivazioni di 2n-1 passi, dove n=|w|;
- se una derivazione genera w, allora ACCETTA; altrimenti RIFIUTA."
Teorema 6 - ECFG è decidibile
Consideriamo il problema di Emptiness per grammatiche libere dal contesto, che si pone l'obiettivo di verificare se una CFG non genera alcuna stringa. Più formalmente:
ECFG = {<G> | G è una CFG e L(G)=0}
Dimostriamo il teorema:
ECFG è un linguaggio decidibile.
Dimostrazione
Per verificare se la grammatica è vuota dobbiamo dimostrare di non riuscire ad arrivare ad una stringa composta solo da terminali.
Come prima cosa dovremo scorrere la CFG e marcare tutti i terminali. Successivamente si passa a scansionare le regole, e se da una di queste risulta che una variabile può essere sostituita da terminali marcati, marchiamo anche lei. L'operazione va ripetuta marcando tutte le variabili ottenute a partire da simboli (terminali/variabili) già marcati. Se si arriva a marcare anche la variabile iniziale significa che da lei posso raggiungere una sequenza composta solo da terminali, quindi la MdT R che risolve ECFG dovrà rifiutare tale eventualità.
R = "su ingresso <G>:
1. marca i simboli terminali di G;
2. ripeti finché non ci sono nuove variabili marcate:
3. marca ogni variabile A in cui G abbia una regola
A->U1...Uk in cui ogni U
1, ... , U
k
sia già marcato;
4. se la variabile iniziale non è marcata, allora ACCETTA; altrimenti RIFIUTA."
Teorema 7 - sulla decidibilità dei linguaggi liberi dal contesto
Ogni linguaggio libero dal contesto è decidibile.
Dimostrazione
Sia A un qualsiasi linguaggio libero dal contesto generato dalla CFG G. Per la dimostrazione sfruttiamo la MdT S definita nel teorema di ACFG, e scriviamo la macchina di Turing MG che decide A:
MG = "su ingresso w:
- esegui S su ingresso <G,w>;
- se S accetta, allora ACCETTA; altrimenti RIFIUTA."
Teorema 8 - sull'indecidibilità dell'Halting Problem
Non tutti i problemi sono algoritmicamente risolvibili, e il più famoso di questi è l' Halting Problem: dato un programma ed una precisa specifica di cosa il programma debba fare, verificare che il programma funzioni come specificato. Il tutto si può ridurre al problema di verificare se una MdT accetta una data stringa in ingresso:
ATM = {<M,w> | M è una MdT e M accetta w}
ATM è Turing-riconoscibile, e infatti scrivere una MdT U che lo riconosca è decisamente semplice:
U = "su ingresso <M,w>:
- esegui M sull'ingresso w;
- se M entra nello stato di accettazione, allora ACCETTA; se M entra invece nello stato di rifiuto, RIFIUTA."
Qual è il problema allora? Che se M non termina su w, allora la macchina va in loop sull'ingresso <M,w>. Il fatto che non possa uscire da questo loop rende il problema indecidibile.
L'indecidibilità la dimostriamo con il metodo della diagonalizzazione scoperto dal matematico Cantor per misurare la dimensione degli insiemi infiniti. Poiché in collezioni infinite non è possibile contare gli elementi che ne fanno parte, per capire se due insiemi sono della stessa dimensione si verifica se è possibile mettere in corrispondenza gli elementi dell'uno con quelli dell'altro. Più formalmente, due insiemi infiniti A e B sono della stessa dimensione se esiste una corrispondenza f:A->B. Per corrispondenza si intende una funzione biettiva da A a B, quindi ogni elemento di A può corrispondere a un solo elemento di B, e ogni elemento di B ha un unico di elemento di A che corrisponde ad esso.
Facciamo un esempio: l'insieme N dei numeri naturali ha la stessa dimensione dell'insieme E dei numeri naturali pari? Esiste una corrispondenza f tra i due? Sì: f(n) = 2n. Quindi hanno stessa dimensione.
Anche se sembrerà di starci allontanando dall'obiettivo (dimostrare che ATM è indecidibile), dobbiamo introdurre un po' di teoremi e dimostrazioni di tipo matematico. Torneranno utilissime poi.
Insiemi contabili
Un insieme A è detto contabile se è finito o se ha la stessa dimensione di N.
Dimostrazione
Per la dimostrazione usiamo come esempio quello dei numeri razionali positivi Q, così definibili:
Q = {(m/n) | m,n ∈ N}
Trovare una corrispondenza tra i due insiemi non è banale, ma comunque possibile. Come prima cosa creiamo una matrice bidimensionale |N|x|N| e scriviamo in ogni cella (i,j) il numero razionale i/j. A questo punto creiamo una lista di numeri spostandoci sulle diagonali ed evitando le ripetizioni (ad esempio 1/1 e 2/2 sono lo stesso valore, quindi li contiamo una sola volta), secondo lo schema mostrato in figura:
Questa lista dimostra l'esistenza di una corrispondenza tra N e Q, quindi i due insiemi infiniti hanno la stessa dimensione.
Insiemi non contabili - Teorema
L'insieme dei numeri reali R non è contabile.
Dimostrazione
Dimostriamo il teorema per assurdo, sostenendo che R è contabile e che quindi esiste una sua corrispondenza con N. Questo ci semplifica la vita, perché basterà trovare una x∈R che non sia compresa nella corrispondenza per mostrare la contraddizione della tesi.
Supponiamo che f(n) sia una corrispondenza tra R ed N, e costruiamoci su misura una x che appartenga ad R ma non abbia corrispondenza in N. Per capire come, partiamo da un esempio:
Costruiamo la x in questo modo: x = 0 , c1 c2 ... cn
dove la cifra decimale ci deve essere diversa dalla i-sima cifra decimale dell'i-simo elemento. Riprendendo il nostro esempio:
Questa costruzione ci dà garanzia che x sia diverso da qualsiasi elemento di R messo in corrispondenza con N (da una fantomatica f(n) che per assurdo abbiamo supposto esistesse). Dato che x sfugge alla corrispondenza pur appartenendo all'insieme dei numeri reali, R ed N non sono della stessa dimensione, e in particolare R non è contabile.
Si noti che in questa dimostrazione si è sfruttato ancora un metodo che sfrutta la diagonali. Benedetto Cantor.
Insiemi non contabili - Corollario
Ci stiamo finalmente avvicinando al nostro obiettivo: dimostrare che ATM non è decidibile. Ci serve ancora quest'ultimo teorema:
Alcuni linguaggi non sono Turing-riconoscibili.
Dimostrazione
La chiave della dimostrazione è che l'insieme dei linguaggi possibili non è contabile, mentre quello delle macchine di Turing sì; dato che una MdT riconosce un solo linguaggio, alcuni linguaggi rimarranno tagliati fuori: quelli non Turing-riconoscibili. Questa spiegazione ci basterebbe se fossimo al bar a parlare di Turing-riconoscibilità, ma siccome - e per fortuna - non lo siamo dobbiamo verificare ogni affermazione.
I. L'insieme delle MdT è contabile
Dato un generico alfabeto Σ, l'insieme di tutte le stringhe Σ* da lui definite è contabile perché è possibile fare una lista di tutte le stringhe di una certa lunghezza (che è finita). Dal momento che ogni MdT può essere codificata come una stringa <M>, anche l'insieme delle MdT è contabile.
II. L'insieme dei linguaggi non è contabile
Definiamo sequenza binaria infinita una sequenza infinita di 0 e di 1, ad esempio 01011010010101011010110101011010110..
Definiamo B l'insieme di tutte le sequenze binarie infinite, e si può dimostrare che non è contabile utilizzando lo stesso metodo della diagonalizzazione usato per l'insieme dei numeri reali R.
Definiamo ora L l'insieme dei linguaggi definiti sull'alfabeto Σ e cerchiamo una relazione tra L e B. Lo scopo è chiaro: se la troviamo abbiamo dimostrato che l'insieme dei linguaggi non è contabile.
Dato un linguaggio A appartenente ad L, definiamo sequenza caratteristica di A (XA) la sequenza binaria in cui ogni bit vale 1 se A usa una possibile stringa del linguaggio, 0 altrimenti. Facciamo un esempio:
Σ*= {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, ...}
A = { 0, 1, 01, 11, 000, 010, ...}
XA = 0 1 1 0 1 0 1 1 0 1 ...
Possiamo quindi affermare che esiste una funzione f:L->B, dove f(A) è la sequenza caratteristica di A che è unica in B. L'esistenza della funzione ci permette finalmente di sostenere che se B non è contabile nemmeno l'insieme dei linguaggi L lo è.
Non decidibilità di ATM
Ci siamo, possiamo dimostrare che:
Dimostrazione
Anche in questo caso la dimostrazione avverrà per assurdo.
Ricordiamo che:
ATM = {<M,w> | M è una MdT e M accetta w}
Supponiamo di avere un decisore H del linguaggio tale che:
H(<M,w>) = / ACCETTA se M accetta w
\ RIFIUTA se M non accetta w
Costruiamo ora una MdT D che usi H come sottoprocedura e faccia esattamente l'opposto:
D: "su ingresso <M>:
- esegui H sull'ingresso <M,<M>>; (dove M è la stringa che descrive la MdT)
- se H accetta, allora RIFIUTA; altrimenti ACCETTA."
Il comportamento di D è quindi il seguente:
D(<M>) = / ACCETTA se M non accetta <M>
\ RIFIUTA se M accetta <M>
Cosa succede se chiediamo a D di girare su sé stesso?
D(<D>) = / ACCETTA se D non accetta <D> ????
\ RIFIUTA se D accetta <D> ????
In entrambi i casi il decisore ciocca, perché dovrebbe tenere il comportamento opposto a sé stesso. Siamo dunque arrivati a una contraddizione, dimostrando così per assurdo che ATM non è decidibile.
Mi sembra di sentirvi dire: "E in tutto questo la diagonalizzazione dove sta?".
Ri-rappresentiamo il tutto con una bella matrice: come indice di ogni riga mettiamo la MdT Mi, e come indice delle colonne la stringa <Mj>. Se una Mi accetta una stringa <Mj>, scriveremo accetta
nella cella (i,j), rifiuta
altrimenti. Aggiungiamo poi un'ultima riga per il decisore D, e un'ultima colonna per la stringa <D> che lo descrive. La riga D è riempita scrivendo l'opposto delle celle che si trovano sulla diagonale della stessa colonna. Bene: che diavolo scriviamo nella cella che incrocia D e <D>? Appunto. Abbiamo così ritrovato la stessa contraddizione di prima su una diagonale, e questo non può che renderci felici.
Teorema 9 - sui linguaggi co-Turing riconoscibili
Un linguaggio è non-Turing riconoscibile o co-Turing riconoscibile se è il complemento di un linguaggio Turing-riconoscibile.
Un linguaggio è decidibile se e solo se è Turing-riconoscibile e co-Turing riconoscibile.
Dimostrazione
Per abbreviare, consideriamo un linguaggio A e chiamiamo:
- Adec: "A decidibile";
- ATu: "A Turing-riconoscibile";
- AcoTu: "A co-Turing-riconoscibile".
Dimostriamo entrambi i sensi del "se e solo se".
I. Se Adec allora ATu Λ AcoTu
Se un linguaggio A è decidibile è per forza di cose anche Turing-riconoscibile, e dato che il complemento di un linguaggio decidibile è anch'esso decidibile, A sarà anche co-Turing-riconoscibile.
I. Se ATu Λ AcoTu allora Adec
Introduciamo il riconoscitore M1 per il linguaggio A, e il riconoscitore M2 per il complemento del linguaggio A. Definiamo ora una MdT M che sia decisore per A:
M: "su ingresso w:
- esegui M1 e M2 in parallelo sull'ingresso w; (M dovrà dunque avere due nastri, uno per decisore)
- se M1 accetta, allora ACCETTA; se M2 accetta, allora RIFIUTA."
Dimostriamo che M è un decisore per A:
- dato che ogni stringa w può essere in A o nel suo complemento, o M1 o M2 la accetteranno;
- dato che M termina quando o M1 o M2 accettano, M terminerà sicuramente.
Per entrambi i motivi, M è un decisore di A, e quindi A è decidibile.
Teorema 10 - corollario al Teorema 9
Il complemento di ATM è Turing-riconoscibile.
Dimostrazione
Visto che ATM non è decidibile, o ATM o il suo complemento saranno sicuramente non riconoscibili. Dato però che all'inizio del paragrafo sul Teorema 8 abbiamo dimostrato che ATM è Turing-riconoscibile, il suo complemento non può esserlo, o per il Teorema 9 ATM diventerebbe decidibile.
Torna alla pagina di Informatica Teorica