Enumerații în teoria calculabilității
Tehnicile de enumerare matematică , cum ar fi funcția de pereche Cantor , sunt adesea folosite în teoria calculabilității pentru a demonstra multe teoreme referitoare la diferite modele de calcul .
În aceste cazuri, o enumerare constă în atribuirea (enumerarea) fiecăruia dintre obiectele unui anumit model de calcul, un număr natural unic, permițând astfel indexarea acestora . De exemplu, în cazul funcțiilor recursive , ca o consecință a enumerării, este indicat cu funcția recursivă la care a fost asociat indexul .
Enumerarea funcțiilor recursive
Există o corespondență bijectivă între setul de programe și setul de numere naturale. Este posibil să se demonstreze existența acestei corespondențe într-un mod constructiv, prin urmare printr-un algoritm care permite asocierea unui program la un număr natural și invers. Această corespondență se numește enumerare Gödel sau proces de gödelizare.
De fapt, fie P setul de programe și fie ƒ o corespondență bijectivă ƒ: P → ℕ, p x programul asociat cu numărul x și φ x (k) funcția k variabile calculate de programul p x . Acest număr x va fi indicele programului p x sau indicele funcției φ x (k) calculat precis din p x . Prin enumerarea funcțiilor recursive înțelegem exact corespondența dintre x și φ x (k) .
Enumerarea mașinilor Turing
Știm că o mașină Turing poate fi transformată într-un șir binar; în special, datele de pe casetele sale vor fi traduse în binar (dacă nu sunt deja) prin convenții universale (de exemplu prin Ascii sau altă codificare); de exemplu, numerele întregi pot fi atribuite stărilor și, prin urmare, o stare va fi tradusă ca 00 ... 0 de câte ori numărul asociat acestuia, deci pentru simbolurile de bandă; o tranziție T (qi, Xj) -> (qk, Xl, Dm) cu q stări, simboluri de bandă X și direcția D în care capul se mișcă cu 0 (ì) 10 (j) 10 (k) 10 (l) 10 (m) unde 0 (i) înseamnă 0 repetat de ori; în același mod, mai multe tranziții pot fi separate de 11 deoarece două 1 consecutive nu apar în codarea unei tranziții. Deoarece un TM este identificat în mod unic prin setul de tranziții, acest cod este suficient; în cele din urmă, pentru a asocia șirul de intrare la un TM, urmați pur și simplu reprezentarea sa binară 111 urmată de codul binar al șirului de intrare; În acest fel, fiecare TM este asociat cu un număr unic și, prin urmare, este posibil să se treacă la o enumerare a mașinilor Turing.
Notă: Limbajul de diagonalizare este dat de setul de șiruri binare reprezentând TM care nu se termină într-o stare de acceptare atunci când primesc codarea lor binară în intrare, adică Ld = {w E {0,1} * | w este un șir și w nu este E TM}, Ld nu este recursiv enumerabil.
