b'\n_START_ARTICLE_\nTeoria calculabilit\xc4\x83\xc8\x9bii\n_START_PARAGRAPH_\nTeoria calculabilit\xc4\x83\xc8\x9bii\xc2\xa0este o ramur\xc4\x83 a\xc2\xa0logicii matematice, a\xc2\xa0informaticii\xc2\xa0\xc8\x99i a\xc2\xa0teoriei computa\xc8\x9biei, care \xc3\xae\xc8\x99i are originea \xc3\xaen anii 1930, cu studiul func\xc8\x9biilor calculabile\xc2\xa0\xc8\x99i al\xc2\xa0gradelor Turing. Domeniul s-a extins, incluz\xc3\xa2nd studiul calculabilit\xc4\x83\xc8\x9bii \xc8\x99i definibilit\xc4\x83\xc8\x9bii generalizate. \xc3\x8en aceste domenii, teoria calculabilit\xc4\x83\xc8\x9bii se suprapune cu teoria demonstra\xc8\x9biilor\xc2\xa0\xc8\x99i teoria descriptiv\xc4\x83 a mul\xc8\x9bimilor._NEWLINE_Chestiunile de baz\xc4\x83 abordate de teoria calculabilit\xc4\x83\xc8\x9bii sunt \xe2\x80\x9ece \xc3\xaenseamn\xc4\x83 c\xc4\x83 o func\xc8\x9bie de\xc2\xa0numere naturale este calculabil\xc4\x83?\xe2\x80\x9d \xc8\x99i \xe2\x80\x9ecum pot fi clasificate func\xc8\x9biile necalculabile \xc3\xaentr-o ierarhie \xc3\xaen func\xc8\x9bie de nivelul lor de necalculabilitate?\xe2\x80\x9d. R\xc4\x83spunsurile la aceste \xc3\xaentreb\xc4\x83ri au condus la o bogat\xc4\x83 teorie care este \xc3\xaenc\xc4\x83 activ cercetat\xc4\x83._NEWLINE_Teoreticienii calculabilit\xc4\x83\xc8\x9bii din logica matematic\xc4\x83 studiaz\xc4\x83 adesea teoria calculabilit\xc4\x83\xc8\x9bii relative, no\xc8\x9biunile de reductibilitate structurile pe grade descrise \xc3\xaen acest articol. Acest lucru contrasteaz\xc4\x83 cu teoria\xc2\xa0ierarhiilor subrecursive, cu\xc2\xa0metodele formale \xc8\x99i cu\xc2\xa0limbajele formale, care sunt comune \xc3\xaen studiul de teoriei calculabilit\xc4\x83\xc8\x9bii \xc3\xaen informatic\xc4\x83. Exist\xc4\x83 \xc3\xaens\xc4\x83 o suprapunere considerabil\xc4\x83 de cuno\xc8\x99tin\xc8\x9be \xc8\x99i metode \xc3\xaentre aceste dou\xc4\x83 comunit\xc4\x83\xc8\x9bi de cercetare \xc8\x99i nu se poate trasa o linie ferm\xc4\x83 de demarca\xc8\x9bie \xc3\xaentre ele.\n_START_SECTION_\nCalculabilitate Turing\n_START_PARAGRAPH_\nPrincipala form\xc4\x83 de calculabilitate studiat\xc4\x83 \xc3\xaen teoria calculabilit\xc4\x83\xc8\x9bii este cea introdus\xc4\x83 de Turing (1936). O mul\xc8\x9bime de numere naturale este declarat\xc4\x83 a fi\xc2\xa0mul\xc8\x9bime calculabil\xc4\x83\xc2\xa0(numit\xc4\x83 \xc8\x99i\xc2\xa0decidabil\xc4\x83, recursiv\xc4\x83, sau Turing-calculabil\xc4\x83) dac\xc4\x83 exist\xc4\x83 o ma\xc8\x99in\xc4\x83 Turing care, dat fiind un num\xc4\x83r n, se opre\xc8\x99te cu ie\xc8\x99irea 1 dac\xc4\x83 n este \xc3\xaen mul\xc8\x9bime \xc8\x99i se opre\xc8\x99te cu ie\xc8\x99irea 0 daca n nu este \xc3\xaen mul\xc8\x9bime. O func\xc8\x9bie f definit\xc4\x83 pe mul\xc8\x9bimea numerelor naturale cu valori tot \xc3\xaen ea este o func\xc8\x9bie\xc2\xa0recursiv\xc4\x83 sau (Turing) calculabil\xc4\x83\xc2\xa0dac\xc4\x83 exist\xc4\x83 o ma\xc8\x99in\xc4\x83 Turing care, c\xc3\xa2nd i se pune la intrare n, se opre\xc8\x99te \xc8\x99i \xc3\xaentoarce la ie\xc8\x99ire f(n). Utilizarea ma\xc8\x99inii Turing aici nu este necesar\xc4\x83; exist\xc4\x83 multe alte modele de calcul care au aceea\xc8\x99i putere de calcul ca \xc8\x99i ma\xc8\x99ina Turing; de exemplu func\xc8\x9biile \xce\xbc-recursive ob\xc8\x9binute din operatorul primitiv de recursivitate \xc8\x99i operatorul \xce\xbc._NEWLINE_Terminologia pentru func\xc8\x9bii \xc8\x99i mul\xc8\x9bimi recursive nu este complet standardizat\xc4\x83. Definirea \xc3\xaen termeni de func\xc8\x9bii \xce\xbc-recursive, precum \xc8\x99i o alt\xc4\x83 defini\xc8\x9bie a func\xc8\x9biilor\xc2\xa0rekursive dat\xc4\x83 de G\xc3\xb6del a condus la numele tradi\xc8\x9bional de\xc2\xa0recursive pentru mul\xc8\x9bimi \xc8\x99i func\xc8\x9bii calculabile de c\xc4\x83tre o ma\xc8\x99in\xc4\x83 Turing. Cuv\xc3\xa2ntul decidabil\xc2\xa0provine de la cuv\xc3\xa2ntul german Entscheidungsproblem (problema deciziei) care a fost folosit \xc3\xaen primele lucr\xc4\x83ri ale lui Turing \xc8\x99i ale altora. \xc3\x8en utilizarea contemporan\xc4\x83, termenul de \xe2\x80\x9efunc\xc8\x9bie calculabil\xc4\x83\xe2\x80\x9d are mai multe defini\xc8\x9bii: conform Cutland (1980), este o func\xc8\x9biei par\xc8\x9bial recursiv\xc4\x83 (care pot fi nedefinit\xc4\x83 pentru unele intr\xc4\x83ri), \xc3\xaen timp ce \xc3\xaen conformitate cu Soare (1987) este una total recursiv\xc4\x83 (echivalent, func\xc8\x9bie general recursiv\xc4\x83). Acest articol cum urmeaz\xc4\x83 aceast\xc4\x83 din urm\xc4\x83 conven\xc8\x9bie. Soare (1996) ofer\xc4\x83 comentarii suplimentare cu privire la terminologie._NEWLINE_Nu toate mul\xc8\x9bimile de numere naturale sunt calculabile. Problema opririi, care este o mul\xc8\x9bime de (descrieri de) ma\xc8\x99ini Turing care se opresc la intrarea 0, este un exemplu bine-cunoscut de mul\xc8\x9bime necalculabil\xc4\x83. Existen\xc8\x9ba a numeroase mul\xc8\x9bimi necalculabile rezult\xc4\x83 din faptul c\xc4\x83 exist\xc4\x83 doar un\xc2\xa0num\xc4\x83r num\xc4\x83rabil\xc2\xa0de ma\xc8\x99ini Turing, \xc8\x99i, astfel, numai un num\xc4\x83r num\xc4\x83rabil de mul\xc8\x9bimi calculabile, dar exist\xc4\x83 un\xc2\xa0num\xc4\x83r nenum\xc4\x83rabil\xc2\xa0de mul\xc8\x9bimi de numere naturale._NEWLINE_De\xc8\x99i problema opririi nu este calculabil\xc4\x83, se poate simula execu\xc8\x9bia programului \xc8\x99i se poate produce o list\xc4\x83 infinit\xc4\x83 de programe care se opresc. Astfel, problema opririi este un exemplu de\xc2\xa0mul\xc8\x9bime recursiv enumerabil\xc4\x83, adic\xc4\x83 o mul\xc8\x9bime ale c\xc4\x83rei elemente pot fi enumerate de c\xc4\x83tre o ma\xc8\x99in\xc4\x83 Turing (al\xc8\x9bi termeni pentru \xe2\x80\x9erecursiv enumerabil\xc4\x83\xe2\x80\x9d ar fi \xc8\x99i\xc2\xa0calculabil enumerabil\xc4\x83\xc2\xa0\xc8\x99i semidecidabil\xc4\x83). Echivalent, o mul\xc8\x9bime este recursiv enumerabil\xc4\x83 dac\xc4\x83 \xc8\x99i numai dac\xc4\x83 este codomeniul unei func\xc8\x9bii calculabile. Mul\xc8\x9bimile recursiv enumerabile, de\xc8\x99i nu sunt decidabile \xc3\xaen general, au fost studiate \xc3\xaen detaliu \xc3\xaen teoria calculabilit\xc4\x83\xc8\x9bii.\n_START_SECTION_\nDomenii de cercetare\n_START_PARAGRAPH_\n\xc3\x8encep\xc3\xa2nd cu teoria mul\xc8\x9bimilor recursive \xc8\x99i cu func\xc8\x9biile descrise mai sus, domeniul teoriei calculabilit\xc4\x83\xc8\x9bii s-a extins \xc8\x99i include ast\xc4\x83zi studiul multor subiecte str\xc3\xa2ns legate. Acestea nu sunt domenii independente de cercetare: fiecare dintre aceste domenii atrag idei \xc8\x99i rezultate de la celelalte, \xc8\x99i majoritatea teoreticienilor calculabilit\xc4\x83\xc8\x9bii sunt familiariza\xc8\x9bi cu majoritatea lor.\n_START_SECTION_\nTeorema lui Rice \xc8\x99i ierarhia aritmetic\xc4\x83\n_START_PARAGRAPH_\nRice a ar\xc4\x83tat c\xc4\x83 pentru fiecare clas\xc4\x83 trivial\xc4\x83\xc2\xa0C (care con\xc8\x9bine unele mul\xc8\x9bimi r.e., dar nu toate) mul\xc8\x9bimea indice\xc2\xa0E = {e: a\xc2\xa0e-ea mul\xc8\x9bime r.e.\xc2\xa0W\xe2\x82\x91 este \xc3\xaen C} are proprietatea c\xc4\x83 fie problema opririi,\xc2\xa0fie complementul acestea este reductibil\xc4\x83 neinjectiv la E, adic\xc4\x83 poate fi mapat\xc4\x83 folosind o\xc2\xa0reducere neinjectiv\xc4\x83\xc2\xa0la E. Dar multe dintre aceste mul\xc8\x9bimi indice sunt chiar mai complicate dec\xc3\xa2t problema opririi. Aceste mul\xc8\x9bimi pot fi clasificate folosind ierarhia aritmetic\xc4\x83. De exemplu, mul\xc8\x9bimea indice FIN a clasei tuturor mul\xc8\x9bimilor finite este la nivelul \xce\xa3\xe2\x82\x82, mul\xc8\x9bimea indice REC a clasei tuturor mul\xc8\x9bimilor recursive este la nivelul \xce\xa3\xe2\x82\x83, mul\xc8\x9bimea indice COFIN a tuturor mul\xc8\x9bimilor cofinite este, de asemenea, la nivelul \xce\xa3\xe2\x82\x83 \xc8\x99i mul\xc8\x9bimea indice COMP a clasei tuturor mul\xc8\x9bimilor Turing-complete \xce\xa3\xe2\x82\x84. Aceast\xc4\x83 ierarhie de niveluri este definit\xc4\x83 inductiv, \xce\xa3\xe2\x82\x99\xe2\x82\x8a\xe2\x82\x81 con\xc8\x9bine doar toate mul\xc8\x9bimile care sunt recursiv enumerabile relativ la \xce\xa3\xe2\x82\x99; \xce\xa3\xe2\x82\x81 con\xc8\x9bine mul\xc8\x9bimile recursiv enumerabile. Mul\xc8\x9bimile indice\xc2\xa0date aici sunt chiar complete pentru nivelul lor, adic\xc4\x83 toate mul\xc8\x9bimile de la aceste niveluri pot fi multe-una redus\xc4\x83 la indexul dat de seturi.\n_START_SECTION_\nReverse matematic\xc4\x83\n_START_PARAGRAPH_\nProgramul matematic\xc4\x83 invers\xc4\x83 \xc3\xaentreab\xc4\x83 care axiome de existen\xc8\x9b\xc4\x83 a mul\xc8\x9bimilor sunt necesare pentru a demonstra anumite teoreme din matematic\xc4\x83 \xc3\xaen subsisteme de artimetic\xc4\x83 de ordinul al doilea. Acest studiu a fost ini\xc8\x9biat de c\xc4\x83tre Harvey Friedman \xc8\x99i a fost studiat \xc3\xaen detaliu de c\xc4\x83tre Stephen Simpson \xc8\x99i al\xc8\x9bii; Simpson (1999) ofer\xc4\x83 o discu\xc8\x9bie detaliat\xc4\x83 a programului. Axiomele \xc3\xaen cauz\xc4\x83 de existen\xc8\x9b\xc4\x83 a \xc2\xa0mul\xc8\x9bimilor corespund \xc3\xaen mod informal unor axiome ce afirm\xc4\x83 c\xc4\x83 mul\xc8\x9bimea p\xc4\x83r\xc8\x9bilor mul\xc8\x9bimii numerelor naturale este \xc3\xaenchis\xc4\x83 \xc3\xaen raport cu diferite reductibilit\xc4\x83\xc8\x9bi. Cea mai slab\xc4\x83 astfel de axiom\xc4\x83 studiat\xc4\x83 de matematica invers\xc4\x83 este comprehensiunea recursiv\xc4\x83, care prevede c\xc4\x83 mul\xc8\x9bimea p\xc4\x83r\xc8\x9bilor mul\xc8\x9bimii numerelor naturale este \xc3\xaenchis\xc4\x83 \xc3\xaen raport cu reductibilitatea Turing.\n_START_SECTION_\nNum\xc4\x83r\xc4\x83rile\n_START_PARAGRAPH_\nO num\xc4\x83rare este o enumerare de func\xc8\x9bii; are doi parametri, e \xc8\x99i x \xc8\x99i produce la ie\xc8\x99ire valoarea func\xc8\x9biei a\xc2\xa0e-ea pe intrarea\xc2\xa0x. Num\xc4\x83r\xc4\x83rile pot fi par\xc8\x9bial-recursive de\xc8\x99i unii membrii ai lor sunt func\xc8\x9bii total recursive, adic\xc4\x83 calculabile. Num\xc4\x83r\xc4\x83rile admisibile\xc2\xa0sunt acelea \xc3\xaen care pot fi traduse toate celelalte. O numerotare Friedberg\xc2\xa0(numit\xc4\x83 dup\xc4\x83 descoperitorul s\xc4\x83u) este o numerotare injectiv\xc4\x83 a tuturor func\xc8\x9biilor par\xc8\x9bial-recursive; \xc3\xaen mod necesar necesar, ea nu este o num\xc4\x83rare admisibil\xc4\x83. Cercet\xc4\x83ri ulterioare au abordat \xc8\x99i num\xc4\x83r\xc4\x83ri de alte clase, cum ar fi clasele de mul\xc8\x9bimi recursiv enumerabile. Goncearov a descoperit, de exemplu, o clas\xc4\x83 de mul\xc8\x9bimi recursiv enumerable pentru care num\xc4\x83r\xc4\x83rile se \xc3\xaencadreaz\xc4\x83 \xc3\xaen exact dou\xc4\x83 clase \xc3\xaen raport cu izomorfismele recursive.\n_START_SECTION_\nMetoda priorit\xc4\x83\xc8\x9bii\n_START_PARAGRAPH_\nProblema lui Post a fost rezolvat\xc4\x83 cu o metod\xc4\x83 numita metoda priorit\xc4\x83\xc8\x9bii; o demonstra\xc8\x9bie ce folose\xc8\x99te aceast\xc4\x83 metod\xc4\x83 se nume\xc8\x99te o\xc2\xa0argument de prioritate. Aceast\xc4\x83 metod\xc4\x83 este folosit\xc4\x83 \xc3\xaen principal pentru a construi mul\xc8\x9bimi recursiv enumerabile cu propriet\xc4\x83\xc8\x9bi speciale. Pentru a utiliza aceast\xc4\x83 metod\xc4\x83, propriet\xc4\x83\xc8\x9bile dorite a fi construite sunt desp\xc4\x83r\xc8\x9bite \xc3\xaentr-o list\xc4\x83 infinit\xc4\x83 de obiective, cunoscut sub numele de cerin\xc8\x9be, astfel \xc3\xaenc\xc3\xa2t satisfacerea tuturor cerin\xc8\x9belor va face ca mul\xc8\x9bimea construit\xc4\x83 s\xc4\x83 aib\xc4\x83 propriet\xc4\x83\xc8\x9bile dorite. Fiecare cerin\xc8\x9b\xc4\x83 este atribuit\xc4\x83 unui num\xc4\x83r natural reprezent\xc3\xa2nd prioritatea cerin\xc8\x9bei; deci, 0 se atribuie celei mai importante priorit\xc4\x83\xc8\x9bi, 1 celei de a doua, \xc8\x99i a\xc8\x99a mai departe. Mul\xc8\x9bimea este apoi construit\xc4\x83 \xc3\xaen etape, la fiecare etap\xc4\x83 \xc3\xaencerc\xc3\xa2ndu-se s\xc4\x83 se satisfac\xc4\x83 una sau mai multe cerin\xc8\x9be, fie prin ad\xc4\x83ugarea de numere la mul\xc8\x9bime, fie prin excluz\xc3\xa2nd numere din mul\xc8\x9bime, astfel \xc3\xaenc\xc3\xa2t mul\xc8\x9bimea final\xc4\x83 s\xc4\x83 satisfac\xc4\x83 cerin\xc8\x9bele. Se poate \xc3\xaent\xc3\xa2mpla ca, satisf\xc4\x83c\xc3\xa2nd o cerin\xc8\x9b\xc4\x83, s\xc4\x83 se \xc3\xaencalce o alta; ordinea de prioritate este folosit\xc4\x83 pentru a hot\xc4\x83r\xc3\xae cum s\xc4\x83 se procedeze \xc3\xaen astfel de cazuri._NEWLINE_Argumentele de prioritate au fost folosite pentru a rezolva multe probleme \xc3\xaen teoria calculabilit\xc4\x83\xc8\x9bii \xc8\x99i au fost clasificate \xc3\xaentr-o ierarhie bazat\xc4\x83 pe complexitatea lor (Soare 1987). Pentru c\xc4\x83 argumentele de prioritate complexe pot fi tehnice \xc8\x99i greu de urm\xc4\x83rit, s-a considerat de dorit s\xc4\x83 se demonstreze rezultatele f\xc4\x83r\xc4\x83 argumente de prioritate, sau s\xc4\x83 se vad\xc4\x83 dac\xc4\x83 rezultatele demonstrate cu argumente de prioritate pot fi demonstrate \xc8\x99i altfel. De exemplu, Kummer a publicat o lucrare ce prezenta o demonstra\xc8\x9bie a existen\xc8\x9bei num\xc4\x83r\xc4\x83rilor Friedberg f\xc4\x83r\xc4\x83 a utiliza metoda priorit\xc4\x83\xc8\x9bii.\n_START_SECTION_\nRe\xc8\x9beaua mul\xc8\x9bimilor recursiv enumerabile\n_START_PARAGRAPH_\nAtunci c\xc3\xa2nd Post a definit no\xc8\x9biunea de mul\xc8\x9bime simpl\xc4\x83 ca o mul\xc8\x9bime r.e. al c\xc4\x83rui complement infinit nu con\xc8\x9bine nicio mul\xc8\x9bime r.e. infinit\xc4\x83, el a \xc3\xaenceput s\xc4\x83 studieze structura mul\xc8\x9bimilor recursiv enumerabile \xc3\xaen raport cu opera\xc8\x9bia de incluziune. Aceast\xc4\x83 re\xc8\x9bea a devenit o structur\xc4\x83 bine-studiat\xc4\x83. Mul\xc8\x9bimile recursive pot fi definite \xc3\xaen aceast\xc4\x83 structur\xc4\x83 cu ajutorul rezultatului c\xc4\x83 o mul\xc8\x9bime este recursiv\xc4\x83 dac\xc4\x83 \xc8\x99i numai dac\xc4\x83 \xc8\x99i mul\xc8\x9bimea \xc8\x99i complementul ei sunt recursiv enumerabile. Mul\xc8\x9bimile\xc2\xa0r.e. infinite au \xc3\xaentotdeauna submul\xc8\x9bimi infinite recursive; dar, pe de alt\xc4\x83 parte, exist\xc4\x83 mul\xc8\x9bimi simple, dar nu au o supramul\xc8\x9bime coinfinit\xc4\x83 recursiv\xc4\x83. Post (1944) introdusese deja mul\xc8\x9bimile hypersimple \xc8\x99i hyperhypersimple; mai t\xc3\xa2rziu, au fost construite mul\xc8\x9bimile maximale care sunt mul\xc8\x9bimi r.e. astfel \xc3\xaenc\xc3\xa2t fiecare supramul\xc8\x9bime r.e. este fie o variant\xc4\x83 finit\xc4\x83 a mul\xc8\x9bimii maximale date, fie este co-finit\xc4\x83. Motiva\xc8\x9bia ini\xc8\x9bial\xc4\x83 a lui\xc2\xa0Post pentru studiul acestei re\xc8\x9bele a fost dorin\xc8\x9ba de a g\xc4\x83si o no\xc8\x9biune structural\xc4\x83 astfel \xc3\xaenc\xc3\xa2t fiecare mul\xc8\x9bime care \xc3\xaendepline\xc8\x99te aceast\xc4\x83 proprietate s\xc4\x83 nu fie \xc3\xaen gradul Turing al mul\xc8\x9bimilor recursive, nici \xc3\xaen gradul Turing al problemei opririi. Post nu a g\xc4\x83sit o astfel de proprietate \xc8\x99i solu\xc8\x9bia problemei sale aplic\xc4\x83 \xc3\xaen schimb metoda priorit\xc4\x83\xc8\x9bii; Harrington \xc8\x99i Soare (1991) au g\xc4\x83sit \xc3\xaen cele din urm\xc4\x83 o astfel de proprietate.\n_START_SECTION_\nProbleme de automorfism\n_START_PARAGRAPH_\nO alt\xc4\x83 \xc3\xaentrebare important\xc4\x83 este existen\xc8\x9ba automorfismelor \xc3\xaen structurile teoriei calculabilit\xc4\x83\xc8\x9bii. Una dintre aceste structuri este cea a mul\xc8\x9bimilor recursiv enumerabile \xc3\xaempreun\xc4\x83 cu incluziunea \xc8\x99i cu diferen\xc8\x9ba modulo finit\xc4\x83; \xc3\xaen aceast\xc4\x83 structur\xc4\x83, A\xc2\xa0este sub B dac\xc4\x83 \xc8\x99i numai dac\xc4\x83 diferen\xc8\x9ba B \xe2\x88\x92\xc2\xa0este finit\xc4\x83. Mul\xc8\x9bimile maximale\xc2\xa0(a\xc8\x99a cum sunt definite \xc3\xaen paragraful anterior) au proprietatea c\xc4\x83 acestea nu pot fi automorfe cu mul\xc8\x9bimi nemaximale, adic\xc4\x83 dac\xc4\x83 exist\xc4\x83 un automorfism al mul\xc8\x9bimilor recursiv enumerabile \xc3\xaen structura men\xc8\x9bionat\xc4\x83, atunci fiec\xc4\x83rei mul\xc8\x9bimi maximale \xc3\xaei corespunde o alt\xc4\x83 mul\xc8\x9bime maximal\xc4\x83. Soare (1974) a ar\xc4\x83tat c\xc4\x83 \xc8\x99i reciproca este valabil\xc4\x83, adic\xc4\x83 orice dou\xc4\x83 mul\xc8\x9bimi maximale sunt automorfe. Deci mul\xc8\x9bimile maximale formeaz\xc4\x83 o orbit\xc4\x83, adic\xc4\x83 fiecare automorfism conserv\xc4\x83 maximalitatea \xc8\x99i orice dou\xc4\x83 mul\xc8\x9bimi maximale sunt transformate una \xc3\xaen alta printr-un automorfism. Harrington a dat un alt exemplu de proprietate automorf\xc4\x83: mul\xc8\x9bimile creative, mul\xc8\x9bimi care sunt echivalente neinjectiv cu problema opririi._NEWLINE_Pe l\xc3\xa2ng\xc4\x83 re\xc8\x9beaua mul\xc8\x9bimilor recursiv enumerabile, automorfismele sunt studiate \xc8\x99i pentru structura gradelor Turing ale tuturor mul\xc8\x9bimilor, precum \xc8\x99i pentru structura de grade Turing ale mul\xc8\x9bimilor r.e.. \xc3\x8en ambele cazuri, Cooper sus\xc8\x9bine c\xc4\x83 a construit automorfisme triviale \xc3\xaen care unele grade corespund la alte grade; aceast\xc4\x83 construc\xc8\x9bie nu au fost \xc3\xaens\xc4\x83 verificat\xc4\x83 \xc8\x99i unii colegi cred c\xc4\x83 construc\xc8\x9bia con\xc8\x9bine erori \xc8\x99i c\xc4\x83 \xc3\xaentrebarea dac\xc4\x83 exist\xc4\x83 un automorfism trivial de grade Turing este \xc3\xaenc\xc4\x83 una dintre principalele chestiuni nerezolvate \xc3\xaen acest domeniu (Slaman \xc8\x99i Woodin 1986, Ambos-Spioni \xc8\x99i Fejer 2006).\n_START_SECTION_\nComplexitate Kolmogorov\n_START_PARAGRAPH_\nDomeniul complexit\xc4\x83\xc8\x9bii Kolmogorov \xc8\x99i al\xc2\xa0aleatoriului algoritmic\xc2\xa0a fost dezvoltat\xc4\x83 \xc3\xaen deceniile anilor 1960 \xc8\x99i 1970 de c\xc4\x83tre Chaitin, Kolmogorov, Levin, Martin-L\xc3\xb6f \xc8\x99i Solomonoff (numele sunt date aici \xc3\xaen ordine alfabetic\xc4\x83; o mare parte din cercetare a fost independent\xc4\x83, iar unitatea conceptului de aleatoriu nu era \xc3\xaen\xc8\x9beleas\xc4\x83 la momentul respectiv). Ideea principal\xc4\x83 este s\xc4\x83 se ia \xc3\xaen considerare o ma\xc8\x99in\xc4\x83 Turing universal\xc4\x83 U \xc8\x99i s\xc4\x83 se m\xc4\x83soare complexitatea unui num\xc4\x83r (sau \xc8\x99ir de caractere) x ca durata cea mai scurt\xc4\x83 a intr\xc4\x83rii\xc2\xa0p astfel \xc3\xaenc\xc3\xa2t U(p) produce la ie\xc8\x99ire\xc2\xa0x. Aceast\xc4\x83 abordare a revolu\xc8\x9bionat modalit\xc4\x83\xc8\x9bile anterioare de a determina c\xc3\xa2nd o secven\xc8\x9b\xc4\x83 infinit\xc4\x83 (echivalent, func\xc8\x9bia caracteristic\xc4\x83 a unei submul\xc8\x9bimi de numere naturale) este aleatoare \xc8\x99i c\xc3\xa2nd nu prin invocarea unei no\xc8\x9biunea de aleatoriu pentru obiecte finite. Complexitatea Kolmogorov a devenit nu numai un subiect de studiu independent, ci este aplicat\xc4\x83 \xc8\x99i la alte subiecte, ca un instrument pentru ob\xc8\x9binerea de demonstra\xc8\x9bii. Exist\xc4\x83 \xc3\xaenc\xc4\x83 multe probleme \xc3\xaen acest domeniu. Din acest motiv, o recent\xc4\x83 conferin\xc8\x9b\xc4\x83 de cercetare \xc3\xaen acest domeniu s-a \xc8\x9binut \xc3\xaen ianuarie 2007 \xc8\x99i o list\xc4\x83 de probleme deschise este men\xc8\x9binut\xc4\x83 de c\xc4\x83tre Joseph Miller \xc8\x99i Andre Nies.\n_START_SECTION_\nCalculul de frecven\xc8\x9b\xc4\x83\n_START_PARAGRAPH_\nAceast\xc4\x83 ramur\xc4\x83 a teoriei calculabilit\xc4\x83\xc8\x9bii analizeaz\xc4\x83 urm\xc4\x83toarea \xc3\xaentrebare: Pentru numerele\xc2\xa0m \xc8\x99i n\xc2\xa0fixe, cu 0 < m < n, pentru care func\xc8\x9bii\xc2\xa0A se poate calcula pentru orice\xc2\xa0n intr\xc4\x83ri distincte\xc2\xa0x\xe2\x82\x81, x\xe2\x82\x82, ..., x\xe2\x82\x99 un tuplu de n numere y\xe2\x82\x81,y\xe2\x82\x82,...,y\xe2\x82\x99 astfel \xc3\xaenc\xc3\xa2t cel pu\xc8\x9bin m din ecua\xc8\x9biile O(x\xe2\x82\x96) = y\xe2\x82\x96 s\xc4\x83 fie adev\xc4\x83rate. Astfel de mul\xc8\x9bimi sunt cunoscute ca mul\xc8\x9bimi (m, n)-recursive. Primul rezultat important \xc3\xaen aceast\xc4\x83 ramur\xc4\x83 a teoriei calculabilit\xc4\x83\xc8\x9bii este rezultatul lui Trakhtenbrot c\xc4\x83 o mul\xc8\x9bime este calculabil\xc4\x83 dac\xc4\x83 este (m, n)-recursiv\xc4\x83 pentru m, n cu 2m > n. Pe de alt\xc4\x83 parte, mul\xc8\x9bimile\xc2\xa0Semi-membership ale lui Jockusch\xc2\xa0(care erau deja cunoscute informal \xc3\xaenainte de a fi prezentate de Jockusch \xc3\xaen 1968) sunt exemple de mul\xc8\x9bimi care sunt (m, n)-recursive dac\xc4\x83 \xc8\x99i numai dac\xc4\x83 2m < n + 1. Exist\xc4\x83 un num\xc4\x83r nenum\xc4\x83rabil de astfel de mul\xc8\x9bimi, dar \xc8\x99i unele mul\xc8\x9bimi de acest tip recursiv enumerabile, dar necalculabile. Mai t\xc3\xa2rziu, Degtev a stabilit o ierarhie a mul\xc8\x9bimilor recursiv enumerabile care sunt (1, n + 1)-recursive dar nu (1, n)-recursive. Dup\xc4\x83 o lung\xc4\x83 faz\xc4\x83 de cercetare de c\xc4\x83tre oameni de \xc8\x99tiin\xc8\x9b\xc4\x83 ru\xc8\x99i, acest subiect a fost repopularizat \xc3\xaen Occident de teza lui Beigel a interog\xc4\x83rilor m\xc4\x83rginite, care lega calculul de frecven\xc8\x9b\xc4\x83 de calculul reductibilit\xc4\x83\xc8\x9bilor m\xc4\x83rginite mai sus-men\xc8\x9bionate \xc8\x99i de alte no\xc8\x9biuni. Unul dintre principalele rezultate a fost teoria cardinalit\xc4\x83\xc8\x9bii a lui Kummer, care afirm\xc4\x83 c\xc4\x83 o mul\xc8\x9bime\xc2\xa0A\xc2\xa0este calculabil\xc4\x83 dac\xc4\x83 \xc8\x99i numai dac\xc4\x83 exist\xc4\x83 un n astfel \xc3\xaenc\xc3\xa2t un algoritm oarecare enumer\xc4\x83 pentru fiecare tuplu de n numere diferite p\xc3\xa2n\xc4\x83 la n variante posibile de cardinalitate a acestei mul\xc8\x9bimi cu\xc2\xa0n numere intersectat\xc4\x83 cu A; aceste variante trebuie s\xc4\x83 con\xc8\x9bin\xc4\x83 cardinalitatea adev\xc4\x83rat\xc4\x83, dar \xc8\x99i cel pu\xc8\x9bin una fals\xc4\x83.\n_START_SECTION_\nInferen\xc8\x9b\xc4\x83 inductiv\xc4\x83\n_START_PARAGRAPH_\nAceasta este o ramur\xc4\x83 a teoriei \xc3\xaenv\xc4\x83\xc8\x9b\xc4\x83rii legat\xc4\x83 de teoria calculabilit\xc4\x83\xc8\x9bii. Este bazat\xc4\x83 pe modelul de \xc3\xaenv\xc4\x83\xc8\x9bare al lui Gold \xc3\xaen limita din 1967 \xc8\x99i a dezvoltat de atunci din ce \xc3\xaen ce mai multe modele de \xc3\xaenv\xc4\x83\xc8\x9bare. \xc3\x8en general, scenariul este urm\xc4\x83torul: Av\xc3\xa2nd \xc3\xaen vedere o clas\xc4\x83\xc2\xa0S de func\xc8\x9bii calculabile, exist\xc4\x83 un sistem de \xc3\xaenv\xc4\x83\xc8\x9bare (recursiv func\xc8\x9bional), care emite pentru orice intrare de forma (f(0),f(1),...,f(n)) o ipotez\xc4\x83. Un sistem de \xc3\xaenv\xc4\x83\xc8\x9bare\xc2\xa0M \xc3\xaenva\xc8\x9b\xc4\x83 o func\xc8\x9bie f dac\xc4\x83 aproape toate ipotezele sunt cu acela\xc8\x99i indice e al lui\xc2\xa0f \xc3\xaen raport cu o num\xc4\x83rare acceptabil\xc4\x83 convenit\xc4\x83 anterior a tuturor func\xc8\x9biilor calculabile; M \xc3\xaenva\xc8\x9b\xc4\x83 S dac\xc4\x83 M \xc3\xaenva\xc8\x9b\xc4\x83 fiecare f\xc2\xa0din S. Rezultatele de baz\xc4\x83 sunt c\xc4\x83 toate clasele recursiv enumerabile de func\xc8\x9bii sunt \xc3\xaenv\xc4\x83\xc8\x9babile, \xc3\xaen timp ce clasa REC a tuturor func\xc8\x9biilor calculabile nu este \xc3\xaenv\xc4\x83\xc8\x9babil\xc4\x83. Au fost analizate multe modele asociate, iar \xc3\xaenv\xc4\x83\xc8\x9barea claselor de mul\xc8\x9bimi recursiv enumerabile din date pozitive este un subiect studiat de la articolul ini\xc8\x9bial al lui Gold din 1967 \xc3\xaencoace.\n_START_SECTION_\nGeneraliz\xc4\x83ri ale calculabilit\xc4\x83\xc8\x9bii Turing\n_START_PARAGRAPH_\nTeoria calculabilit\xc4\x83\xc8\x9bii cuprinde studiul unor no\xc8\x9biuni generalizate din acest domeniu, cum ar fi\xc2\xa0reductibilitatea aritmetic\xc4\x83, reductibilitatea hyperarithmetic\xc4\x83\xc2\xa0\xc8\x99i teoria \xce\xb1-recursivit\xc4\x83\xc8\x9bii, a\xc8\x99a cum descrie Sacks (1990). Aceste no\xc8\x9biuni generalizate includ reductibilit\xc4\x83\xc8\x9bi care nu pot fi executate de ma\xc8\x99ini Turing dar cu toate acestea sunt generaliz\xc4\x83ri naturale\xc2\xa0ale reductibilit\xc4\x83\xc8\x9bii Turing. Aceste studii includ abord\xc4\x83ri de a investiga ierarhia analitic\xc4\x83\xc2\xa0ce difer\xc4\x83 de ierarhia aritmetic\xc4\x83\xc2\xa0prin aceea c\xc4\x83 permite cuantificarea peste mul\xc8\x9bimi de numere naturale, \xc3\xaen plus fa\xc8\x9b\xc4\x83 de cuantificarea pe numere individuale. Aceste zone sunt legate de teoriile bunelor-ordon\xc4\x83ri \xc8\x99i arborilor; de exemplu mul\xc8\x9bimea tuturor indicilor arborilor recursivi (nebinari) f\xc4\x83r\xc4\x83 ramuri infinite este complet\xc4\x83 pentru nivelul  de ierarhie analitic\xc4\x83. At\xc3\xa2t reductibilitatea Turing c\xc3\xa2t \xc8\x99i reductibilitatea hyperarithmetic\xc4\x83 sunt importante \xc3\xaen domeniul teoriei mul\xc8\x9bimilor efectiv descriptive. No\xc8\x9biune \xc8\x99i mai general\xc4\x83 de grade de constructibilitate\xc2\xa0este studiat\xc4\x83 \xc3\xaen teoria mul\xc8\x9bimilor.\n_START_SECTION_\nTeoria continu\xc4\x83 a calculabilit\xc4\x83\xc8\x9bii\n_START_PARAGRAPH_\nTeoria calculabilit\xc4\x83\xc8\x9bii pentru calculul numeric este bine dezvoltat\xc4\x83. Teoria calculabilit\xc4\x83\xc8\x9bii este mai pu\xc8\x9bin dezvoltat\xc4\x83 pentru calculul analogic\xc2\xa0care apare \xc3\xaen calculatoarele analogice, \xc3\xaen\xc2\xa0prelucrarea semnalelor analogice, electronica analogic\xc4\x83, re\xc8\x9bele neurale \xc8\x99i teoria controlului\xc2\xa0\xc3\xaen timp continuu, modelate prin ecua\xc8\x9bii diferen\xc8\x9biale \xc8\x99i sisteme dinamice\xc2\xa0continue (Orponen 1997; Moore, 1996).\n_START_SECTION_\nRela\xc8\x9biile dintre definibilitate, demonstra\xc8\x9bie \xc8\x99i calculabilitate\n_START_PARAGRAPH_\nExist\xc4\x83 rela\xc8\x9bii str\xc3\xa2nse \xc3\xaentre gradul Turing\xc2\xa0al unei mul\xc8\x9bimi de numere naturale \xc8\x99i dificultatea (\xc3\xaen termeni de ierarhie aritmetic\xc4\x83) de definire a acelei mul\xc8\x9bimi, folosind o formul\xc4\x83 de ordinul \xc3\xaent\xc3\xa2i. O astfel de rela\xc8\x9bie este precizat\xc4\x83 de teorema lui Post. O rela\xc8\x9bie mai slab\xc4\x83 a fost demonstrat\xc4\x83 de Kurt G\xc3\xb6del \xc3\xaen demonstra\xc8\x9biile teoremei sale de completitudine \xc8\x99i incompletitudine. Demonstra\xc8\x9biile lui\xc2\xa0G\xc3\xb6del arat\xc4\x83 c\xc4\x83 mul\xc8\x9bimea de consecin\xc8\x9be logice a unei teorii de ordinul \xc3\xaent\xc3\xa2i este o mul\xc8\x9bime recursiv enumerabil\xc4\x83, \xc8\x99i c\xc4\x83, dac\xc4\x83 teoria este suficient de puternic\xc4\x83 aceast\xc4\x83 mul\xc8\x9bime va fi necalculabil\xc4\x83. \xc3\x8en mod similar,\xc2\xa0teorema indefinibilit\xc4\x83\xc8\x9bii a lui Tarski\xc2\xa0poate fi interpretat\xc4\x83 at\xc3\xa2t \xc3\xaen termeni de definibilitate c\xc3\xa2t \xc8\x99i \xc3\xaen termeni de calculabilitate._NEWLINE_Teoria calculabilit\xc4\x83\xc8\x9bii este legat\xc4\x83 \xc8\x99i de aritmetica de ordinul al doilea, o teorie formal\xc4\x83 a numerelor naturale \xc8\x99i a mul\xc8\x9bimilor de numere naturale. Faptul c\xc4\x83 anumite mul\xc8\x9bimi sunt calculabile sau relativ calculabile implic\xc4\x83 de multe ori\xc2\xa0faptul c\xc4\x83 aceste mul\xc8\x9bimi pot fi definite \xc3\xaen subsisteme slabe ale aritmeticii de ordinul al doilea. Programul\xc2\xa0matematicii inverse\xc2\xa0utilizeaz\xc4\x83 aceste subsisteme pentru a m\xc4\x83sura necalculabilitatea inerent\xc4\x83 a unor teoreme matematice bine cunoscute. Simpson (1999) discut\xc4\x83 mai multe aspecte de aritmetic\xc4\x83 de ordinul al doilea \xc8\x99i matematic\xc4\x83 invers\xc4\x83._NEWLINE_Domeniul teoriei demonstra\xc8\x9biei\xc2\xa0include studiul aritmeticii de ordinul al doilea \xc8\x99i a\xc2\xa0aritmeticii Peano, precum \xc8\x99i teorii formale de numere naturale mai slabe dec\xc3\xa2t aritmetica Peano. O metod\xc4\x83 de clasificare a puterii acestor sisteme slabe este prin caracterizatarea func\xc8\x9biilor calculabile pe care sistemul le poate demonstra c\xc4\x83 sunt\xc2\xa0totale\xc2\xa0(a se vedea Fairtlough \xc8\x99i Wainer (1998)). De exemplu, \xc3\xaen aritmetica primitiv recursiv\xc4\x83 orice func\xc8\x9bie calculabil\xc4\x83 care se poate demonstra c\xc4\x83 este total\xc4\x83 este de fapt primitiv recursiv\xc4\x83, \xc3\xaen timp ce aritmetica Peano\xc2\xa0demonstreaz\xc4\x83 c\xc4\x83 func\xc8\x9bii ca func\xc8\x9bia Ackermann, care nu sunt primitiv recursive, sunt totale. Nu fiecare func\xc8\x9bie total\xc4\x83 calculabil\xc4\x83 este demonstrabil\xc4\x83 a fi total\xc4\x83 \xc3\xaen aritmetica Peano dar un exemplu de astfel de func\xc8\x9bie este dat de teorema lui Goodstein.\n_START_SECTION_\nNumele domeniului\n_START_PARAGRAPH_\nDomeniul din logica matematic\xc4\x83 ce se ocup\xc4\x83 cu calculabilitatea \xc8\x99i generaliz\xc4\x83rile ei a fost numit \xe2\x80\x9eteoria recursivit\xc4\x83\xc8\x9bii\xe2\x80\x9d la \xc3\xaenceputurile sale. Robert I. Soare, un renumit cercet\xc4\x83tor \xc3\xaen domeniu, a propus (Soare 1996) ca domeniul s\xc4\x83 se numeasc\xc4\x83 \xc3\xaen schimb \xe2\x80\x9eteoria calculabilit\xc4\x83\xc8\x9bii\xe2\x80\x9d. El sus\xc8\x9bine c\xc4\x83 terminologia lui Turing bazat\xc4\x83 pe cuv\xc3\xa2ntul \xe2\x80\x9ecalculabil\xe2\x80\x9d este mai natural\xc4\x83 \xc8\x99i mai larg \xc3\xaen\xc8\x9beleas\xc4\x83 dec\xc3\xa2t terminologia folosind cuv\xc3\xa2ntul \xe2\x80\x9erecursiv\xe2\x80\x9d, introdus de Kleene. Mul\xc8\x9bi cercet\xc4\x83tori contemporani au \xc3\xaenceput s\xc4\x83 foloseasc\xc4\x83 aceast\xc4\x83 nou\xc4\x83 terminologie. Ace\xc8\x99ti cercet\xc4\x83tori utilizeaz\xc4\x83 \xc8\x99i terminologia func\xc8\x9bie\xc2\xa0par\xc8\x9bial calculabil\xc4\x83\xc2\xa0\xc8\x99i mul\xc8\x9bime enumerabil calculabil\xc4\x83\xc2\xa0\xc3\xaen loc de\xc2\xa0func\xc8\x9bie par\xc8\x9bial recursiv\xc4\x83\xc2\xa0\xc8\x99i mul\xc8\x9bime recursiv enumerabil\xc4\x83\xc2\xa0(r.e.). Nu to\xc8\x9bi cercet\xc4\x83torii au fost \xc3\xaens\xc4\x83 convin\xc8\x99i, dup\xc4\x83 cum au explicat Fortnow \xc8\x99i Simpson. Unii comentatori sus\xc8\x9bin c\xc4\x83 at\xc3\xa2t numele de\xc2\xa0teoria\xc2\xa0recursivit\xc4\x83\xc8\x9bii\xc2\xa0c\xc3\xa2t \xc8\x99i cel de teoria calculabilit\xc4\x83\xc8\x9bii\xc2\xa0nu reu\xc8\x99esc s\xc4\x83 transmit\xc4\x83 c\xc4\x83 cele mai multe dintre obiectele studiate \xc3\xaen teoria calculabilit\xc4\x83\xc8\x9bii nu sunt calculabile._NEWLINE_Rogers (1967) a sugerat ca o proprietatea-cheie a teoriei calculabilit\xc4\x83\xc8\x9bii este faptul c\xc4\x83 rezultatele \xc8\x99i structurile sale\xc2\xa0ar trebui s\xc4\x83 fie invariante la bijec\xc8\x9bii\xc2\xa0calculabile\xc2\xa0pe mul\xc8\x9bimea numerelor naturale (aceast\xc4\x83 sugestie se bazeaz\xc4\x83 pe ideile\xc2\xa0programului Erlangen\xc2\xa0din geometrie). Ideea este c\xc4\x83 o bijec\xc8\x9bie calculabil\xc4\x83 doar schimb\xc4\x83 denumirea numerelor dintr-o mul\xc8\x9bime, \xc8\x99i nu indic\xc4\x83 vreo structur\xc4\x83 \xc3\xaen mul\xc8\x9bime, a\xc8\x99a cum o rota\xc8\x9bie a planului euclidian nu schimba niciun aspect geometric al liniilor trasate pe el. Deoarece orice dou\xc4\x83 mul\xc8\x9bimi infinite calculabile sunt legate printr-o bijec\xc8\x9bie calculabil\xc4\x83, aceast\xc4\x83 propunere identific\xc4\x83 toate mul\xc8\x9bimile infinite calculabile (mul\xc8\x9bimile finite calculabile sunt considerate caz banal). Potrivit lui Rogers, mul\xc8\x9bimile de interes din teoria recursivit\xc4\x83\xc8\x9bii sunt mul\xc8\x9bimile necalculabile, \xc3\xaemp\xc4\x83r\xc8\x9bite \xc3\xaen clase de echivalen\xc8\x9b\xc4\x83 de bijec\xc8\x9biile calculabile ale numerelor naturale.\n_START_SECTION_\nOrganiza\xc8\x9bii profesionale\n_START_PARAGRAPH_\nPrincipala organiza\xc8\x9bie profesional\xc4\x83 pentru teoria recursivit\xc4\x83\xc8\x9bii este cea Association for Symbolic Logic, care sus\xc8\x9bine mai multe conferin\xc8\x9be de cercetare \xc3\xaen fiecare an. Asocia\xc8\x9bia de cercetare interdisciplinar\xc4\x83\xc2\xa0Computability in Europe\xc2\xa0(CiE) organizeaz\xc4\x83 \xc8\x99i ea o serie de conferin\xc8\x9be anuale.'