7. Decidibilità e indecibilità

Una volta esaminati gli automi, le grammatiche e le macchine di Turing, adesso ci concentreremo sulla potenza degli algoritmi nella risoluzione dei problemi. Vedremo che alcuni problemi non possono essere risolti in forma algoritmica e vedremo come dimostrarlo. Iniziamo a trattare i linguaggi decidibili mediante algoritmi e il primo problema che affrontiamo è il problema dell'accettazione per DFA, il quale consiste nel testare se un particolare automa finito deterministico accetta una data stringa può essere espresso come un linguaggio $A_{DFA}$. Questo linguaggio contiene le codifiche di tutti i DFA con le stringhe che essi accettano. Quindi definiamo$A_{DFA} = \{ < B, w > |$ B è un DFA che accetta la stringa di input w }.

Il problema di verificare se un DFA B accetta l'input w coincide con il problema di verificare se $< B, w >$ è un elemento del linguaggio $A_{DFA}$. Enunciamo il seguente teorema:

Teorma DFA decidibile

$A_{DFA}$ è un linguaggio decidibile.

Per dimostrare questo teorema esaminiamo in primo luogo l'input $< B, w >$ che rappresenta un DFA B insieme ad una stringa w. B può essere rappresentato attraverso la sua lista di componenti. Quando M riceve il suo input viene verificata se viene rappresentato correttamente il DFA e la stringa. In caso negativo, viene rifiutato. In caso affermativo invece, viene effettuato la simulazione, tenendo traccia dello stato corrente di B e della posizione corrente di B nell'input w attraverso la scrittura sul nastro. Inizialmente lo stato correnti di B è $q_0$ e la posizione corrente dell'input di B è il simbolo più a sinistra di w. Gli stati e le posizioni vengono aggiornati in base alla funzione di transizione specificata da $\delta$. Quando M termina l'elaborazione dell'ultimo simbolo di w, M accetta l'input se B è in uno stato di accettazione, mentre lo rifiuta in caso contrario.

In maniera molto simile possiamo dimostrare un teorema per gli automi a stati finiti non deterministici. Quindi dato $A_{NFA} = \{ < B,w > |$ B è un NFA che accetta la stringa di input w }, possiamo definire il seguente teorema:

Teorma NFA decidibile

$A_{NFA}$ è un linguaggio decidibile.

Per dimostrare questo teorema esaminiamo in primo luogo una TM N che decide $A_{NFA}$. Potremmo progettare N in modo che operi come M, simulando un NFA inviece di un DFA. Potremmo anche seguire un'altra strada, ovvero quella nella quale N usa M come una sottoprocedura. Poichè M è progettata per funzionare con un DFA, N prima converte l'NFA che riceve come input in un DFA e poi lo passa ad M. Quindi possiamo definire N = "Su un input $< B, w >$ dove B è un NFA e w è una stringa:

• Converte l'NFA B in un DFA C equivalente, usando la procedura di conversione
• Esegue la TM M sull'input $< C, w >$
• Se M accetta, accetta altrimenti rifiuta."

L'esecuzione della TM M nella fase 2 significa incorporare M nella progettazione di N come sottoprocedura.

Anche i linguaggi context-free, le espressioni regolari e i DFA sono dedicibili e la dimostrazione dei singoli teoremi è simile a quelle viste in precedenza.

Dopo aver visto alcuni teoremi della decidibilità, approfondiamo l'indecidibilità. Un primo teorema stabilisce che l'indecidibilità di uno specifico linguaggio: il problema di determinare se una macchina di Turing accetta una determinata stringa in input. Definiamo tale linguaggio $A_{TM}$ e per analogia $A_{DFA}$ e$A_{CFG}$. Mentre $A_{DFA}$ e $A_{CFG}$ sono decidibili, $A_{TM}$ non lo è. Sia$A_{TM} = \{ < M, w > |$ M è una TM e M accetta w }, possiamo definire il seguente teorema:

Teorema di indecidibilità di una macchina di Turing

$A_{TM}$ è indecidibile.

Prima di dimostrare questo teorema occorre definire una macchina di Turing U che riconosce $A_{TM}$. U = "Su inpu < M, w >, dove M è una TM e w è una stringa:

• Simula M su input w
• Se durante la computazione M entra nello stato di accettazione, accetta altrimenti rifiuta."

Se l'algoritmo avesse modo di determinare che M non si ferma su w, sarebbe in tal caso in grado di rifiutare w. Però nessun algoritmo è in grado di determinarlo. Per dimostrare dell'indecidibilità di $A_{ATM}$ si utilizza la tecnica della diagonalizzazione. Questo teorema si basa sullo stabilire se due insiemi infiniti hanno la stessa cardinalità o se uno è più grande dell'altro. Per risolvere questo problema si cerca di contare gli elementi.

