Teoria calculabilității

Teoria calculabilității este o ramură a logicii matematice, a informaticii și a teoriei computației, care își are originea în anii 1930, cu studiul funcțiilor calculabile^⁠(d) și al gradelor Turing^⁠(d). Domeniul s-a extins, incluzând studiul calculabilității și definibilității generalizate. În aceste domenii, teoria calculabilității se suprapune cu teoria demonstrațiilor^⁠(d) și teoria descriptivă a mulțimilor^⁠(d).

Chestiunile de bază abordate de teoria calculabilității sunt „ce înseamnă că o funcție de numere naturale este calculabilă?” și „cum pot fi clasificate funcțiile necalculabile într-o ierarhie în funcție de nivelul lor de necalculabilitate?”. Răspunsurile la aceste întrebări au condus la o bogată teorie care este încă activ cercetată.

Teoreticienii calculabilității din logica matematică studiază adesea teoria calculabilității relative, noțiunile de reductibilitate structurile pe grade descrise în acest articol. Acest lucru contrastează cu teoria ierarhiilor subrecursive, cu metodele formale^⁠(d) și cu limbajele formale, care sunt comune în studiul de teoriei calculabilității în informatică. Există însă o suprapunere considerabilă de cunoștințe și metode între aceste două comunități de cercetare și nu se poate trasa o linie fermă de demarcație între ele.

Mulțimi calculabile și necalculabile

Teoria calculabilității își are originea în anii 1930, cu activitatea lui Kurt Gödel, Alonzo Church, Alan Turing, Stephen Kleene și Emil Leon Post^⁠(d).

Rezultatele fundamentale obținute de cercetători au stabilit Turing-calculabilitatea^⁠(d) ca fiind formalizarea corectă a ideii informale de calcul efectiv. Aceste rezultate l-au condus pe Stephen Kleene (1952) să introducă denumirile de „teza lui Church” (Kleene 1952:300) și „teza lui Turing” (Kleene 1952:376). În zilele noastre, acestea sunt adesea considerate a fi o singură ipoteză, teza Church–Turing, care prevede că orice funcție care calculabilă de un algoritm este o funcție calculabilă^⁠(d). Deși inițial sceptic, prin 1946, Gödel a susținut și el această teză:

"Tarski a subliniat în prelegerea sa (și cred că pe bună dreptate) marea importanță a conceptului general de recursivitate (sau calculabilitatea lui Turing). Cred că această importanță se datorează în mare parte faptului că acest concept a reușit pentru prima dată să dea o noțiune absolută unei interesante noțiuni epistemologice, adică una care să nu depindă de formalismul ales.*”(Gödel 1946 în Davis, 1965:84).

Împreună cu definiția calculului efectiv au venit și primele demonstrații că există probleme în matematică, ce nu pot fi decise^⁠(d) în mod eficient. Church (1936a, 1936b) și Turing (1936), inspirați de tehnicile utilizate de către Gödel (1931) pentru a-și demonstra teoremele de incompletitudine, a demonstrat independent că problema deciziei nu este efectiv decidabilă. Acest rezultat a arătat că nu există nicio procedură algoritmică care să poată decide în mod corect dacă unele propoziții matematice arbitrare sunt adevărate sau false.

Multe probleme din matematică au fost demonstrate a fi indecidabile după încetățenirea acestor prime exemple. În 1947, Markov și Post au publicat articole independente în care arătau că problema cuvintelor pentru semigrupuri nu poate fi decisă efectiv. Dezvoltând pe marginea acestui rezultat, Piotr Novikov^⁠(d) și William Boone^⁠(d) au arătat independent în 1950 că problema cuvântului pentru grupuri^⁠(d) nu este nici ea eficient rezolvabilă: nu există nicio procedură efectivă care, dat fiind un cuvânt dintr-un grup finit generat, să decidă dacă elementul reprezentat prin cuvânt este elementul neutru al grupului. În 1970, Iuri Matiasevici^⁠(d) a demonstrat (folosind rezultatele Juliei Robinson^⁠(d)) teorema lui Matiasevici^⁠(d), care afirmă că a zecea problemă a lui Hilbert^⁠(d) nu are soluție efectivă; este vorba de problema dacă există o procedură eficientă de a decide dacă o ecuație diofantică^⁠(d) cu coeficienți întregi are o soluție în mulțimea numerelor întregi. Lista problemelor indecidabile dă exemple suplimentare de probleme care nu au nicio soluție calculabilă.

Studiul căror construcții matematice care pot fi efectiv efectuate este uneori numit matematică recursivă; Handbook of Recursive Mathematics (Ershov et al. 1998) acoperă multe din rezultatele cunoscute în acest domeniu.

Calculabilitate Turing

Principala formă de calculabilitate studiată în teoria calculabilității este cea introdusă de Turing (1936). O mulțime de numere naturale este declarată a fi mulțime calculabilă^⁠(d) (numită și decidabilă, recursivă, sau Turing-calculabilă) dacă există o mașină Turing care, dat fiind un număr n, se oprește cu ieșirea 1 dacă n este în mulțime și se oprește cu ieșirea 0 daca n nu este în mulțime. O funcție f definită pe mulțimea numerelor naturale cu valori tot în ea este o funcție recursivă sau (Turing) calculabilă^⁠(d) dacă există o mașină Turing care, când i se pune la intrare n, se oprește și întoarce la ieșire f(n). Utilizarea mașinii Turing aici nu este necesară; există multe alte modele de calcul^⁠(d) care au aceeași putere de calcul ca și mașina Turing; de exemplu funcțiile μ-recursive^⁠(d) obținute din operatorul primitiv de recursivitate și operatorul μ.

