Teorija izračunljivosti (računarstvo)

Teorija izračunljivosti, takođe se zove i teorija rekurzije, je grana matematičke logike, informatike i teorije izračunljivosti je nastala 1930-ih sa proučavanjem izračunljivih funkcija i Tjuringovih stepena.

Osnovna pitanja upućena teoriji rekurzije su Šta to znači za funkciju nad prirodnim brojevima da bude izračunljiva? i Kako neizračunljive funkcije mogu biti klasifikovane u hijerarhiju baziranu na njihovom nivou neizračunljivosti?. Odgovori na ova pitanja vođena su do bogate teorije koja se i dalje aktivno istražuje. Polje je raslo da uključi i proučavanje generalisanih izračunljivosti i definitivnosti. Izum centralno kombinatornog objekta teorije rekurzije, nazvana Univerzalna Tjuringova mašina, prethodi i predodređuje izum modernih računara. Istorijski, proučavanja algoritamskih neodlučivih skupova i funkcija su bila motivisana raznim problemima u matematici koji su postali neodlučivi; na primer,problem reči za grupe i slično. Postoji nekoliko primena teorije na ostalim granama matematike koje se ne moraju koncentrisati na neodluvost. Rane primene uključuju proslavljenu Higmanovu teoriju ugrađivanja koja omogućava vezu između teorije rekurzije i teorije grupe, rezultati Majkl O. Rabina i Anatolija Malceva na algoritamskoj prezentaciji algebre, i rešenje negativnog u Hilbertovom desetom problemu. Skorašnje primene uključuju algoritamsku slučajnost, rezultat Soara, koji je uključio rekurzivnu-teoretsku metodu da bi rešio problem u algebarskoj geometriji, i nedavni rad Slamana na normalnim brojevima koji rešavaju problem u teoriji analitičkih brojeva.

Rekurzija teorija poklapa se sa teorijom dokaza, teorijom efektivno opisnog seta, teorijom modela i apstraktnom algebrom. Verovatno, teorija kompleksnosti je dete teorije rekurzije; obe teorije dele iste tehničke alate, to jest Tjuringova mašina. Teoretičari rekurzije u matematičkoj logici često proučavaju teoriju relativne izračunljivosti, smanjenje pojmova i stepena struktura opisanih u ovom članku. Ovo je u suprotnosti sa teorijom subrekurzivne hijerarhije, formalnih metoda i formalnih jezika koji je uobičajen u istraživanju teorije izračunljivosti u računarstvu. Postoji znatan stepen preklapanja u znanju i metodama između ove dve istraživačke zajednice; Međutim, nijedna snažna linija ne može se ispisati između njih. Na primer, parametrisanu kompleksnost izumeo je eoretičar kompleksnosti Majkl Felovs i teoretičar rekurzije Rod Dauni.

Izračunljivi i neizračunljivi skupovi

Teorija rekurzije nastala je 1930ih, sa radom Kurta Gedela, Alonza Čerča, Alana Tjuringa, Stefana Klinea i Emila Posta.

Dobijeni osnovni rezultati istraživača utvrdili su Tjuringovu izračunljivost kao tačnu formalizaciju neformalne ideje efektivnog računanja. Ove rezultate vodili su Stefana Klinea (1952) da kuje dva imena „Čerčova teza(Kline 1952:300) i „Tjuringova teza(Kline 1952:376). Danas se one često posmatraju kao jedna hipoteza, Čerč-Tjuringova teza, koje navode da je bilo koja funkcija koja je izračunljiva pomoću algoritama je i izračunljiva funkcija. Iako u početku skeptičan, 1946 Gedel tvrdi u prilog ovoj tezi:

„Tarski je naglasio u svojim predavanjima (i ja mislim pravedno) veliki značaj koncepta opšte rekurzivnosti (ili Tjuringove izračunljivosti). Čini mi se da je ovaj značaj veliki zbog činjenice da je sa ovim konceptom po prvi put dobijen uspeh u davanju apsolutne ideje ka interesantnoj epistomološkoj ideji, to jest, u nezavisnosti od izabranog formalizma.*

Sa definicijom efektivnog računanja su došli i prvi dokazi da su problemi u matematici koji ne mogu biti efektivno odlučeni. Čerč (1936a, 1936b) i Tjuring (1936), inspirisani tehnikama koje je koristio Gedel (1931) da dokaže svoju teoreme nepotpunosti, nezavisno je demonstrirao da Ajnšajdungsproblem nije efektivno odlučiv. Rezultat je pokazao da tamo nema algoritamskih procedura koje mogu pravilno odlučiti da li su proizvoljni matematički iskazi istiniti ili lažni.

Mnogi problemi u matematici su bili pokazani da budu neodlučivi nakon što su ovi početni primeri bili objavljeni. 1947, Markov i Post objavili su nezavisno radove pokazujući da problem reči u semigrupama ne može biti efektivno odlučiv. Proširenjem ovog rezultata, Petar Novikov i Vilijam Bun su nezavisno pokazali 1950ih da problem reči u grupama nije efektivno rešiv: nema efektivne procedure koja, dajući reč u konačno predstavljenoj grupi, će odlučiti proizvoljni element predstaljen rečju je element identiteta grupe. 1970-e, Juri Matijasevič je dokazao (koristeći rezultate Julije Robinson) Matijasevičovu teoremu, koja implicira da Hilbertov deseti problem  nema efektivno rešenje; ovaj problem pita proizvoljno da efektivna procedura odluči proizvoljno da li Diofantina jednačina preko celih brojeva ima rešenje u celim brojevima. Lista neodlučivih problema daje adekvatni primer problema sa neizračunljivim rešenjem.

