Visualizza wikitesto di Enumerazioni nella teoria della calcolabilità

{{S|matematica}}

Le tecniche della [[Enumerazione (matematica)|enumerazione matematica]], come ad esempio la [[Enumerazione (matematica)|funzione coppia di Cantor]], vengono spesso usate nella [[teoria della calcolabilità]] per dimostrare molti teoremi riguardanti i vari [[modello di calcolo|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 [[indicizzazione|indicizzarli]]. Ad esempio nel caso delle [[funzione ricorsiva|funzioni ricorsive]], come conseguenza dell'enumerazione, si indica con <math>\varphi_i</math> la funzione ricorsiva a cui è stato associato l'indice <math>i</math>.

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

== 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.

{{Portale|matematica}}

[[Categoria:Teoria della computazione]]