Terminologia pentru funcții și mulțimi recursive nu este complet standardizată. Definirea în termeni de funcții μ-recursive, precum și o altă definiție a funcțiilor rekursive dată de Gödel a condus la numele tradițional de recursive pentru mulțimi și funcții calculabile de către o mașină Turing. Cuvântul decidabil provine de la cuvântul german Entscheidungsproblem (problema deciziei) care a fost folosit în primele lucrări ale lui Turing și ale altora. În utilizarea contemporană, termenul de „funcție calculabilă” are mai multe definiții: conform Cutland (1980), este o funcției parțial recursivă (care pot fi nedefinită pentru unele intrări), în timp ce în conformitate cu Soare (1987) este una total recursivă (echivalent, funcție general recursivă). Acest articol cum urmează această din urmă convenție. Soare (1996) oferă comentarii suplimentare cu privire la terminologie.

Nu toate mulțimile de numere naturale sunt calculabile. Problema opririi, care este o mulțime de (descrieri de) mașini Turing care se opresc la intrarea 0, este un exemplu bine-cunoscut de mulțime necalculabilă. Existența a numeroase mulțimi necalculabile rezultă din faptul că există doar un număr numărabil de mașini Turing, și, astfel, numai un număr numărabil de mulțimi calculabile, dar există un număr nenumărabil de mulțimi de numere naturale.

Deși problema opririi nu este calculabilă, se poate simula execuția programului și se poate produce o listă infinită de programe care se opresc. Astfel, problema opririi este un exemplu de mulțime recursiv enumerabilă^⁠(d), adică o mulțime ale cărei elemente pot fi enumerate de către o mașină Turing (alți termeni pentru „recursiv enumerabilă” ar fi și calculabil enumerabilă și semidecidabilă). Echivalent, o mulțime este recursiv enumerabilă dacă și numai dacă este codomeniul unei funcții calculabile. Mulțimile recursiv enumerabile, deși nu sunt decidabile în general, au fost studiate în detaliu în teoria calculabilității.

Domenii de cercetare

Începând cu teoria mulțimilor recursive și cu funcțiile descrise mai sus, domeniul teoriei calculabilității s-a extins și include astăzi studiul multor subiecte strâns legate. Acestea nu sunt domenii independente de cercetare: fiecare dintre aceste domenii atrag idei și rezultate de la celelalte, și majoritatea teoreticienilor calculabilității sunt familiarizați cu majoritatea lor.

Calculabilitate relativă și grade Turing

Teoria calculabilității din logica matematică s-a concentrat în mod tradițional pe calculabilitatea relativă, o generalizare a calculabilității Turing definită folosind mașini Turing cu oracol^⁠(d), concept introdus de Turing (1939). O mașină Turing cu oracol este un dispozitiv ipotetic care, în plus față de efectuarea acțiunilor unei mașini Turing obișnuite, este capabilă să pună întrebări unui oracol, care este o anumită mulțime de numere naturale. Mașina cu oracol poate pune întrebări de forma „n este în mulțimea oracol?”. Fiecare întrebare va primi imediat răspunsul corect, chiar dacă mulțimea oracil nu este calculabilă. Astfel, o mașină cu un oracol necalculabil va fi capabilă să calculeze mulțimi pe care o mașină Turing fără oracol nu le poate calcula.

Informal, o mulțime de numere naturale A este Turing reductibilă^⁠(d) la o mulțime B dacă există o mașină cu oracol care spune corect dacă numerele sunt în A atunci când rulează cu B ca mulțime oracol (în acest caz, despre mulțimea A se spune și că este (relativ) calculabilă din B și recursivă în B). Dacă o mulțime A este Turing reductibilă la o mulțime B și B este Turing reductibilă la A, atunci se spune despre aceste mulțimi că au același grad Turing (numit și grad de nerezolvabilitate). Gradul Turing al unei mulțimi dă o măsură precisă a cât de necalculabilă este ea.

Mulțimile de numere naturale care nu sunt calculabile, inclusiv multe mulțimi diferite care codifică variante ale problemei opririi^⁠(d), au două proprietăți în comun:

1. Sunt recursiv enumerabile^⁠(d), și
2. Fiecare poate fi tradusă în oricare alta printr-o reducere neinjectivă^⁠(d). Adică, date fiind astfel de mulțimi A și B, există o funcție total calculabilă f astfel încât A = {x : f(x) ∈ B}. Se spune despre aceste mulțimi că sunt echivalente neinjectiv (sau m-echivalente).