Proučavanje koja matematička konstrukcija može biti efektivno izvedena je ponekad nazivana rekurzivna matematika; Priručnik rekurzivne matematike (Eršov i dr. 1998) pokriva mnoge poznate rezultate u ovoj oblasti.

Tjuringova izračunljivost

Glavni oblik izračunljivosti proučavan u teoriji rekurzije je predstavio Tjuring (1936). Za skup prirodnih brojeva je rečeno da bude izračunljiv skup(takođe nazvan i odlučiv, rekurzivan, ili Tjuring izračunljiv skup) ako postoji Tjuringova mašina koja, s obzirom na dati broj n, se zaustavlja sa izlazom 1 ako je n u skupu i zaustavlja se sa izlazom 0 ako n nije u skupu. Funkcija f iz prirodnih brojeva sami sebi su rekurzivni ili (Tjuring) izračunljiva funkcija ako postoji Tjuringova mašina koja, na izlazu n, se zaustavlja i vraća izlaz f(n), Upotreba Tjuringovih mašina ovde nije obavezna; postoje mnogi drugi modeli izračunavanja koji imaju iste izračunljive moći kao Tjuringove mašine; na primer μ-rekurzivna funkcija dobijena od primitivne rekurzije i μ operatora.

Terminologija za rekurzivne funkcije i skupove nije kompletno standardizovana. Definicija u pojmovima μ-rekurzivnih funkcija kao i različite denicije rekurzivnih funkcija Gedela vođena do tradicionalnog naziva rekurzivan za skupove i funkcije izračunljiv od strane Tjuringove mašine. Reč odlučiv potiče od nemačke reči Ajnšajdungsproblem koji je korišćen u originalnim radovima Tjuringa i ostalih. U savremenoj upotrebi, pojam „izračunljiva funkcija ima različite definicije: prema Kutlandu (1980), je parcijalno rekurzivna funkcija (koja može biti nedefinisana za neke ulaze), dok prema Soaru (1987) je totalno rekurzivna (ekvivalentna, opšte rekurzivna) funkcija. Ovaj članak prati drugi od ovih konvencija. Soar (1996) daje dodatne komentare o terminologiji.

Nije svaki skup prirodnih brojeva izračunljiv. Halting problem, koji je skup (opisa) Tjuringovih mašina koje se zaustavljaju na ulazu 0, je i dobro poznat primer neizračunljivog skupa. Postojanje mnogih neizračunljivih skupova proizilazi iz činjenice da postoje samo izračunljivo mnogo Tjuringovih mašina, i na taj način ovih mnogo samo izračunljivih skupova, ali postoje i neizračunljivo mnogo skupova prirodnih brojeva.

Iako Halting problem nije izračunljiv, moguće je da simulira izvršavanje programa i proizvede beskonačnu listu programa koje se zaustavljaju. Tako je Halting problem primer rekurzivno prebrojiv skup, skup koji može biti nabrojiv Tjuringovom mašinom (drugi uslovi za rekurzivno nabrojive uključuje i izračunljivo nabrojive i poluodlučive). Ekvivalntno, skup je rekurzivno nabrojiv ako i samo ako je raspon neke izračunljive funkcije. Rekurzivno nabrojivi skupovi, iako neodlučivi u opštem, su proučavani detaljno u teoriji rekurzije.

Oblasti istraživanja

Počevši sa teorijom rekurzivnih skupova i funkcija opisanih gore, oblast teorije rekurzije je rasla da obuhvati proučavanje mnogih blisko povezanih tema. One nisu nezavisne oblasti istraživanja: svaka od njih crpi ideje i rezultate od ostalih, i većina teoretičara rekurzije su upoznata sa većinom njih.

Relativna izračunljivost i Tjuringovi stepeni

Teorija rekurzije u matematičkoj logici je tradicionalno fokusirana ka relativnoj izračunljivosti, generalizacija Tjuringove izračunljivosti definisana je upotrebom  Proročke mašine, predstavljenu od strane Tjuringa (1939). Tjuringova proročka mašina je hipotetički uređaj koji, pored obavljanja postupaka regularne Tjuringove mašine, ima mogučnost da postavlja pitanja o proroku, koji je određen skupom prirodnih brojeva. Proročka mašina može samo postavljati pitanja oblika „Da li je n u proročkom skupu?. Svako pitanje će biti odmah odgovoreno pravilno, čak i ako proročki skup nije izračunljiv. Takva proročka mašina sa neizračunljivim prorokom će biti u stanju da izračuna skupove koje Tjuringova mašina bez proroka ne može.

Neformalno, skup prirodnih brojeva A je Tjuring smanjiv skupu B ako je tamo proročka mašina koja tačno govori koji brojevi su u A kada se pokrene sa B kao proročki skup (u ovom slučaju, skup A je takođe rekao da bude (relativno) izračunljiv iz B i rekurzivan u B). Ako je skup A Tjuring smanjiv skupu B i B je Tjuring smanjiv skupu A onda je za skupove rečeno da imaju isti Tjuringov stepen (takođe zvanih i kao stepen nerazrešivosti). Tjuringov stepen skupa daje preciznu meru koliko je skup neizračunljiv.

Prirodni primeri skupova koji nisu izračunljivi, uključujući i mnogo različitih skupova koji kodiraju varijante halting problema, imaju dva svojstva u zajedničkom:

