Informatica Teorica - Decidibilità

Torna alla pagina di Informatica Teorica

---

 :: Informatica Teorica - Decidibilità ::

Appunti & Dimostrazioni del 21 Aprile

Teorema 1 - A_DFA è decidibile

Sia dato il problema di verificare se un automa a stati finiti deterministico accetta una stringa. Più formalmente:
A_DFA = {<B,w> | B è un DFA che accetta la stringa in ingresso w}

Si dimostri il seguente teorema:

Dimostrazione

Dobbiamo trovare una MdT deterministica che lo risolva:

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, Σ, δ, q₀, 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 q₀ 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 - A_NFA è 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:

Teorema 3 - E_DFA è decidibile

Il problema Emptiness verifica se un automa a stati finiti non accetta alcuna stringa, ovvero:
E_DFA = {<A> | A è un DFA e L(A)=0}

Si dimostri ora il seguente teorema:

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 E_DFA:

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 - EQ_DFA è decidibile

Il problema Equivalence verifica se due automi a stati finiti riconoscono lo stesso linguaggio, ovvero:
EQ_DFA = {<A,B> | A e B sono due DFA L(A)=L(B)}

Si dimostri ora il seguente teorema:

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 EQ_DFA su A e B può essere dunque ricondotto a un problema di E_DFA su C! Costruiamo allora la MdT deterministica F che risolve EQ_DFA:

Teorema 5 - A_CFG è decidibile

Passiamo ora dai problemi decidibili relativi a linguaggi regolari a quelli relativi a linguaggi liberi dal contesto. Cominciamo col problema A_CFG che consiste nel determinare se una grammatica libera dal contesto (CFG) genera una particolare stringa, ovvero:
A_CFG = {<G,w> | G è una CFG che genera la stringa w}

Dimostriamo il seguente teorema:

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 A_CFG:

Teorema 6 - E_CFG è 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:
E_CFG = {<G> | G è una CFG e L(G)=0}

Dimostriamo il teorema:

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 E_CFG dovrà rifiutare tale eventualità.

Teorema 7 - sulla decidibilità dei linguaggi liberi dal contesto

Dimostrazione

Sia A un qualsiasi linguaggio libero dal contesto generato dalla CFG G. Per la dimostrazione sfruttiamo la MdT S definita nel teorema di A_CFG, e scriviamo la macchina di Turing M_G che decide A:

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:
A_TM = {<M,w> | M è una MdT e M accetta w}

A_TM è Turing-riconoscibile, e infatti scrivere una MdT U che lo riconosca è decisamente semplice:

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 A_TM è indecidibile), dobbiamo introdurre un po' di teoremi e dimostrazioni di tipo matematico. Torneranno utilissime poi.

Insiemi contabili

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

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 , c₁ c₂ ... c_n
dove la cifra decimale c_i 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 A_TM non è decidibile. Ci serve ancora quest'ultimo teorema:

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 (X_A) la sequenza binaria in cui ogni bit vale 1 se A usa una possibile stringa del linguaggio, 0 altrimenti. Facciamo un esempio:

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 A_TM

Ci siamo, possiamo dimostrare che:

Dimostrazione

Anche in questo caso la dimostrazione avverrà per assurdo.
Ricordiamo che:
A_TM = {<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:

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 A_TM 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 M_i, e come indice delle colonne la stringa <M_j>. Se una M_i accetta una stringa <M_j>, 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.

Dimostrazione

Per abbreviare, consideriamo un linguaggio A e chiamiamo:

• A_dec: "A decidibile";
• A_Tu: "A Turing-riconoscibile";
• A_coTu: "A co-Turing-riconoscibile".

Dimostriamo entrambi i sensi del "se e solo se".

I. Se A_dec allora A_Tu Λ A_coTu
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 A_Tu Λ A_coTu allora A_dec
Introduciamo il riconoscitore M₁ per il linguaggio A, e il riconoscitore M₂ per il complemento del linguaggio A. Definiamo ora una MdT M che sia decisore per A:

Dimostriamo che M è un decisore per A:

• dato che ogni stringa w può essere in A o nel suo complemento, o M₁ o M₂ la accetteranno;
• dato che M termina quando o M₁ o M₂ accettano, M terminerà sicuramente.

Per entrambi i motivi, M è un decisore di A, e quindi A è decidibile.

Teorema 10 - corollario al Teorema 9

Dimostrazione

Visto che A_TM non è decidibile, o A_TM o il suo complemento saranno sicuramente non riconoscibili. Dato però che all'inizio del paragrafo sul Teorema 8 abbiamo dimostrato che A_TM è Turing-riconoscibile, il suo complemento non può esserlo, o per il Teorema 9 A_TM diventerebbe decidibile.

---

Torna alla pagina di Informatica Teorica