Reducerile neinjective sunt „mai puternice” decât reducerile Turing: dacă o mulțime A este reductibilă neinjectiv la o mulțime B, atunci A este Turing reductibilă la B, dar reciproca nu este mereu valabilă. Deși exemplele naturale de mulțimi necalculabile sunt toate echivalente neinjectiv, se poate construi mulțimea recursiv enumerabilă A și B astfel încât A este Turing reductibilă la B, dar nu reductibilă neinjectiv la B. Se poate demonstra că toate mulțimile recursiv enumerabile sunt reductibile neinjectiv la problema opririi, și, astfel, problema opririi este cea mai complicată mulțime recursiv enumerabilă în raport cu reductibilitatea neinjectivă și cu reductibilitatea Turing. Post (1944) a întrebat dacă toate mulțimile recursiv nenumerable sunt fie calculabile fie echivalente Turing cu problema opririi, adică dacă nu există nicio mulțime recursiv enumerabilă cu un grad Turing intermediar între cele două.

Ca rezultate intermediare, Post a definit tipurile naturale de mulțimi recursiv enumerabile ca simple^⁠(d), hipersimple^⁠(d) și hiperhipersimplu. Post a arătat că aceste mulțimi sunt strict între mulțimile calculabile și problema opririi în ce privește reductibilitatea neinjectivă. Post a arătat și că unele dintre ele sunt strict intermediare în raport cu alte noțiuni de reductibilitate mai puternice decât reductibilitatea Turing. Dar Post a lăsat deschisă problema principală a existenței mulțimilor recursiv-enumerabile de grade Turing intermediare; această problemă a devenit cunoscută sub numele de problema lui Post^⁠(d). După zece ani, Kleene și Post au arătat în 1954 că există grade Turing intermediare între cel al mulțimilor calculabile și cel al problemei opririi, dar nu au reușit să arate că oricare dintre aceste grade conține o mulțime recursiv-enumerabilă. Foarte curând după aceasta, Friedberg și Muchnik au rezolvat independent problema lui Post, stabilind existența de mulțimi recursiv-enumerabile de grad intermediar. Acest rezultat important a deschis un larg studiu al gradelor Turing de mulțimi recursiv-enumerabile care s-a dovedit a poseda o structură foarte complicată și netrivială.

Există un număr nenumărabil de mulțimi care nu sunt recursiv-enumerable, iar cercetările despre gradul Turing al tuturor mulțimilor este central în teoria calculabilității ca cercetare a gradelor Turing recursiv-enumerabile. S-au construit multe grade cu proprietăți speciale: gradele hiperimun-libere unde fiecare funcție calculabilă relativ la acest grad este majorată de o funcție calculabilă (nerelativizată); gradele înalte în raport cu care se poate calcula o funcție f care domină fiecare funcție calculabilă g, în sensul că există o constantă c care depinde de g astfel încât g(x) < f(x) pentru x > c; grade aleatoare ce conțin mulțimi algoritmic aleatoare^⁠(d); grade 1-generice de mulțimi 1-generice; și grade aflate sub problema opririi, cu mulțimi recursive la limită^⁠(d).

Studiul de gradelor Turing arbitrare (nu neapărat recursiv enumerabile) implică studiul saltului Turing. Dată fiind o mulțime A, saltul Turing al lui A este o mulțime de numere naturale ce codifică o soluție pentru problema opririi pentru mașini Turing cu oracolul A. Saltul Turing al oricărei mulțimi este întotdeauna de grad Turing mai mare decât mulțimea, și o teoremă a lui Friedburg arată că orice mulțime care calculează problema opririi poate fi obținută ca salt Turing al unei alte mulțimi. Teorema lui Post stabilește o relație strânsă între operația de salt Turing și ierarhia aritmetică, care este o clasificare a anumitor submulțimi de numere naturale pe baza definibilității lor în aritmetică.

Multe cercetări recente pe tema gradelor Turing s-au concentrat pe structura de ansamblu a mulțimii gradelor Turing și mulțimea gradelor Turing ce conțin mulțimi recursiv enumerabile. O teoremăa lui Shore și Slaman (1999) afirmă că funcția ce asociază un grad x gradului saltului său Turing este definibilă în ordinea parțială a gradelor Turing. Un sondaj recent realizat de Ambos-Spioni și Fejer (2006) oferă o imagine de ansamblu a acestei cercetări și a avansului ei istoric.

Alte reductibilități

O arie de cercetare curentă în teoria calculabilității studiază relațiile de reductibilitate, altele decât reductibilitatea Turing. Post (1944) a introdus mai multe reductibilități tari, numite astfel pentru că ele implică reductibilitatea cu tabela de adevăr. O mașină Turing ce implementează o reductibilitate tare va calcula o funcție totală, indiferent de ce oracol i se prezintă. Reductibilitățile slabe sunt cele în care procesul de reducere ar putea să nu se termine pentru orice oracol; reductibilitatea Turing este un exemplu.

Reductibilități tari sunt:

Reductibilitatea injectivă^⁠(d)

A este reductibilă injectiv (sau 1-reductibilă) la B dacă există o funcție injectivă total calculabilă f astfel încât fiecare n este în A dacă și numai dacă f(n) este în B.

Reductibilitatea neinjectivă^⁠(d)

Aceasta este, în esență, similară cu cea de sus, fără constrângerea ca f să fie injectivă. A este reductibilă neinjectiv (sau m-reductibilă) la B dacă există o funcție total calculabilă f astfel încât un n este în A dacă și numai dacă f(n) este în B.

Reductibilitatea cu tabelă de adevăr^⁠(d)