1. Oni su rekurzivno prebrojivi, i
2. Svaki se može prevesti u drugu pomoću mnogo-jedan smanjenja. To, s obzirom na date skupove A i B, tamo je ukupna izračunljiva funskcija f takva da je  A = {x : f(x) ∈ B}. Za ove skupove se kaže da su mnogo-jedan ekvivalentni (ili m-ekvivalentni).

Mnogo-jedan smanjenja su „jača od Tjuringovog smanjenja: ako je skup A mnogo-jedan smanjiv skupu B, onda je A Tjuring smanjiv B, ali obrnuto se ne drži uvek. Iako su svi prirodni primeri neizračunljivih skupova mnogo-jedan ekvivalentni, moguće je konstruisati rekurzivno prebrojive skupove A i B takvih da je A Tjuring smanjiv ka B ali nije mnogo-jedan smanjiv ka B. Može se pokazati da je svaki rekurzivno prebrojiv skup mnogo-jedan smanjiv ka halting problemu, i takav halting problem je najviše komplikovani rekurzivno prebrojiv skup s obzirom ka mnogo-jedan smanjenju i Tjuring smanjenju. Post (1944) je pitao da li je svaki rekurzivno prebrojiv skup takođe i izračunljiv ili Tjuring ekvivalentan halting problemu, to jest, da li postoji rekurzivno prebrojiv skup sa Tjuringovim stepenom u sredini između njih dvoje.

Kao srednje rezultate, Post definiše prirodne tipove rekurzivnih prebrojivih skupova kao proste, hiperproste i hiperhiperproste. Post je pokazao da su ovi skupovi striktno između izračunljivih skupova i halting problema s obzirom na mnogo-jedan smanjenje. Post je takođe pokazao da su neki od njih striktno srednji pod drugim pojmovima smanjenja jači nego Tjuringovo smanjenje. Ali je Post ostavio otvorenim glavni problem postojanja rekurzivno prebrojivih skupova srednjeg Tjuringovog stepena; ovaj problem je postao poznat kao Postov problem. Nakon deset godina, Kline i Post su pokazali 1954.-e da je srednji Tjuringov stepen između izračunljivih skupova i halting problema, ali nisu uspeli da pokažu da bilo koji od ovih stepena sadrži rekurzivno prebrojiv skup. Vrlo brzo nakon toga, Fridberg i Mučnik nezavisno su rešili postojanje rekurzivno prebrojivih skupova srednjeg stepena. Ovaj revolucionarni rezultat je otvorio široko proučavanje Tjuringovog stepena rekurzivno prebrojivih skupova za koje se ispostavilo da sadrže veoma komplikovanu i netrivijalnu strukturu,

Postoje mnogi neizračunljivi skupovi koji nisu rekurzivno prebrojivi, i istraga Tjuringovih stepena svih skupova kao centralnu u teoriji rekurzije kao istraga rekurzivnih prebrojivih Tjuringovih stepena. Mnogi stepeni sa posebnim svojstvima su konstruisani: hiperimuni-slobodni stepeni gde svaka funkcija za izračunavanje relativna u odnosu na taj stepen je glavna od strane (nerelativizirajuće) izračunljive funkcije; visoki stepeni relativni onima koji mogu izračunati funkciju f koja dominira svaku izračunljivu funkciju g u smislu da postoji konstanta c u odnosu na g takvu da je g (h) < f (h) za sve h>c; slučajni stepeni sadže algoritamski slučajne skupove; 1-opšti stepeni 1-opštih skupova; i stepeni ispod halting problema limitiranih-rekurzivnih skupova.

Proučavanje slučajnih (ne nužno rekurzivno prebrojivih) Tjuringovih stepena uključuju i proučavanje Tjuringovog skoka. S obzirom na skup A, Tjuringov skok skupa A je skup prirodnih brojeva kodirajući rešenje halting problema za proročke Tjuringove mašine koje rade sa prorokom A. Tjuringov skok bilo kog skupa je uvek na višem Tjuringovom stepenu nego originalni skup, i Friburgova teorema pokazuje da bilo koji skup koji izračunava halting problem može biti dobijen kao Tjuringov skok drugog skupa. Postova teorema uspostavlja bliske veze između operacije Tjuringovog skoka i aritmetičke hijerarhije, koja je klasifikacija određenih podgrupa prirodnih brojeva baziranih na njihovim definisanostima u aritmetici.

Najskorije istraživanje Tjuringovih stepena je bilo fokusirano na strukturu skupa Tjuringovih stepena i skupa Tjuringovih stepena koji sadrže rekurzivno prebrojive skupove. Duboka teorema Šorea i Slamana (1999) navodi da funkcija mapiranja stepena h na stepen njegovog Tjuringovog skoka je definisana u delimičnom redosledu Tjuringovih stepena. Nedavno istraživanje Ambos Spajsa i Fejera (2006) daje pregled ovog istraživanja i istorijski napredak.

Ostala smanjenja

Stalna oblast istraživanja teorije rekurzije proučava odnose smanjenja ostalih osim Tjuringovog smanjenja. Post (1944) je predstavio nekoliko jakih smanjenja, tako nazvanih zato što one ulaze u istinitu-tabelu smanjenja. Tjuringova mašina implementira da će jaka smanjenja izračunati ukupnu funkciju bez obzira sa kojim je prorokom predstavljena. Slaba smanjenja su ona gde se proces smanjenja možda neće raskinuti za sve proroke; Tjuringovo smanjenje je jedan primer.

Jaka smanjenja uključuju:

Smanjenje jedan-jedan

A je jedan-jedan smanjivo (ili 1-smanjivo) ka B ako je tamo ukupna izračunljiva injektivna funkcija f takva da je svako n u A ako i samo ako je f (n) u B.

