Enumerazioni nella teoria della calcolabilità

Le tecniche della enumerazione matematica, come ad esempio la funzione coppia di Cantor, vengono spesso usate nella teoria della calcolabilità per dimostrare molti teoremi riguardanti i vari modelli di calcolo.

In questi casi un'enumerazione consiste nell'assegnare (enumerare) a ciascuno degli oggetti di un certo modello di calcolo un numero naturale univoco, permettendo così di indicizzarli. Ad esempio nel caso delle funzioni ricorsive, come conseguenza dell'enumerazione, si indica con $\varphi _{i}$ la funzione ricorsiva a cui è stato associato l'indice $i$.

Enumerazione delle funzioni ricorsive

Esiste una corrispondenza biettiva fra l'insieme dei programmi e l'insieme dei numeri naturali. È possibile dimostrare l'esistenza di questa corrispondenza in modo costruttivo, tramite quindi un algoritmo che consenta di associare un programma ad un numero naturale e viceversa. Questa corrispondenza si chiama Enumerazione di Gödel o processo di gödelizzazione.

Infatti sia P l'insieme dei programmi e sia ƒ una corrispondenza bigettiva ƒ: P → ℕ, p_x il programma associato al numero x e φ_x^(k) la funzione di k variabili calcolata dal programma p_x. Tale numero x sarà l'indice del programma p_x o indice della funzione φ_x^(k) calcolata proprio da p_x. Per enumerazione delle funzioni ricorsive si intende proprio la corrispondenza fra x e φ_x^(k).

Enumerazione delle macchine di Turing

Sappiamo che una macchina di Turing può essere trasformata in una stringa binaria; in particolare i dati sui suoi nastri verranno tradotti in binario (se già non lo sono) attraverso delle convenzioni universali (ad esempio tramite Ascii o altri encoding); ad esempio agli stati potranno essere assegnati dei numeri interi e quindi uno stato sarà tradotto come 00...0 tante volte quanto il numero ad esso associato, così per i simboli di nastro; una transizione T(qi,Xj)→(qk,Xl,Dm) con q stati, X simboli di nastro e D direzione in cui si sposta la testina con 0(ì)10(j)10(k)10(l)10(m) dove con 0(i) si intende 0 ripetuto i volte; allo stesso modo più transizioni potranno essere separate da 11 poiché nella codifica di una transizione non compaiono due 1 consecutivi. Poiché una TM è univocamente identificata dall'insieme delle sue transizioni questo codice è sufficiente; infine per associare ad una TM la sua stringa di input semplicemente si fa seguire alla sua rappresentazione binaria 111 seguito dal codice binario della stringa in input; In questo modo ogni TM è associata ad un numero unico e quindi si può procedere ad una enumerazione delle macchine di Turing.

Nota: il Linguaggio di diagonalizzazione è dato dall'insieme di quelle stringhe binarie che rappresentano TM che non terminano in uno stato accettante quando ricevono la loro codifica binaria in input, cioè Ld={w ∈ {0,1}* | w è una stringa e w non ∈ TM}, Ld non è ricorsivamente enumerabile.