A este reductibilă cu tabelă de adevăr la B dacă A este Turing reductibilă la B prin intermediul unei mașini Turing cu oracol care calculează o funcție totală, indiferent de oracol. Din cauza faptului că spațiul Cantor este compact, acest lucru este echivalent cu a spune că reducerea prezintă o singură listă de întrebări (în funcție de intrare) simultan oracolului simultan, și după ce află răspunsurile poate produce o ieșire fără a pune întrebări suplimentare, indiferent de răspunsul dat  de oracol la interogarea inițială. S-au studiat mai multe variante de reductibilitate cu tabelă de adevăr.

Direcțiile majore de cercetare asupra reducibilităților tari au fost de a compara teoriile, atât pentru clasa tuturor mulțimilor recursiv-enumerabile, precum și pentru clasa tuturor subgrupurilor de numere naturale. În plus, s-au studiat și relațiile dintre reducibilități. De exemplu, este cunoscut faptul că fiecare grad Turing este fie un grad cu tabelă de adevăr sau este reuniunea a infinit de multe grade cu tabelă de adevăr.

S-au studiat și reductibilitățile mai slabe decât reductibilitatea Turing (adică reducibilitățile care sunt implicate de reductibilitatea Turing). Cele mai cunoscute sunt reductibilitatea aritmetică^⁠(d) și cea hiperaritmetică^⁠(d). Aceste reducibilități sunt strâns legate de definibilitate prin modelul standard al aritmeticii.

Teorema lui Rice și ierarhia aritmetică

Rice a arătat că pentru fiecare clasă trivială C (care conține unele mulțimi r.e., dar nu toate) mulțimea indice E = {e: a e-ea mulțime r.e. W_e este în C} are proprietatea că fie problema opririi^⁠(d), fie complementul acestea este reductibilă neinjectiv la E, adică poate fi mapată folosind o reducere neinjectivă^⁠(d) la E. Dar multe dintre aceste mulțimi indice sunt chiar mai complicate decât problema opririi. Aceste mulțimi pot fi clasificate folosind ierarhia aritmetică^⁠(d). De exemplu, mulțimea indice FIN a clasei tuturor mulțimilor finite este la nivelul Σ₂, mulțimea indice REC a clasei tuturor mulțimilor recursive este la nivelul Σ₃, mulțimea indice COFIN a tuturor mulțimilor cofinite este, de asemenea, la nivelul Σ₃ și mulțimea indice COMP a clasei tuturor mulțimilor Turing-complete Σ₄. Această ierarhie de niveluri este definită inductiv, Σ_n+1 conține doar toate mulțimile care sunt recursiv enumerabile relativ la Σ_n; Σ₁ conține mulțimile recursiv enumerabile. Mulțimile indice date aici sunt chiar complete pentru nivelul lor, adică toate mulțimile de la aceste niveluri pot fi multe-una redusă la indexul dat de seturi.

Matematică inversă

Programul matematică inversă^⁠(d) întreabă care axiome de existență a mulțimilor sunt necesare pentru a demonstra anumite teoreme din matematică în subsisteme de artimetică de ordinul al doilea^⁠(d). Acest studiu a fost inițiat de către Harvey Friedman^⁠(d) și a fost studiat în detaliu de către Stephen Simpson^⁠(d) și alții; Simpson (1999) oferă o discuție detaliată a programului. Axiomele în cauză de existență a  mulțimilor corespund în mod informal unor axiome ce afirmă că mulțimea părților mulțimii numerelor naturale este închisă în raport cu diferite reductibilități. Cea mai slabă astfel de axiomă studiată de matematica inversă este comprehensiunea recursivă, care prevede că mulțimea părților mulțimii numerelor naturale este închisă în raport cu reductibilitatea Turing.

Numărările

O numărare este o enumerare de funcții; are doi parametri, e și x și produce la ieșire valoarea funcției a e-ea pe intrarea x. Numărările pot fi parțial-recursive deși unii membrii ai lor sunt funcții total recursive, adică calculabile. Numărările admisibile^⁠(d) sunt acelea în care pot fi traduse toate celelalte. O numerotare Friedberg (numită după descoperitorul său) este o numerotare injectivă a tuturor funcțiilor parțial-recursive; în mod necesar necesar, ea nu este o numărare admisibilă. Cercetări ulterioare au abordat și numărări de alte clase, cum ar fi clasele de mulțimi recursiv enumerabile. Goncearov a descoperit, de exemplu, o clasă de mulțimi recursiv enumerable pentru care numărările se încadrează în exact două clase în raport cu izomorfismele recursive.

Metoda priorității

Problema lui Post a fost rezolvată cu o metodă numita metoda priorității; o demonstrație ce folosește această metodă se numește argument de prioritate. Această metodă este folosită în principal pentru a construi mulțimi recursiv enumerabile cu proprietăți speciale. Pentru a utiliza această metodă, proprietățile dorite a fi construite sunt despărțite într-o listă infinită de obiective, cunoscut sub numele de cerințe, astfel încât satisfacerea tuturor cerințelor va face ca mulțimea construită să aibă proprietățile dorite. Fiecare cerință este atribuită unui număr natural reprezentând prioritatea cerinței; deci, 0 se atribuie celei mai importante priorități, 1 celei de a doua, și așa mai departe. Mulțimea este apoi construită în etape, la fiecare etapă încercându-se să se satisfacă una sau mai multe cerințe, fie prin adăugarea de numere la mulțime, fie prin excluzând numere din mulțime, astfel încât mulțimea finală să satisfacă cerințele. Se poate întâmpla ca, satisfăcând o cerință, să se încalce o alta; ordinea de prioritate este folosită pentru a hotărî cum să se procedeze în astfel de cazuri.