Smanjenje mnogo-jedan

Ovo je u suštini jedan-jedan smanjenje bez ograničenja da će f biti injektivno. A je mnogo-jedan smanjivo (ili m-smanjivo) ka B ako je tamo ukupna izračunljiva funkcija f takva da je svako n u A ako i samo ako je f (n) u B.

Smanjenje istina-tabele

A je istina-tabela smanjiva ka B ako je A Tjuring smanjiva ka B upotrebom proročke Tjuringove mašine koja izračunava ukupnu funkciju bez obzira na prorok koji je dat. Zbog kompaktnosti Kantor prostora, ovo je ekvivalentno tome da se kaže da smanjenje predstavlja jedinstvenu listu pitanja (zavisi jedino od ulaza) ka proroku istovremeno, i tada kada vide svoje odgovore moguće je da proizvedu izlaz bez dodatnih pitanja bez obzira na proročki odgovor početnim ulazima. Mnoge varijante istina-tabele smanjenja su takođe bile proučavane.

Dalja smanjenja (pozitivna, disjunkcivna, konjuktivna, linearna i njihove slabe i ograđene verzije) se razmatraju u članku Smanjenje (teorija rekurzije).

Glavno istraživanje o jakim smanjenjima je da uporede svoje teorije, kako za klasu svih rekurzivno prebrojivih skupova, kao i za klasu svih podgrupa prirodnih brojeva. Osim toga, odnosi između smanjenja su bili priučavani. Na primer, poznato je da je svaki Tjuringov stepen takođe istina-tabela stepena ili je ujedinjenje beskonačno mnogo istina-tabela stepena.

Smanjenja slabija nego Tjuringovo smanjenje (to je, smanjenja koja podrazumevaju Tjuringovo smanjenje) su takođe proučavana. Najpoznatija su aritmetičko smanjenje i hiperaritmetičko smanjenje. Ova smanjenja su usko povezana sa definisanostima u odnosu na standardni model aritmetike.

Rajsova teorema i aritmetička hijerarhija

Rajs je pokazao da za svaku netrivijalnu klasu C (koje sadrže neke, ali ne svi ponovni skupovi) indeksni skup E = {e: ETH skup Ve je u C} ima svojstvo da ili halting problem ili njen komplement je mnogo-jedan smanjiv na E, to jest, može da se preslika koristeći mnogo-jedan smanjenje u E (vidi Rajsovu teoremu za više detalja). Ali, mnogi od ovih indeksnih skupova su još komplikovaniji nego halting problem. Ova vrsta skupova  može biti klasifikovana korišćenjem aritmetičke hijerarhije. Na primer, indeksni skup FIN klase svih konačnih skupova je na nivou Σ2, indeksni skup REC klase svih rekurzivnih skupova je na nivou Σ3, indeksni skup COFIN svih  skoro konačnih skupova je takođe na nivou Σ3 i indeksni skup COMP klase svih Tjuring potpunih skupova Σ4. Ovi hijerarhijski nivoi su induktivno definisani, Σn+1 sadrži samo sve skupove koji su rekurzivno prebrojivi u odnosu na Σn; Σ1 sadrži rekurzivno prebrojive skupove. Indeksni skupovi dati ovde su čak i potpuni za svoje nivoe, to jest, svi skupovi u ovim nivoima mogu biti mnogo-jedan smanjeni na datim indeksnim skupovima.

Obrnuta matematika

Program obrnute matematike pita koji skup-postojanja aksioma su neophodni da se dokažu određene teoreme matematike u podsistemima aritmetike drugog reda. Ovo proučavanje je inicirao Harvej Fridman i bilo je proučavano u detalje od  strane Stefana Simpsona i drugih; Simpson (1999) daje detaljnu raspravu programa. Skup-postojanja aksioma u pitanju odgovaraju neformalno aksiomima govoreći da je moćan skup prirodnih brojeva zatvoren pod različitim smanjenjem pojmova. Najslabiji takav aksiom proučavan u obrnutoj matematici je rekurzivno razumevanje, koje navodi da je moćan skup na prirodnim zatvoren pod Tjuringovim smanjenjem.

Numeracija

Numeracija je nabrajanje funkcija; ima dva parametra, E i H i izlaze vrednosti e-te funkcije u numeraciji na ulazu h. Numeracije mogu biti delimično-rekurzivne iako su neki od njenih članova ukupno rekurzivne, to jest, izračunljive funkcije. Dopustljive numeracije su one u kojima se sve druge mogu prevesti. Fridbergova numeracija (nazvana po svom pronalazaču) je jedan-jedan numeracija svih parcijalnih-rekurzivnih funkcija; neophodno je neprihvatljiva numeracija Kasnija istraživanja bavila su se i sa numeracijama druge klase kao klase rekurzivno prebrojivih skupova. Gončarov je otkrio na primer klasu rekurzivno prebrojivih skupova za koje numeracije spadaju u dve klase tačno u vezi sa rekurzivnim izomorfizmima.

Prioritetni metod

Za dalje objašnjenje, pogledajte odeljak Postov problem i metod prioriteta u članu Tjuringov stepen.