Due insiemi finiti hanno la stessa dimensione se gli elementi di un insieme possono essere accoppiati agli elementi dell'altro gruppo. Così facendo si confrontano le dimensioni senza ricorrere al conteggio. Utilizziamo questo principio anche per gli insiemi infiniti e per poterlo fare, diamo una definizione di funzione iniettiva, funzione suriettiva e di funzione biettiva.

Definizione di funzione iniettiva, funzione suriettiva e di funzione biettiva

Supponiamo di avere due insiemi A e B e una funzione f da A in B. Si definisce funzione iniettiva, quella funzione f che non mappa mai due elementi diversi nello stesso punto, ovvero per la quale si ha $f(a) \ne f(b)$ ogniqualvolta che $a \ne b$. Invece diciamo che la funzione f è una funzione suriettiva se tocca ogni elemento di B, ovvero se per ogni $b \in B$ esiste un $a \in A$ tale che $f(a)=b$. Possiamo affermare che A e B hanno la stessa cardinalità se esiste una funzione iniettiva e suriettiva. Una funzione che è contemporaneamente suriettiva e iniettiva, prende il nome di funzione biettiva. In questa funzione ogni elemento di A viene mappato in un unico elemento di B e per ogni elemento di B esiste un unico elemento di A che viene mappato in esso.

Consideriamo l'insieme dei numeri naturali N e l'insieme Q definito come: $Q =\{ \frac{m}{n} | m , n \in N$. Per ottenere la lista degli elementi dei due insiemi creiamo una matrice infinita contenente tutti i numeri razionali positivi. La riga i-esima contiene tutti i numeri con numeratore i e la colonna j-esima ha tutti i numeri con denominatore j. in tal modo il numero $\frac{i}{j}$ occupa la i-esima riga e la j-esima colonna. Adesso abbiamo la necessita di trasformare questa matrice in una lista. Un modo errato di farlo è quello di cominciare con una lista di tutti gli elementi della prima riga. Essendo infinita, non raggiungeremo mai la seconda.

Un modo corretto di farlo consiste nell'elencare gli elementi sulle diagonali sovrapposte al diagramma a partire da un angolo. In questo modo avremo quindi una lista di tutti gli elementi di Q. Dopo aver visto la biezioni di questi due insiemi, potremmo pensare di dimostrare che presa qualsiasi coppia di insiemi infiniti, questi hanno la stessa dimensione.

A questo punto possiamo dire che abbiamo capito che alcuni linguaggi non sono decidibili e neppure Turing riconoscibili, per il semplice fatto che l'insieme dei linguaggi è non numerabile, mentre l'insieme di tutte le macchine di Turing è numerabile. Poichè ogni macchina di Turing è in grado di riconoscere un solo linguaggio e ci sono più linguaggi che macchine di Turing, quindi alcuni linguaggi non sono Turing-riconoscibili.

Teoremma linguaggi non Turing-riconoscibili

Alcuni linguaggi non sono Turing-riconoscibili.

Per dimostrare che l'insieme di tutte le macchine di Turing è numerabile dobbiamo prima osservare che l'insieme di tutte le stringhe $\sum *$ è numerabile per ogni alfabeto $\sum$. Avendo un numero finito di stringhe di ogni lunghezza, possiamo formare una lista di $\sum *$ scrivendo tutte le stringhe di lunghezza 0, 1, 2 e così via. L'insieme di tutte le macchine di Turing M; può essere codificata con una stringa <MM>. Se ci limitiamo a tralasciare quelle stringhe che non sono la codifica di una macchina di Turing, possiamo ottenere una lista di tutte le macchine di Turing. Per mostrare che l'insieme di tutti i linguaggi è non numerabile, dobbiamo prima osservare che l'insieme delle sequenze binarie infinite è non-numerabile.

Una sequenza binaria infinita è una sequenza senza fine di 0 e 1. Sia B l'insieme di tutte le sequenze binarie infinite, possiamo dimostrare che B è non numerabile. Per farlo si può utilizzare una dimostrazione mediante diagonalizzazione. Inoltre L è non-numerabile e lo mostriamo dando una corrispondenza con B, dimostrando così che i due insiemi hanno la stessa cardinalità. Sia $\sum * = \{s_1,s_2,s_3, ... \}$. Ogni linguaggio $A \in L$ ha un'unica sequenza in B. Il bit i-esimo della sequenza è 1 se $s_i \in A$ ed è uno 0 se $s_i \notin A$; questa è definita quindi sequenza caratteristica di A. La funzione $f : L \longrightarrow B$, dove f(A) è uguale alla squenza caratteristica di A è una funzione biettiva. Pertanto essendo B non numerabile, anche L è non numerabile.

Questa è la dimostrazione che l'insieme di tutti i linguaggio non può essere messo in corrispondenza biunivoca con l'insieme di tutte le macchine di Turing.