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 la funzione ricorsiva a cui è stato associato l'indice .

Enumerazione delle funzioni ricorsiveModifica

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 → ℕ, px il programma associato al numero x e φx(k) la funzione di k variabili calcolata dal programma px. Tale numero x sarà l'indice del programma px o indice della funzione φx(k) calcolata proprio da px. Per enumerazione delle funzioni ricorsive si intende proprio la corrispondenza fra x e φx(k).

Enumerazione delle macchine di TuringModifica

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 E {0,1}* | w è una stringa e w non E TM}, Ld non è ricorsivamente enumerabile.

Enumerazione delle macchine a registri elementariModifica

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica