Enumerazioni nella teoria della calcolabilità
Da Wikipedia, l'enciclopedia libera.
Questa voce è solo un abbozzo (stub). Se puoi, contribuisci adesso a migliorarla secondo le convenzioni di Wikipedia. Per l'elenco completo degli stub di matematica, vedi la relativa categoria.
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 i.
[modifica] Enumerazione delle funzioni ricorsive
[modifica] Enumerazione della macchine di Turing
Sappiamo che una macchina di Tùring 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 transiozioni 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 Tùring 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 TM e w non E TM} Ld è ricorsivamente enumerabile