Postov problem je rešen sa metodom koja se zove metod prioriteta; dokaz koristeći ovaj metod se zove prioritetna rasprava. Ova metoda se uglavnom koristi za izgradnju rekurzivno prebrojivih skupova sa određenim osobinama. Da biste koristili ovaj metod, željene osobine skupa koji će se graditi su raskinute u beskrajnom spicku ciljeva, poznatih kao zahtevi, tako da zadovoljavaju sve uslove koje će izazvati skup konstruisan tako željenih osobina. Svaki zahtev je dobio prirodan broj koji predstavlja prioritet zahteva; pa 0 je dodeljen najvažniji prioritet, 1 je druga najvažnija, i tako dalje. Skup je zatim izgrađen u fazama, svaka faza pokušava da zadovolji jedan od više zahteva bilo dodavanjem brojeva setu ili zabrani brojeva iz skupa, tako da će konačni skup zadovoljiti zahteve. Može se desiti da će zadovoljenje jednog uslova izazvati ostale da postanu nezadovoljni; prioritet se koristi da odluči šta da rade u takvom događaju.

Prioritetni argumenti su bili zaposleni da reše mnoge probleme u teoriji rekurzije, i oni su klasifikovani u hijerarhiji na osnovu njihove složenosti (Soar 1987). Zbog složenih prioritetnih argumenata mogu biti tehničke i teške za praćenje, to se tradicionalno smatra poželjnim da dokaže rezultate bez prioritetnih argumenata, ili da vidimo da li rezultati dokazani prioritetnim argumentima mogu biti dokazani i bez njih. Na primer, Kumer je objavio rad na dokazu za postojanje Fridbergove numeracije bez metode prioriteta.

Rešetka rekurzivnih setova nabrajanja

Kada je Post definisao pojam jednostavnog skupa kao rekurzivno prebrojiv skup sa beskonačnim dodacima koji ne sadrži nikakav beskrajno rekurzivno prebrojiv skup set počeo je da proučava strukturu rekurzivno prebrojivih skupova pod inkluzijom. Ova rešetka je postala dobro proučena struktura. Rekurzivni skupovi mogu se definisati u ovoj strukturi osnovnim rezultatom da je skup rekurzivan ako i samo ako su skup i njegova dopuna rekurzivno prebrojivi. Beskonačni rekurzivno prebrojivi skupovi su uvek beskrajne rekurzivne podgrupe; ali sa druge strane, jednostavni skupovi postoje, ali nemaju skoro konačan rekurzivni nadskup. Post (1944) je predstavio već hiperproste i hiperhiperproste skupove; Kasnije maksimalni skupovi su izgrađeni koji su ponovo postavljeni tako da svaki rekurzivno prebrojiv nadskup je bila konačna varijanta datog maksimalnog skupa ili je ko-konačna. Postova originalna motivacija u proučavanju ove rešetke je bila da se pronađe strukturalni pojam takav da svaki skup koji zadovoljava ovaj objekat nije ni u Tjuringovom stepenu rekurzivnih skupova ni u Tjuringovom stepenu halting problema. Post nije našao takvu imovinu i rešenje za njegov problem primenjuje metode prioritetnih umesto toga; Harington i Soare (1991) su našli na kraju takve osobine.

Automorfzni problemi

Drugo važno pitanje jeste postojanje automorfizma u rekurzivno-teoretskim konstrukcijama. Jedna od tih struktura je da je jedan od rekurzivno prebrojivih skupova po uključivanju modula konačnih razlika; u ovoj strukturi, A je ispod B ako i samo ako je skup razlika B - A konačna. Maksimalni skupovi (kao što je definisano u prethodnom pasusu) imaju osobinu da ne mogu biti automorfne ka nemaksimalnim skupovima, to jest, ako postoji automorfizam rekurzivnih prebrojivih skupova po strukturi upravo pomenuti, onda svaki maksimalni skup se preslikava na drugi maksimalni skup. Soare (1974) je pokazao da se i obrnuto drži, to jest, svaka dva maksimalna skupa su automorfna. Tako maksimalni setovi formiraju orbitu, to jest, svaki automorfizam čuva maksimalnost i bilo koja dva maksimalna skupa se transformišu jedan u drugi pomoću nekog automorfizma. Harington je dao još jedan primer jedne automorfne imovine: da kreativni skupovi, skupovi koji su mnogi-jedan ekvivalentni halting problemu.

Pored rešetke rekurzivno prebrojivih skupova, automorfizmi su takođe proučavani za strukture Tjuringovih stepena svih skupova, kao i za strukture Tjuringovih stepena rekurzivno prebrojivih skupova. U oba slučaja, Kuper tvrdi da su konstruisali netrivijalne avtomorfizme koji mapiraju neke stepene prema drugim stepenima; ova konstrukcija, međutim, nije bila verifikovana i neke kolege veruju da izgradnja sadrži greške i da je pitanje da li postoji netrivijalni automorfizmi Tjuringovih stepena i dalje jedno od glavnih nerešenih pitanja u ovoj oblasti (Slaman i Vudin 1986, Ambos Spajs i Fejer 2006).

Kolmogorova kompleksnost

Oblast Kolmogorove složenosti i algoritamske slučajnosti je razvijena tokom 1960-ih i 1970-ih od strane Čaitina, Kolmogorova, Levina, Martin-Lofa i Solomonofa (imena su ovde dati po abecednom redu, veliki deo istraživanja je nezavisan, a jedinstvo koncepta slučajnosti nije tada shvaćeno). Osnovna ideja je da se razmotri univerzalna Tjuringova Mašina U i za merenje složenosti broja (ili stringa) h kao dužina najkraće ulaza p takvog da U(p) izlaza h. Ovaj pristup revolucirao je ranije načine da se odredi kada je beskonačni niz (ekvivalentno, karakteristična funkcija podskup prirodnih brojeva) slučajan ili ne pozivajući se na ideju o slučajnosti konačnih objekata. Kolmogorova kompleksnost je postala ne samo predmet nezavisnih proučavanja, već se takođe primenjuje i na druge predmete kao sredstvo dobijanja dokaza. Postoji još mnogo otvorenih problema u ovoj oblasti. Iz tog razloga, nedavno istraživanje konferencija u ovoj oblasti održan je u januaru 2007. godine i spisak otvorenih problema je održavanod strane Jozefa Milera i Andrea Niza.

