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 și al . Domeniul s-a extins, incluzând studiul calculabilității și definibilității generalizate. În aceste domenii, teoria calculabilității se suprapune cu și .
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 ș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.Multe din aceste articole fundamentale sunt adunate în The Undecidable (1965) editată de .
Rezultatele fundamentale obținute de cercetători au stabilit Turing-calculabilitatea 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ă. 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).Lucrarea completă se poate găsi la paginile 150ff (cu comentariile lui Charles Parsons la 144ff) în Feferman et al. redactori 1990 Kurt Gödel Volume II Publications 1938-1974, Oxford University Press, New York, . Împreună cu definiția calculului efectiv au venit și primele demonstrații că există probleme în matematică, ce nu pot fi î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, și au arătat independent în 1950 că 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, a demonstrat (folosind rezultatele ) , care afirmă că nu are soluție efectivă; este vorba de problema dacă există o procedură eficientă de a decide dacă o 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 (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ă 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 care au aceeași putere de calcul ca și mașina Turing; de exemplu 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ție parțial recursivă (care poate 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 , 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 , 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 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, au două proprietăți în comun: Sunt , și Fiecare poate fi tradusă în oricare alta printr-o . 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 , ș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 . 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ă.