Argumentele de prioritate au fost folosite pentru a rezolva multe probleme în teoria calculabilității și au fost clasificate într-o ierarhie bazată pe complexitatea lor (Soare 1987). Pentru că argumentele de prioritate complexe pot fi tehnice și greu de urmărit, s-a considerat de dorit să se demonstreze rezultatele fără argumente de prioritate, sau să se vadă dacă rezultatele demonstrate cu argumente de prioritate pot fi demonstrate și altfel. De exemplu, Kummer a publicat o lucrare ce prezenta o demonstrație a existenței numărărilor Friedberg fără a utiliza metoda priorității.

Rețeaua mulțimilor recursiv enumerabile

Atunci când Post a definit noțiunea de mulțime simplă ca o mulțime r.e. al cărui complement infinit nu conține nicio mulțime r.e. infinită, el a început să studieze structura mulțimilor recursiv enumerabile în raport cu operația de incluziune. Această rețea a devenit o structură bine-studiată. Mulțimile recursive pot fi definite în această structură cu ajutorul rezultatului că o mulțime este recursivă dacă și numai dacă și mulțimea și complementul ei sunt recursiv enumerabile. Mulțimile r.e. infinite au întotdeauna submulțimi infinite recursive; dar, pe de altă parte, există mulțimi simple, dar nu au o supramulțime coinfinită recursivă. Post (1944) introdusese deja mulțimile hypersimple și hyperhypersimple; mai târziu, au fost construite mulțimile maximale care sunt mulțimi r.e. astfel încât fiecare supramulțime r.e. este fie o variantă finită a mulțimii maximale date, fie este co-finită. Motivația inițială a lui Post pentru studiul acestei rețele a fost dorința de a găsi o noțiune structurală astfel încât fiecare mulțime care îndeplinește această proprietate să nu fie în gradul Turing al mulțimilor recursive, nici în gradul Turing al problemei opririi. Post nu a găsit o astfel de proprietate și soluția problemei sale aplică în schimb metoda priorității; Harrington și Soare (1991) au găsit în cele din urmă o astfel de proprietate.

Probleme de automorfism

O altă întrebare importantă este existența automorfismelor în structurile teoriei calculabilității. Una dintre aceste structuri este cea a mulțimilor recursiv enumerabile împreună cu incluziunea și cu diferența modulo finită; în această structură, A este sub B dacă și numai dacă diferența B − este finită. Mulțimile maximale^⁠(d) (așa cum sunt definite în paragraful anterior) au proprietatea că acestea nu pot fi automorfe cu mulțimi nemaximale, adică dacă există un automorfism al mulțimilor recursiv enumerabile în structura menționată, atunci fiecărei mulțimi maximale îi corespunde o altă mulțime maximală. Soare (1974) a arătat că și reciproca este valabilă, adică orice două mulțimi maximale sunt automorfe. Deci mulțimile maximale formează o orbită, adică fiecare automorfism conservă maximalitatea și orice două mulțimi maximale sunt transformate una în alta printr-un automorfism. Harrington a dat un alt exemplu de proprietate automorfă: mulțimile creative, mulțimi care sunt echivalente neinjectiv cu problema opririi.

Pe lângă rețeaua mulțimilor recursiv enumerabile, automorfismele sunt studiate și pentru structura gradelor Turing ale tuturor mulțimilor, precum și pentru structura de grade Turing ale mulțimilor r.e.. În ambele cazuri, Cooper susține că a construit automorfisme triviale în care unele grade corespund la alte grade; această construcție nu au fost însă verificată și unii colegi cred că construcția conține erori și că întrebarea dacă există un automorfism trivial de grade Turing este încă una dintre principalele chestiuni nerezolvate în acest domeniu (Slaman și Woodin 1986, Ambos-Spioni și Fejer 2006).

Complexitate Kolmogorov

Domeniul complexității Kolmogorov^⁠(d) și al aleatoriului algoritmic^⁠(d) a fost dezvoltată în deceniile anilor 1960 și 1970 de către Chaitin, Kolmogorov, Levin, Martin-Löf și Solomonoff (numele sunt date aici în ordine alfabetică; o mare parte din cercetare a fost independentă, iar unitatea conceptului de aleatoriu nu era înțeleasă la momentul respectiv). Ideea principală este să se ia în considerare o mașină Turing universală^⁠(d) U și să se măsoare complexitatea unui număr (sau șir de caractere) x ca durata cea mai scurtă a intrării p astfel încât U(p) produce la ieșire x. Această abordare a revoluționat modalitățile anterioare de a determina când o secvență infinită (echivalent, funcția caracteristică a unei submulțimi de numere naturale) este aleatoare și când nu prin invocarea unei noțiunea de aleatoriu pentru obiecte finite. Complexitatea Kolmogorov a devenit nu numai un subiect de studiu independent, ci este aplicată și la alte subiecte, ca un instrument pentru obținerea de demonstrații. Există încă multe probleme în acest domeniu. Din acest motiv, o recentă conferință de cercetare în acest domeniu s-a ținut în ianuarie 2007 și o listă de probleme deschise este menținută de către Joseph Miller și Andre Nies.