Učestalost računanja

Ova grana teorije rekurzije analizirala je sledeće pitanje: Za fiksne m i n sa 0 <m <n, za koje je funkcija A moguća za izračunavanje za bilo koje drugačije n ulaza H1, H2..., Hn torka od n brojeva U1, U2..., Un tako da bar m jednačine A (Hk) = Uk su istinite. Takvi skupovi su poznati kao (m, n) -rekurzivni skupovi. Prvi veliki rezultat u ovoj grani teorije rekurzije je Traktenbrotov rezultat koji kaže da je skup izračunljiv ako je (m, n) -rekurzivno za neko m, n sa 2m> n. S druge strane, Jokušovi semirekurzivni skupovi su (koji su već neformalno poznati pre nego što ih je Jokuš uveo 1968) primeri skupa koji je (m, n) -rekurzivni ako i samo ako je 2m <n + 1. Postoje mnogo neizračunljivo ovih skupova, kao i nekih rekurzivno prebrojivih ali neizračunljivih skupova ove vrste. Kasnije, Degtev je uspostavio hijerarhiju rekurzivno prebrojivih skupova koji su (1, n + 1) -rekurzivni, ali ne (1, n) -rekurzivni. Posle duge faze istraživanja ruskih naučnika, ova tema postala ponovo popularizovana na zapadu od strane Bigelove teze na ograđene upite, koji je povezivao frekvencionalno izračunavanje do navedenih ograničenih smanjenja i drugih srodnih pojmova. Jedan od glavnih rezultata je Kumerova Kardinalna teorija kojom se navodi da je skup A izračunljiv ako i samo ako postoji n, takvo da su neki algoritam prebrojava za svaku torku od n različitih brojeva do N mnogo mogućih izbora kardinalnosti ovog skupa od N brojeva ispresecan sa A; ovi izbori moraju da sadrže prave kardinalnosti, ali izostave bar jedno lažno jedan.

Induktivni zaključak

Ovo je rekurzibno-teorijska grana teorije učenja. On je zasnovan na Goldovom modelu učenja u roku od 1967. godine i razvijala od tada više i više modela učenja. Generalni scenario je sledeći: S obzirom na klasu S izračunljivih funkcija, postoji učenik (koji je, rekurzivno funkcionalan) koji izlazi za bilo koji ulaz oblika (f (0), f (1)..., F (N)) hipoteza. Učenik M saznaje funkciju F ako su skoro sve hipoteze isti indeks E od F u vezi sa prethodno dogovorenom prihvatanju numeracije svih izračunljivih funkcija; M saznaje S ako M saznaje svaku f u S. Osnovni rezultati su da su sve rekurzivno prebrojive klase funkcije učljive dok klasa REC svih izračunljivih funkcija nije. Mnogi srodni modeli su smatrali kao i takođe učenje klasa rekurzivno prebrojivih skupova iz pozitivnih podataka je tema proučavanja Goldovog pionirskog rada u 1967. pa nadalje.

Generalizacije Tjuringove izračunljivosti

Teorija rekurzije obuhvata proučavanje uopštenih pojmova iz ove oblasti, kao što su aritmetičko smanjenje, hiperaritmetičko smanjenje i  α-rekurzivne teorije, kao što je opisano od strane Saksa (1990). Ovi generalisani pojmovi uključuju smanjenja koja se ne mogu izvršavati Tjuringovim mašinama, ali su ipak prirodne generalizacije o Tjuringovom smanjenju. Ove studije obuhvataju pristupe da se ispita analitička hijerarhija koja se razlikuje od aritmetičke hijerarhije dozvoljavajući kvantifikaciju u preko skupova prirodnih brojeva u dodatku kvantifikacije preko pojedinih brojeva. Ove oblasti su povezane sa teorijama dobro-poređanih i stabala; Na primer skup svih indeksa rekurzivnih (nebinarnih) stabala, bez beskonačnih grana je kompletan za nivo $\Pi _{1}^{1}$ analitičke hijerarhije. Tjuringovo smanjenje i hiperaritmetičko smanjenje su važni u oblasti teorije efektivno opisanog skupa. Još više opšti pojam stepena izračunljivosti je proučavana u teoriji skupova.

Kontinuirana teorija izračunljivosti

Teorija Izračunljivosti za digitalno izračunavanje je dobro razvijena. Teorija izračunljivosti je manje razvijena za analogno izračunavanje koje se javlja kod analognih računara, obrade analognog signala, analogne elektronike, neuronske mreže i teorije kontrole kontinuiranog vremena, modeliranu od strane diferencijalnih jednačina i kontinuiranih dinamičkih sistema (Orponen 1997; Mur 1996).

Odnosi između definitnosti, dokaza i izračunljivosti

Postoje bliski odnosi između Tjuringovog stepena skupa prirodnih brojeva i teškoća (u smislu aritmetičke hijerarhije) definisanja tog skupa koristeći formulu prvog reda. Jedan takav odnos je precizno obrazložen Postovom teoremom. Slabija veza je pokazana od strane Kurta Gedela u dokazima njegove teoreme potpunosti i teoreme nepotpunosti. Gedelovi dokazi pokazuju da je skup logičkih posledica efikasne teorije prvog reda rekurzivno prebrojiv skup, i da, ako je teorija dovoljno jaka ovaj skup će biti neizračunljiv. Slično tome, Tarskijeva teorema nedefinisanosti može se tumačiti u smislu definisanosti i u smislu izračunljivosti.

