Teoria calculabilității

începând cu teoria mulțimilor și funcțiilor recursive descrise mai sus, domeniul teoriei recursivității a crescut pentru a include studiul multor subiecte strâns legate. Acestea nu sunt domenii independente de cercetare: fiecare dintre aceste domenii atrage idei și rezultate din celelalte, iar majoritatea teoreticienilor recursivității sunt familiarizați cu majoritatea acestora.

calculabilitatea relativă și gradul Turingedit

teoria recursivității în logica matematică s-a concentrat în mod tradițional pe calculabilitatea relativă, o generalizare a calculabilității Turing definită folosind oracle mașini Turing, introdus de Turing (1939). O mașină Turing oracolă este un dispozitiv ipotetic care, pe lângă efectuarea acțiunilor unei mașini Turing obișnuite, este capabil să pună întrebări unui oracol, care este un set special de numere naturale. Mașina oracle poate pune doar întrebări despre formularul ” este n în setul oracle?”. Fiecare întrebare va primi imediat un răspuns corect, chiar dacă setul oracle nu este calculabil. Astfel, o mașină oracle cu un oracol necalculabil va putea calcula seturi pe care o mașină Turing fără oracol nu le poate.

informal, un set de numere naturale a este Turing reductibil la o mulțime B dacă există o mașină oracle care spune corect dacă numerele sunt în a când sunt rulate cu B Ca Set oracle (în acest caz, se spune că și mulțimea A 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 că mulțimile au același grad Turing (numit și grad de nesolvabilitate). Gradul Turing al unui set oferă o măsură precisă a cât de necomputabil este setul.

exemplele naturale de seturi care nu sunt calculabile, inclusiv multe seturi diferite care codifică variante ale problemei de oprire, au două proprietăți comune:

1. ele sunt recursiv enumerabile și
2. fiecare poate fi tradus în oricare altul printr-o reducere multi-unu. Adică, având în vedere astfel de mulțimi a și B, există o funcție totală calculabilă f astfel încât a = {x : F(x) b}. Se spune că aceste seturi sunt echivalente cu mai multe (sau echivalent m).

reducerile Multi-unu sunt “mai puternice” decât reducerile Turing: dacă o mulțime A este multi-unu reductibil la o mulțime B, atunci A este Turing reductibil la B, dar inversul nu se menține întotdeauna. Deși exemplele naturale de mulțimi necalculabile sunt toate echivalente cu mai multe, este posibil să se construiască mulțimi recursiv enumerabile A și B astfel încât a este Turing reductibil la B, dar nu mulți-unu reductibil la B. Se poate arăta că fiecare mulțime recursiv enumerabilă este multi-unu reductibil la problema opririi și, prin urmare, problema opririi este cea mai complicată mulțime recursiv enumerabilă în ceea ce privește reductibilitatea multi-unu și în ceea ce privește reductibilitatea Turing. Post (1944) a întrebat dacă fiecare mulțime recursiv enumerabilă este fie calculabilă, fie Turing echivalentă cu problema opririi, adică dacă nu există o mulțime recursiv enumerabilă cu un grad Turing intermediar între cele două.

ca rezultate intermediare, post a definit tipuri naturale de mulțimi recursiv enumerabile, cum ar fi mulțimile simple, hipersimple și hiperhipersimple. Post a arătat că aceste seturi sunt strict între seturile calculabile și problema opririi în ceea ce privește reductibilitatea multora. Post a arătat, de asemenea, că unele dintre ele sunt strict intermediare sub alte noțiuni de reductibilitate mai puternice decât reductibilitatea Turing. Dar Post a lăsat deschisă principala problemă a existenței seturilor recursiv enumerabile de grad Turing intermediar; această problemă a devenit cunoscută sub numele de problema lui Post. După zece ani, Kleene și Post au arătat în 1954 că există grade Turing intermediare între cele ale mulțimilor calculabile și problema opririi, dar nu au reușit să arate că oricare dintre aceste grade conține un set recursiv enumerabil. Foarte curând după aceasta, Friedberg și Muchnik au rezolvat în mod independent problema lui Post stabilind existența unor seturi recursiv enumerabile de grad intermediar. Acest rezultat revoluționar a deschis un studiu amplu al gradelor Turing ale mulțimilor recursiv enumerabile care s-au dovedit a poseda o structură foarte complicată și non-banală.

există nenumărate mulțimi care nu sunt recursiv enumerabile, iar investigarea gradelor Turing ale tuturor mulțimilor este la fel de centrală în teoria recursivității ca și investigarea gradelor Turing recursiv enumerabile. Au fost construite multe grade cu proprietăți speciale: grade fără hiperimune în care fiecare funcție calculabilă în raport cu acel grad este majorizată de o funcție calculabilă (nerelativizată; grade î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 în funcție de g astfel încât g(x) < f(x) pentru toate X > c; grade aleatorii care conțin seturi algoritmice aleatorii; 1-grade generice ale mulțimilor 1-generice; și gradele de sub problema opririi mulțimilor limită-recursive.

studiul gradelor Turing arbitrare (nu neapărat recursiv enumerabile) implică studiul saltului Turing. Având în vedere o mulțime A, saltul Turing al lui A este un set de numere naturale care codifică o soluție la problema opririi pentru mașinile oracle Turing care rulează cu oracle A. saltul Turing al oricărui set este întotdeauna de grad Turing mai mare decât setul original și o teoremă a lui Friedburg arată că orice set care calculează problema opririi poate fi obținut ca saltul Turing al unui alt set. 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 subseturi ale numerelor naturale pe baza definibilității lor în aritmetică.

multe cercetări recente privind gradele Turing s-au concentrat asupra structurii generale a mulțimii de grade Turing și a mulțimii de grade Turing care conține mulțimi recursiv enumerabile. O teoremă profundă a lui Shore și Slaman (1999) afirmă că funcția care mapează un grad x la gradul saltului său Turing este definibilă în ordinea parțială a gradelor Turing. Un sondaj recent realizat de Ambos-Spies și Fejer (2006) oferă o imagine de ansamblu asupra acestei cercetări și a progresiei sale istorice.

alte reductibilitățiedit

un domeniu continuu de cercetare în teoria recursivității studiază relațiile de reductibilitate, altele decât reductibilitatea Turing. Post (1944) a introdus mai multe reductibilități puternice, numite astfel pentru că implică reductibilitatea tabelului adevărului. O mașină Turing care implementează o reductibilitate puternică va calcula o funcție totală indiferent de oracolul cu care este prezentată. Reducibilitățile slabe sunt cele în care un proces de reducere nu se poate încheia pentru toate oracolele; reductibilitatea Turing este un exemplu.

reducibilitățile puternice includ:

reductibilitatea unu-unu a este reductibilă unu-unu (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 mulți-unu aceasta este în esență reductibilitatea unu-unu fără constrângerea ca f să fie injectiv. A este multi-unu reductibil (sau m-reductibil) la B dacă există o funcție totală calculabilă f astfel încât fiecare n este în a dacă și numai dacă f(n) este în B. Reductibilitatea tabelului adevărului a este tabelul adevărului reductibil la B dacă A este Turing reductibil la B printr-un oracol mașină Turing care calculează o funcție totală indiferent de oracolul care îi este dat. Datorită compactității spațiului Cantor, acest lucru este echivalent cu a spune că reducerea prezintă o singură listă de întrebări (în funcție doar de intrare) către oracol simultan, iar apoi văzând răspunsurile lor este capabil să producă o ieșire fără a pune întrebări suplimentare, indiferent de răspunsul oracolului la interogările inițiale. Au fost studiate și multe variante ale reductibilității tabelului adevărului.

reductibilități suplimentare (pozitive, disjunctive, conjunctive, liniare și versiunile lor slabe și delimitate) sunt discutate în articolul reducere (teoria recursivității).

cercetările majore privind reducibilitățile puternice au fost compararea teoriilor lor, atât pentru clasa tuturor mulțimilor recursiv enumerabile, cât și pentru clasa tuturor subseturilor numerelor naturale. Mai mult, au fost studiate relațiile dintre reducibilități. De exemplu, se știe că fiecare grad Turing este fie un grad de masă a adevărului, fie este unirea a infinit de multe grade de masă a adevărului.

Reducibilitățile mai slabe decât reductibilitatea Turing (adică reducibilitățile care sunt implicate de reductibilitatea Turing) au fost, de asemenea, studiate. Cele mai cunoscute sunt reductibilitatea aritmetică și reductibilitatea hiperaritmetică. Aceste reductibilități sunt strâns legate de definibilitate peste modelul standard de aritmetică.

teorema lui Rice și ierarhia aritmeticăedit

Rice a arătat că pentru fiecare clasă nontrivială C (care conține unele, dar nu toate seturile r.e.) setul index E = {e: eth r.e. setul We is in C} are proprietatea că fie problema opririi, fie complementul său este multi-unu reductibil la E, adică poate fi mapat folosind o reducere multi-unu la E (vezi teorema lui Rice pentru mai multe detalii). Dar, multe dintre aceste seturi de indici sunt chiar mai complicate decât problema opririi. Aceste tipuri de seturi pot fi clasificate folosind ierarhia aritmetică. De exemplu, indicele set FIN de clasă a tuturor seturilor finite este la nivelul de la sută 2, Indicele set REC al clasei de la toate seturile recursive este la nivelul de la sută 3, indicele set COFIN al tuturor seturilor de la sută este, de asemenea, la nivelul de la sută 3 și indicele set COMP al clasei de la toate seturile Turing-complete de la sută 44. Aceste niveluri de ierarhie sunt definite inductiv, Hectolitric + 1 conține doar toate mulțimile care sunt recursiv enumerabile în raport cu Hectolitric; XV1 conține mulțimile recursiv enumerabile. Seturile de indici date aici sunt chiar complete pentru nivelurile lor, adică toate seturile din aceste niveluri pot fi multe-unul redus la seturile de indici date.

reverse mathematicsEdit

programul de matematică inversă întreabă ce axiome ale existenței mulțimilor sunt necesare pentru a dovedi anumite teoreme ale matematicii în subsistemele aritmeticii de ordinul doi. Acest studiu a fost inițiat de Harvey Friedman și a fost studiat în detaliu de Stephen Simpson și alții; Simpson (1999) oferă o discuție detaliată a programului. Axiomele existenței mulțimilor în cauză corespund informal axiomelor care spun că setul de putere al numerelor naturale este închis sub diferite noțiuni de reductibilitate. Cea mai slabă astfel de axiomă studiată în matematica inversă este înțelegerea recursivă, care afirmă că setul de putere al naturalilor este închis sub Turing reductibilitate.

NumberingsEdit

o numerotare este o enumerare a funcțiilor; are doi parametri, e și x și emite valoarea funcției e în numerotarea de pe intrarea x. Numărările pot fi parțial-recursive, deși unii dintre membrii săi sunt recursivi totali, adică funcții calculabile. Numerele admisibile sunt cele în care toate celelalte pot fi traduse. O numerotare Friedberg (numită după descoperitorul său) este o numerotare unu-unu a tuturor funcțiilor parțial-recursive; nu este neapărat o numerotare admisibilă. Cercetările ulterioare s-au ocupat și de numărarea altor clase, cum ar fi clasele de mulțimi recursiv enumerabile. Goncharov a descoperit, de exemplu, o clasă de mulțimi recursiv enumerabile pentru care numerotările se încadrează exact în două clase în ceea ce privește izomorfismele recursive.

metoda priorităedit

pentru explicații suplimentare, consultați secțiunea problema postării și metoda prioritară din articolul gradul Turing.

problema lui Post a fost rezolvată cu o metodă numită metoda priorității; o dovadă care folosește această metodă se numește argument prioritar. Această metodă este utilizată în principal pentru a construi seturi recursiv enumerabile cu proprietăți particulare. Pentru a utiliza această metodă, proprietățile dorite ale setului care urmează să fie construit sunt împărțite într-o listă infinită de obiective, cunoscută sub numele de cerințe, astfel încât satisfacerea tuturor cerințelor va determina setul construit să aibă proprietățile dorite. Fiecare cerință este atribuită unui număr natural care reprezintă prioritatea cerinței; deci 0 este atribuit celei mai importante priorități, 1 celei de-a doua cele mai importante și așa mai departe. Setul este apoi construit în etape, fiecare etapă încercând să satisfacă una dintre mai multe cerințe fie prin adăugarea de numere la set, fie prin interzicerea numerelor din set, astfel încât setul final să satisfacă cerința. Se poate întâmpla ca satisfacerea unei cerințe să facă ca alta să devină nesatisfăcută; ordinea prioritară este utilizată pentru a decide ce să facă într-un astfel de eveniment.

argumentele prioritare au fost folosite pentru a rezolva multe probleme în teoria recursivității și au fost clasificate într-o ierarhie bazată pe complexitatea lor (Soare 1987). Deoarece argumentele prioritare complexe pot fi tehnice și dificil de urmărit, în mod tradițional s-a considerat de dorit să se demonstreze rezultatele fără argumente prioritare sau să se vadă dacă rezultatele dovedite cu argumente prioritare pot fi dovedite și fără ele. De exemplu, Kummer a publicat o lucrare despre o dovadă a existenței Numerotărilor Friedberg fără a utiliza metoda prioritară.

rețeaua mulțimilor recursiv enumerabile

când Post a definit noțiunea unui set simplu ca un set r.e. cu un complement infinit care nu conține niciun r.e infinit. set, a început să studieze structura mulțimilor recursiv enumerabile sub includere. Această rețea a devenit o structură bine studiată. Mulțimile Recursive pot fi definite în această structură prin rezultatul de bază că o mulțime este recursivă dacă și numai dacă mulțimea și complementul său sunt ambele recursiv enumerabile. Mulțimile r. e. Infinite au întotdeauna subseturi recursive infinite; dar, pe de altă parte, există mulțimi simple, dar nu au un superset recursiv coinfinit. Post (1944) a introdus deja seturi hipersimple și hiperhipersimple; mai târziu au fost construite seturi maxime care sunt seturi r.e. astfel încât fiecare r.e. supersetul este fie o variantă finită a setului maxim dat, fie este co-finit. Motivația inițială a lui Post în studiul acestei rețele a fost de a găsi o noțiune structurală astfel încât fiecare mulțime care satisface această proprietate să nu fie nici î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 a aplicat în schimb metode prioritare; Harrington și Soare (1991) au găsit în cele din urmă o astfel de proprietate.

Automorfism problemsEdit

o altă întrebare importantă este existența automorfismelor în structurile teoretice recursive. Una dintre aceste structuri este aceea a mulțimilor recursiv enumerabile sub incluziune modulo diferență finită; în această structură, A este sub B dacă și numai dacă diferența de mulțimi B − A este finită. Mulțimile maxime (așa cum sunt definite în paragraful anterior) au proprietatea că nu pot fi automorfe la mulțimi non-maxime, adică dacă există un automorfism al mulțimilor enumerabile recursive sub structura menționată, atunci fiecare mulțime maximă este mapată la un alt set maxim. Soare (1974) a arătat că și inversul deține, adică fiecare două seturi maxime sunt automorfe. Deci mulțimile maxime formează o orbită, adică fiecare automorfism păstrează maximalitatea și oricare două mulțimi maxime sunt transformate una în cealaltă de un anumit automorfism. Harrington a dat un alt exemplu de proprietate automorfă: cea a seturilor creative, seturile care sunt multe-una echivalentă 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 gradelor Turing ale mulțimilor r.e. În ambele cazuri, Cooper susține că a construit automorfisme netriviale care mapează unele grade la alte grade; cu toate acestea, această construcție nu a fost verificată și unii colegi consideră că construcția conține erori și că întrebarea dacă există un automorfism netrivial al gradelor Turing este încă una dintre principalele întrebări nerezolvate în acest domeniu (Slaman și Woodin 1986, Ambos-Spies și Fejer 2006).

complexitatea Kolmogorov

domeniul complexității Kolmogorov și aleatorie algoritmică a fost dezvoltat în anii 1960 și 1970 de Chaitin, Kolmogorov, Levin, Martin-L și Solomonoff (numele sunt date aici în ordine alfabetică; o mare parte din cercetare a fost independentă, iar unitatea conceptului de aleatorie nu a fost înțeleasă la acea vreme). Ideea principală este de a considera o mașină Turing universală U și de a măsura complexitatea unui număr (sau șir) x ca lungimea celei mai scurte intrări p astfel încât u(p) să iasă x. Această abordare a revoluționat modalitățile anterioare de a determina când o secvență infinită (echivalent, funcția caracteristică a unui subset al numerelor naturale) este aleatorie sau nu prin invocarea unei noțiuni de aleatorie pentru obiecte finite. Complexitatea Kolmogorov a devenit nu numai un subiect de studiu independent, ci este aplicată și altor subiecte ca instrument de obținere a dovezilor.Există încă multe probleme deschise în acest domeniu. Din acest motiv, o conferință recentă de cercetare în acest domeniu a avut loc în ianuarie 2007 și o listă de probleme deschise este menținută de Joseph Miller și Andre Nies.

calculul Frecvențeiedit

această ramură a teoriei recursivității a analizat următoarea întrebare: pentru M și n fixe cu 0 < m < n, pentru care funcțiile A este posibil să se calculeze pentru orice n intrări diferite x1, x2, …, xn un tuplu de n numere y1, y2,…, yn astfel încât cel puțin M din ecuațiile a (xk) = yk sunt adevărate. Astfel de mulțimi sunt cunoscute sub numele de (m, n)-mulțimi recursive. Primul rezultat major în această ramură a teoriei recursivității este rezultatul lui Trakhtenbrot că un set este calculabil dacă este (m, n)-recursiv pentru unii m, N cu 2m > n. Pe de altă parte, seturile semirecursive ale lui Jockusch (care erau deja cunoscute informal înainte ca Jockusch să le introducă în 1968) sunt exemple de set care este (m, n)-recursiv dacă și numai dacă 2m < n + 1. Există nenumărate dintre aceste seturi și, de asemenea, unele seturi recursiv enumerabile, dar necalculabile de acest tip. 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 a oamenilor de știință ruși, acest subiect a devenit repopularizat în Occident prin teza lui Beigel privind interogările delimitate, care a legat calculul frecvenței de reducibilitățile delimitate menționate mai sus și alte noțiuni conexe. Unul dintre rezultatele majore a fost teoria Cardinalității lui Kummer, care afirmă că o mulțime A este calculabilă dacă și numai dacă există un n astfel încât un algoritm enumeră pentru fiecare tuplu de n numere diferite până la n multe opțiuni posibile ale cardinalității acestui set de n numere intersectate cu A; aceste alegeri trebuie să conțină adevărata cardinalitate, dar să lase cel puțin una falsă.

inferență inductivă

aceasta este ramura teoretică recursivă a teoriei învățării. Se bazează pe modelul de învățare al lui E. Mark Gold în limita din 1967 și a dezvoltat de atunci tot mai multe modele de învățare. Scenariul general este următorul: având în vedere o clasă S de funcții calculabile, există un cursant (adică funcțional recursiv) care emite pentru orice intrare a formularului (f(0),f(1),…, f(n)) o ipoteză. Un cursant m învață o funcție f dacă aproape toate ipotezele sunt același index e de f cu privire la o numerotare 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 de funcții recursiv enumerabile sunt învățabile în timp ce clasa REC a tuturor funcțiilor calculabile nu este învățabilă. Multe modele conexe au fost luate în considerare și, de asemenea, învățarea claselor de seturi recursiv enumerabile din date pozitive este un subiect studiat din lucrarea de pionierat a lui Gold din 1967 încoace.

generalizări ale calculabilității Turingedit

teoria recursivității include studiul noțiunilor generalizate ale acestui domeniu, cum ar fi reductibilitatea aritmetică, reductibilitatea hiperaritmetică și teoria recursivității în funcție de ecuație, așa cum este descris de Sacks (1990). Aceste noțiuni generalizate includ reducibilități care nu pot fi executate de mașinile Turing, dar sunt totuși generalizări naturale ale reductibilității Turing. Aceste studii includ abordări pentru a investiga ierarhia analitică care diferă de ierarhia aritmetică prin permiterea cuantificării peste seturi de numere naturale în plus față de cuantificarea peste numere individuale. Aceste zone sunt legate de teoriile de bine-ordonări și copaci; de exemplu, setul de toți indicii de recursiv (nonbinary) copaci fără ramuri infinite este completă pentru nivelul de 11 {\displaystyle \ Pi _{1}^{1}}

ierarhiei analitice. Atât Reductibilitatea Turing, cât și reductibilitatea hiperaritmetică sunt importante în domeniul teoriei descriptive eficiente a mulțimilor. Noțiunea și mai generală de grade de constructibilitate este studiată în teoria mulțimilor.

teoria calculabilității Continueedit

teoria calculabilității pentru calculul digital este bine dezvoltată. Teoria calculabilității este mai puțin bine dezvoltată pentru calculul analogic care apare în computerele analogice, procesarea semnalului analogic, electronica analogică, rețele neuronale și teoria controlului în timp continuu, modelat de ecuații diferențiale și sisteme dinamice continue (Orponen 1997; Moore 1996).