Calculul de frecvență

Această ramură a teoriei calculabilității analizează următoarea întrebare: Pentru numerele m și n fixe, cu 0 < m < n, pentru care funcții A se poate calcula pentru orice n intrări distincte x₁, x₂, ..., x_n un tuplu de n numere y₁,y₂,...,y_n astfel încât cel puțin m din ecuațiile O(x_k) = y_k să fie adevărate. Astfel de mulțimi sunt cunoscute ca mulțimi (m, n)-recursive. Primul rezultat important în această ramură a teoriei calculabilității este rezultatul lui Trakhtenbrot că o mulțime este calculabilă dacă este (m, n)-recursivă pentru m, n cu 2m > n. Pe de altă parte, mulțimile semi-membership^⁠(d) ale lui Jockusch (care erau deja cunoscute informal înainte de a fi prezentate de Jockusch în 1968) sunt exemple de mulțimi care sunt (m, n)-recursive dacă și numai dacă 2m < n + 1. Există un număr nenumărabil de astfel de mulțimi, dar și unele mulțimi de acest tip recursiv enumerabile, dar necalculabile. Mai târziu, Degtev a stabilit o ierarhie a mulțimilor recursiv enumerabile care sunt (1, n + 1)-recursive dar nu (1, n)-recursive. După o lungă fază de cercetare de către oameni de știință ruși, acest subiect a fost repopularizat în Occident de teza lui Beigel a interogărilor mărginite, care lega calculul de frecvență de calculul reductibilităților mărginite mai sus-menționate și de alte noțiuni. Unul dintre principalele rezultate a fost teoria cardinalității a lui Kummer, care afirmă că o mulțime A este calculabilă dacă și numai dacă există un n astfel încât un algoritm oarecare enumeră pentru fiecare tuplu de n numere diferite până la n variante posibile de cardinalitate a acestei mulțimi cu n numere intersectată cu A; aceste variante trebuie să conțină cardinalitatea adevărată, dar și cel puțin una falsă.

Inferență inductivă

Aceasta este o ramură a teoriei învățării legată de teoria calculabilității. Este bazată pe modelul de învățare al lui Gold în limita din 1967 și a dezvoltat de atunci din ce în ce mai multe modele de învățare. În general, scenariul este următorul: Având în vedere o clasă S de funcții calculabile, există un sistem de învățare (recursiv funcțional), care emite pentru orice intrare de forma (f(0),f(1),...,f(n)) o ipoteză. Un sistem de învățare M învață o funcție f dacă aproape toate ipotezele sunt cu același indice e al lui f în raport cu o numărare acceptabilă convenită anterior a tuturor funcțiilor calculabile; M învață S dacă M învață fiecare f din S. Rezultatele de bază sunt că toate clasele recursiv enumerabile de funcții sunt învățabile, în timp ce clasa REC a tuturor funcțiilor calculabile nu este învățabilă. Au fost analizate multe modele asociate, iar învățarea claselor de mulțimi recursiv enumerabile din date pozitive este un subiect studiat de la articolul inițial al lui Gold din 1967 încoace.

Generalizări ale calculabilității Turing

Teoria calculabilității cuprinde studiul unor noțiuni generalizate din acest domeniu, cum ar fi reductibilitatea aritmetică^⁠(d), reductibilitatea hyperarithmetică^⁠(d) și teoria α-recursivității^⁠(d), așa cum descrie Sacks (1990). Aceste noțiuni generalizate includ reductibilități care nu pot fi executate de mașini Turing dar cu toate acestea sunt generalizări naturale ale reductibilității Turing. Aceste studii includ abordări de a investiga ierarhia analitică^⁠(d) ce diferă de ierarhia aritmetică^⁠(d) prin aceea că permite cuantificarea peste mulțimi de numere naturale, în plus față de cuantificarea pe numere individuale. Aceste zone sunt legate de teoriile bunelor-ordonări și arborilor; de exemplu mulțimea tuturor indicilor arborilor recursivi (nebinari) fără ramuri infinite este completă pentru nivelul $\Pi _{1}^{1}$ de ierarhie analitică. Atât reductibilitatea Turing cât și reductibilitatea hyperarithmetică sunt importante în domeniul teoriei mulțimilor efectiv descriptive^⁠(d). Noțiune și mai generală de grade de constructibilitate este studiată în teoria mulțimilor.

Teoria continuă a calculabilității

Teoria calculabilității pentru calculul numeric este bine dezvoltată. Teoria calculabilității este mai puțin dezvoltată pentru calculul analogic care apare în calculatoarele analogice, în prelucrarea semnalelor analogice^⁠(d), electronica analogică^⁠(d), rețele neurale și teoria controlului^⁠(d) în timp continuu, modelate prin ecuații diferențiale și sisteme dinamice continue (Orponen 1997; Moore, 1996).

Relațiile dintre definibilitate, demonstrație și calculabilitate