Teorija rekurzije je takođe povezana sa aritmetikom drugog reda, formalne teorije prirodnih brojeva i skupova prirodnih brojeva. Činjenica da su neki skupovi izračunljivi ili relativno izračunljivi često podrazumeva da ovi skupovi mogu biti definisani u slabim podsistemima drugog reda aritmetike. Program obrnute matematike koristi ove podsisteme za merenje neizračunljivosti u veoma dobro poznatim matematičkim teoremama. Simpson (1999) razmatra mnoge aspekte aritmetike drugog reda i obrnute matematike.

Oblast teorije dokazivanja obuhvata proučavanje aritmetike drugog reda i Peano aritmetike, kao i formalne teorije prirodnih brojeva slabijih od Peano aritmetike. Jedan način klasifikacije snage ovih slabih sistema je karakterizacijom koja izračunljiva funkcija sistema može dokazati da je ukupna (vidi Fairtlog i Vajner (1998)). Na primer, u primitivnoj rekurzivnoj aritmetici bilo koja izračunljiva funkcija koja je dokazivo ukupna je zapravo primitivno rekurzivna, dok Peano aritmetika pokazuje da funkcije kao Akermanova funkcija, koje nisu primitivno rekurzivne, su ukupne. Nije svaka ukupna izračunljiva funkcija i dokazivo ukupna u Peano aritmetici, međutim; primer takve funkcije obezbeđuje Gudštajnova teorema.

Naziv predmeta

Oblast matematičke logike koja se bavi izračunljivošću i njenim generalizacijama je nazvana "teorija rekurzije" od svojih ranih dana. Robert I. Soare, istaknuti istraživač u oblasti, je predložio (Soare 1996) da oblast treba nazvati "teorija izračunljivosti" umesto. On tvrdi da Tjuringova terminologija koristi reč "izračunljiv" je prirodnije i šire shvaćena od terminologije koja koristi reč "rekurzivna" koju je uveo Kline. Mnogi savremeni istraživači su počeli da koriste ovu alternativnu terminologiju. Ovi istraživači takođe koriste terminologiju, kao što su delimične izračunljive funkcije i izračunljivi prebrojivi (IP) skupovi umesto delimično rekurzivne funkcije i rekurzivno prebrojivi (RP) skupovi. Nisu svi istraživači bili ubeđeni, međutim, kako je objasnio Fortnov i Simpson. Neki komentatori tvrde da su imena teorija rekurzije i teorija izračunljivosti ne prenose činjenicu da je većina objekata ispitivanih u teoriji rekurzije nisu izračunljivi.

Rodžers (1967) je predložio da je ključna imovina teorije rekurzije da njeni rezultati i strukture moraju biti invarijantni pod izračunljivim bijekcijama na prirodnim brojevima (ova sugestija oslanja se na idejama Erlangen programa u geometriji). Ideja je da se za izračunavanje bijekcije samo preimenuje brojevi u skupu, umesto što ukazuju na bilo koji objekat u skupu, kao i što rotacija euklidskog aviona ne menja geometrijski aspekt linija nacrtanih na njemu. Od bilo koja dve nekonačno izračunljiva skupa su vezana za izračunavanje bijekcije, ovaj predlog identifikuje sve beskrajne izračunljive skupove (konačni izračunljivi skupovi su smatrale kao trivijalne). Prema Rodžersu, skupovi interesa u teoriji rekurzije su neizračunljivi skupovi, podeljeni u klase ekvivalencije za izračunljive bijekcije  prirodnih brojeva.

Profesionalne organizacije

Glavna profesionalna organizacija za teoriju rekurzije je Udruženje za Simboličku Logiku, koja ima nekoliko istraživačkih konferencija svake godine. Interdisciplinarno istraživačko Udruženje Izračunljivosti u Evropi (CiE) organizuje niz godišnjih konferencija.

Vidi još

• Rekurzija (kompjuterske nauke)
• Logika izračunljivosti
• Transizračunljiv problem

Literatura

Preddiplomski tekstovi