Există relații strânse între gradul Turing al unei mulțimi de numere naturale și dificultatea (în termeni de ierarhie aritmetică^⁠(d)) de definire a acelei mulțimi, folosind o formulă de ordinul întâi^⁠(d). O astfel de relație este precizată de teorema lui Post^⁠(d). O relație mai slabă a fost demonstrată de Kurt Gödel în demonstrațiile teoremei sale de completitudine^⁠(d) și incompletitudine^⁠(d). Demonstrațiile lui Gödel arată că mulțimea de consecințe logice a unei teorii de ordinul întâi este o mulțime recursiv enumerabilă^⁠(d), și că, dacă teoria este suficient de puternică această mulțime va fi necalculabilă. În mod similar, teorema indefinibilității a lui Tarski^⁠(d) poate fi interpretată atât în termeni de definibilitate cât și în termeni de calculabilitate.

Teoria calculabilității este legată și de aritmetica de ordinul al doilea, o teorie formală a numerelor naturale și a mulțimilor de numere naturale. Faptul că anumite mulțimi sunt calculabile sau relativ calculabile implică de multe ori faptul că aceste mulțimi pot fi definite în subsisteme slabe ale aritmeticii de ordinul al doilea. Programul matematicii inverse utilizează aceste subsisteme pentru a măsura necalculabilitatea inerentă a unor teoreme matematice bine cunoscute. Simpson (1999) discută mai multe aspecte de aritmetică de ordinul al doilea și matematică inversă.

Domeniul teoriei demonstrației^⁠(d) include studiul aritmeticii de ordinul al doilea și a aritmeticii Peano^⁠(d), precum și teorii formale de numere naturale mai slabe decât aritmetica Peano. O metodă de clasificare a puterii acestor sisteme slabe este prin caracterizatarea funcțiilor calculabile pe care sistemul le poate demonstra că sunt totale^⁠(d) (a se vedea Fairtlough și Wainer (1998)). De exemplu, în aritmetica primitiv recursivă^⁠(d) orice funcție calculabilă care se poate demonstra că este totală este de fapt primitiv recursivă^⁠(d), în timp ce aritmetica Peano^⁠(d) demonstrează că funcții ca funcția Ackermann^⁠(d), care nu sunt primitiv recursive, sunt totale. Nu fiecare funcție totală calculabilă este demonstrabilă a fi totală în aritmetica Peano dar un exemplu de astfel de funcție este dat de teorema lui Goodstein^⁠(d).

Numele domeniului

Domeniul din logica matematică ce se ocupă cu calculabilitatea și generalizările ei a fost numit „teoria recursivității” la începuturile sale. Robert I. Soare^⁠(d), un renumit cercetător în domeniu, a propus (Soare 1996) ca domeniul să se numească în schimb „teoria calculabilității”. El susține că terminologia lui Turing bazată pe cuvântul „calculabil” este mai naturală și mai larg înțeleasă decât terminologia folosind cuvântul „recursiv”, introdus de Kleene. Mulți cercetători contemporani au început să folosească această nouă terminologie. Acești cercetători utilizează și terminologia funcție parțial calculabilă și mulțime enumerabil calculabilă în loc de funcție parțial recursivă și mulțime recursiv enumerabilă (r.e.). Nu toți cercetătorii au fost însă convinși, după cum au explicat Fortnow și Simpson. Unii comentatori susțin că atât numele de teoria recursivității cât și cel de teoria calculabilității nu reușesc să transmită că cele mai multe dintre obiectele studiate în teoria calculabilității nu sunt calculabile.

Rogers (1967) a sugerat ca o proprietatea-cheie a teoriei calculabilității este faptul că rezultatele și structurile sale ar trebui să fie invariante la bijecții calculabile pe mulțimea numerelor naturale (această sugestie se bazează pe ideile programului Erlangen din geometrie). Ideea este că o bijecție calculabilă doar schimbă denumirea numerelor dintr-o mulțime, și nu indică vreo structură în mulțime, așa cum o rotație a planului euclidian nu schimba niciun aspect geometric al liniilor trasate pe el. Deoarece orice două mulțimi infinite calculabile sunt legate printr-o bijecție calculabilă, această propunere identifică toate mulțimile infinite calculabile (mulțimile finite calculabile sunt considerate caz banal). Potrivit lui Rogers, mulțimile de interes din teoria recursivității sunt mulțimile necalculabile, împărțite în clase de echivalență de bijecțiile calculabile ale numerelor naturale.

Organizații profesionale

Principala organizație profesională pentru teoria recursivității este cea Association for Symbolic Logic^⁠(d), care susține mai multe conferințe de cercetare în fiecare an. Asociația de cercetare interdisciplinară Computability in Europe^⁠(d) (CiE) organizează și ea o serie de conferințe anuale.

Bibliografie

La nivel de ciclu de diplomă/licență

• S. B. Cooper, 2004. Computability Teorie, Chapman & Hall/CRC. ISBN: 1-58488-237-91-58488-237-9
• N. Cutland, 1980. Computability, O introducere în teoria funcțiilor recursive, Cambridge University Press. ISBN: 0-521-29465-70-521-29465-7
• Y. Matiyasevich, 1993. Hilbert a Zecea Problema, MIT Press. ISBN: 0-262-13295-80-262-13295-8

Texte avansate

• S. Jain, D. Osherson, J. Royer and A. Sharma, 1999. Systems that learn, an introduction to learning theory, second edition, Bradford Book. ISBN: 0-262-10077-00-262-10077-0
• S. Kleene, 1952. Introduction to Metamathematics, North-Holland (a 11-a tipărire; la a 6-a s-au adăugat comentarii). ISBN: 0-7204-2103-90-7204-2103-9
• M. Lerman, 1983. Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag. ISBN: 3-540-12155-23-540-12155-2.
• Andre Nies, 2009. Computability and Randomness, Oxford University Press, 447 pages. ISBN: 978-0-19-923076-1978-0-19-923076-1.
• P. Odifreddi, 1989. Classical Recursion Theory, North-Holland. ISBN: 0-444-87295-70-444-87295-7
• P. Odifreddi, 1999. Classical Recursion Theory, Volume II, Elsevier. ISBN: 0-444-50205-X0-444-50205-X
• H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN: 0-262-68052-10-262-68052-1 (paperback), ISBN: 0-07-053522-10-07-053522-1
• G Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN: 3-540-19305-73-540-19305-7
• S. G. Simpson, 1999. Subsystems of Second Order Arithmetic, Springer-Verlag. ISBN: 3-540-64882-83-540-64882-8
• R. I. Soare, 1987. Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag. ISBN: 0-387-15299-70-387-15299-7.

Articole și colecții de studiu

• K. Ambos-Spies and P. Fejer, 2006. "Degrees of Unsolvability." Pretipărire nepublicată.
• H. Enderton, 1977. "Elements of Recursion Theory." Handbook of Mathematical Logic, editată de  J. Barwise, North-Holland (1977), pp. 527–566. ISBN: 0-7204-2285-X0-7204-2285-X
• Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, 1998. Handbook of Recursive Mathematics, North-Holland (1998). ISBN: 0-7204-2285-X0-7204-2285-X
• M. Fairtlough and S. Wainer, 1998. "Hierarchies of Provably Recursive Functions". In Handbook of Proof Theory, edited by S. Buss, Elsevier (1998).
• R. I. Soare, 1996. Computability and recursion, Bulletin of Symbolic Logic v. 2 pp. 284–321.

Articole și colecții de cercetare

• Burgin, M. and Klinger, A. "Experience, Generations, and Limits in Machine Learning." Theoretical Computer Science v. 317, No. 1/3, 2004, pp. 71–91
• A. Church, 1936a. "An unsolvable problem of elementary number theory." American Journal of Mathematics v. 58, pp. 345–363. Retipărit în "The Undecidable", M. Davis ed., 1965.
• A. Church, 1936b. "A note on the Entscheidungsproblem." Journal of Symbolic Logic v. 1, n. 1, and v. 3, n. 3. Retipărit în "The Undecidable", M. Davis ed., 1965.
• M. Davis, ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN: 0-486-43228-90-486-43228-9
• R. M. Friedberg, 1958. "Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition." The Journal of Symbolic Logic, v. 23, pp. 309–316.
• Gold, E. Mark (1967), Language Identification in the Limit (PDF), 10, Information and Computation^⁠(d), pp. 447–474  [1] Arhivat în 25 ianuarie 2009, la Wayback Machine.
• L. Harrington and R. I. Soare, 1991. "Post's Program and incomplete recursively enumerable sets", Proceedings of the National Academy of Sciences of the USA, volumul 88, paginile 10242—10246.
• C. Jockusch jr, "Semirecursive sets and positive reducibility", Trans. Amer. Math. Soc. 137 (1968) 420-436
• S. C. Kleene și E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability." Annals of Mathematics v. 2 n. 59, 379–407.
• Moore, C. (1996). „Recursion theory on the reals and continuous-time computation”. Theoretical Computer Science. doi:10.1016/0304-3975(95)00248-0. 
• J. Myhill, 1956. "The lattice of recursively enumerable sets." The Journal of Symbolic Logic, v. 21, pp. 215–220.
• Orponen, P. (1997). „A survey of continuous-time computation theory”. Advances in algorithms, languages, and complexity. 
• E. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, volume 50, pages 284–316.
• E. Post, 1947. "Recursive unsolvability of a problem of Thue." Journal of Symbolic Logic v. 12, pp. 1–11. Reprinted in "The Undecidable", M. Davis ed., 1965.
• Shore, Richard A.; Slaman, Theodore A. (1999), „Defining the Turing jump” (PDF), Mathematical Research Letters, 6: 711–722, doi:10.4310/mrl.1999.v6.n6.a10, ISSN 1073-2780 
• T. Slaman and W. H. Woodin, 1986. "Definability in the Turing degrees." Illinois J. Math. v. 30 n. 2, pp. 320–334.
• R. I. Soare, 1974. "Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets." Annals of Mathematics, v. 100, pp. 80–120.
• A. Turing, 1937. "On computable numbers, with an application to the Entscheidungsproblem." Proceedings of the London Mathematics Society, ser. 2 v. 42, pp. 230–265. Corecturi ibid. v. 43 (1937) pp. 544–546. Reprinted in "The Undecidable", M. Davis ed., 1965. PDF from comlab.ox.ac.uk
• A. Turing, 1939. "Systems of logic based on ordinals." Proceedings of the London Mathematics Society, ser. 2 v. 45, pp. 161–228. Retipărit în "The Undecidable", M. Davis ed., 1965.