• S. B. Cooper (2004). Computability Theory. Chapman & Hall/CRC. ISBN 978-1-58488-237-4. 
• N. Cutland (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN 978-0-521-29465-2. 
• Y. Matiyasevich (1993). Hilbert's Tenth Problem. MIT Press. ISBN 978-0-262-13295-4. 

Napredni tekstovi

• S. Jain, D. Osherson, J. Royer and A. Sharma (1999). Systems that learn, an introduction to learning theory, second edition. Bradford Book. ISBN 978-0-262-10077-9. CS1 održavanje: Višestruka imena: spisak autora (veza)
• S. Kleene (1952). Introduction to Metamathematics. North-Holland (11th printing; 6th printing added comments). ISBN 978-0-7204-2103-3. 
• M. Lerman (1983). Degrees of unsolvability. Perspectives in Mathematical Logic, Springer-Verlag. ISBN 978-3-540-12155-8. 
• Nies, Andre (2009). Computability and Randomness. Oxford University Press. 447 pages. ISBN 978-0-19-923076-1. .
• P. Odifreddi (1989). Classical Recursion Theory. North-Holland. ISBN 978-0-444-87295-1. 
• P. Odifreddi (1999). Classical Recursion Theory, Volume II. Elsevier. ISBN 978-0-444-50205-6. 
• H. Rogers, Jr. The Theory of Recursive Functions and Effective Computability. second edition 1987, MIT Press. ISBN 978-0-262-68052-3.  (paperback). . 1967. ISBN 978-0-07-053522-0. 
• G Sacks (1990). Higher Recursion Theory. Springer-Verlag. ISBN 978-3-540-19305-0. 
• S. G. Simpson (1999). Subsystems of Second Order Arithmetic. Springer-Verlag. ISBN 978-3-540-64882-6. 
• R. I. Soare (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Springer-Verlag. ISBN 978-0-387-15299-8. 

Anketni radovi  i zbirke

• K. Ambos-Spies and P. Fejer, 2006. "Degrees of Unsolvability." Unpublished preprint.
• J. Barwise, North-Holland . (1977). H. Enderton, 1977. "Elements of Recursion Theory." Handbook of Mathematical Logic, edited. North-Holland Publishing Company. str. 527–566. ISBN 978-0-7204-2285-6. 
• Y. L. Ershov; S. S. Goncharov; A. Nerode; J. B. Remmel (1998). Handbook of Recursive Mathematics. North-Holland. ISBN 978-0-7204-2285-6. 
• M. Fairtlough and S. Wainer, 1998. "Hierarchies of Provably Recursive Functions". In Handbook of Proof Theory, edited by S. Buss, Elsevier (1998).
• Soare, Robert I. (1996). „Computability and Recursion”. Bulletin of Symbolic Logic. 2 (3): 284—321. JSTOR 420992. S2CID 5894394. doi:10.2307/420992. 

Istraživački radovi i zbirke

• Burgin, Mark; Klinger, Allen (2004). „Experience, generations, and limits in machine learning”. Theoretical Computer Science. 317 (1/3): 71—91. doi:10.1016/j.tcs.2003.12.005. 
• Church, Alonzo (1936). „An Unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics. 58 (2): 345—363. JSTOR 2371045. doi:10.2307/2371045. 
• A. Church, 1936b. "A note on the Entscheidungsproblem." . Journal of Symbolic Logic. 1.  , n. 1, and. . 3.  , n. 3. Reprinted in "The Undecidable", M. Davis ed., 1965.
• M. Davis, ur. (2004) [1965]. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven. Reprint, Dover. ISBN 978-0-486-43228-1. 
• Friedberg, Richard M. (1958). „Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication”. The Journal of Symbolic Logic. 23 (3): 309—316. JSTOR 2964290. S2CID 25834814. doi:10.2307/2964290. .
• Gold, E. Mark (1967), Language Identification in the Limit (PDF) Gold, E Mark (1967). „Language identification in the limit”. Information and Control. 10 (5): 447—474. doi:10.1016/S0019-9958(67)91165-5. 
• 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, volume 88, pages 10242—10246.
• C. Jockusch jr, "Semirecursive sets and positive reducibility", Trans. Amer. Math. Soc. Trans. Amer. Math. Soc. 137: 420—436. 1968. 
• S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability." . Annals of Mathematics. 2 (59): 379—407. 1954.  .
• Moore, Cristopher (1996). „Recursion theory on the reals and continuous-time computation”. Theoretical Computer Science. 162: 23—44. CiteSeerX 10.1.1.6.5519 . doi:10.1016/0304-3975(95)00248-0. 
• Myhill, John (1956). „Problems in symbolic logic”. The Journal of Symbolic Logic. 21 (2): 215—220. S2CID 123260425. doi:10.1017/S002248120008525X. .
• Orponen, P. (1997). „A Survey of Continuous-Time Computation Theory”. Advances in Algorithms, Languages, and Complexity. str. 209—224. CiteSeerX 10.1.1.53.1991 . ISBN 978-1-4613-3396-8. doi:10.1007/978-1-4613-3394-4_11. 
• Post, Emil L. (1944). „Recursively enumerable sets of positive integers and their decision problems”. Bulletin of the American Mathematical Society. 50 (5): 284—316. S2CID 2560730. doi:10.1090/S0002-9904-1944-08111-1. 
• Post, Emil L. (1947). „Recursive Unsolvability of a Problem of Thue”. Journal of Symbolic Logic. 12 (1): 1—11. JSTOR 2267170. S2CID 30320278. doi:10.2307/2267170. . Reprinted in "The Undecidable", M. Davis ed., 1965.
• Shore, Richard A.; Slaman, Theodore A. (1999). „Defining the Turing Jump”. Mathematical Research Letters. 6 (6): 711—722. ISSN 1073-2780. doi:10.4310/mrl.1999.v6.n6.a10. 
• T. Slaman and W. H. Woodin, 1986. "Definability in the Turing degrees." Illinois J. Math.. Illinois J. Math. 30 (2): 320—334. 1986. 
• Soare, Robert I. (1974). „Automorphisms of the Lattice of Recursively Enumerable Sets Part I: Maximal Sets”. Annals of Mathematics. 100 (1): 80—120. JSTOR 1970842. doi:10.2307/1970842. .
• A. Turing (1937). „On computable numbers, with an application to the Entscheidungsproblem” (PDF). Proceedings of the London Mathematics Society: 230—265. S2CID 73712. doi:10.1112/plms/s2-42.1.230. . Corrections. . 43: 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. . 45: 161—228.  . Reprinted in "The Undecidable", M. Davis ed., 1965.

Spoljašnje veze

• Association for Symbolic Logic homepage
• Computability in Europe homepage Arhivirano na sajtu Wayback Machine (17. februar 2011)
• Webpage on Recursion Theory Course at Graduate Level with approximately 100 pages of lecture notes
• German language lecture notes on inductive inference