Computability theory

alkaen teorian rekursiiviset asetetaan ja tehtävät kuvattu edellä, alalla rekursioteoria on kasvanut sisällyttää tutkimuksen monia läheistä aiheista. Nämä eivät ole itsenäisiä tutkimusaloja: jokainen näistä alueista ammentaa ideoita ja tuloksia toisista, ja useimmat rekursioteoreetikot tuntevat suurimman osan niistä.

suhteellinen laskettavuus ja Turing degreesEdit

Rekursioteoria matemaattisessa logiikassa on perinteisesti keskittynyt suhteelliseen laskettavuuteen, Turingin (1939) oracle Turingin koneiden avulla määriteltyyn Turingin laskettavuuden yleistykseen. Oraakkeli Turingin kone on hypoteettinen laite, joka tavallisen Turingin koneen toimien suorittamisen lisäksi pystyy esittämään kysymyksiä oraakkelilta, joka on tietty luonnollisten lukujen joukko. Oraakkelikone saa esittää vain muotoa ” onko n oraakkelijoukossa?”. Jokaiseen kysymykseen vastataan heti oikein, vaikka oraakkelijoukko ei olisikaan laskettavissa. Näin oraakkelikone, jolla on epäluotettava oraakkeli, pystyy laskemaan joukkoja, joita Turingin kone ilman oraakkelia ei pysty laskemaan.

epävirallisesti luonnollisten lukujen joukko A on Turing reducible joukoksi B, jos on olemassa oraakkelikone, joka oikein kertoo, ovatko numerot A: ssa, kun ajetaan B: n kanssa oraakkelijoukkona (tässä tapauksessa joukon A sanotaan myös olevan (suhteellisen) laskettavissa B: stä ja rekursiivinen B: ssä). Jos joukko A on Turing reducible joukko B ja B on Turing reducible joukko A sitten asetetaan sanotaan olevan sama Turing aste (kutsutaan myös aste unsolvability). The Turing aste joukko antaa tarkka toimenpide, kuinka uncomputable joukko on.

luonnollisilla esimerkeillä joukoista, jotka eivät ole laskettavissa, mukaan lukien monet erilaiset joukot, jotka koodaavat pysäyttämisongelman variantteja, on kaksi yhteistä ominaisuutta:

1. ne ovat rekursiivisesti lueteltuja, ja
2. jokainen voidaan kääntää moneen kertaan pelkistämällä. Toisin sanoen, kun otetaan huomioon tällaiset joukot A ja B, on olemassa yhteensä laskennallinen funktio f siten, että A = {x:f (x) ∈ b}. Näitä joukkoja sanotaan olevan monta-yksi ekvivalentti (tai m-ekvivalentti).

monen yhden vähennykset ovat” vahvempia ” kuin Turingin vähennykset: jos joukko A on monen yhden reduktiivinen joukoksi B, niin A on Turingin reduktiivinen B: ksi, mutta käänteisluku ei aina pidä. Vaikka luonnolliset esimerkit ei-Computable asetetaan ovat kaikki monet-yksi vastaava, se on mahdollista rakentaa rekursiivisesti enumerable asetetaan A ja B siten, että A on Turing reducible, B mutta ei monta-yksi reducible, B. Voidaan osoittaa, että jokainen recursively enumerable joukko on monta-yksi reducible, pysäyttäminen ongelma, ja siten pysäyttäminen ongelma on kaikkein monimutkainen recursively enumerable asettaa osalta monet-yksi reducibility ja osalta Turing reducibility. Post (1944) kysyi, onko jokainen recursively enumerable joukko on joko computable tai Turing vastaa pysäyttäminen ongelma, eli onko Ei recursively enumerable asettaa kanssa Turing aste väli näiden kahden.

välituloksina Post määritteli rekursiivisesti enumeroituvien joukkojen luonnolliset tyypit, kuten yksinkertaiset, hypersimple – ja hyperhypersimple-joukot. Post osoitti, että nämä sarjat ovat tiukasti välillä computable asetetaan ja pysäyttäminen ongelma suhteessa monet-yksi reducibility. Post osoitti myös, että jotkut niistä ovat tiukasti välituotetta muiden reducibility käsitteitä vahvempi kuin Turing reducibility. Mutta Post vasemmalle auki suurin ongelma olemassaolon recursively enumerable sarjoiksi väli Turing aste; tämä ongelma tuli tunnetuksi Postin ongelma. Kymmenen vuoden kuluttua, Kleene ja Post osoitti vuonna 1954, että on olemassa väli Turing astetta välillä kuin computable asetetaan ja pysäyttäminen ongelma, mutta ne eivät osoita, että jokin näistä asteista sisältää rekursiivisesti enumerable asettaa. Hyvin pian tämän jälkeen, Friedberg ja Muchnik itsenäisesti ratkaista Post ongelma perustamalla olemassaolo recursively enumerable sarjoiksi väli astetta. Tämä uraauurtava tulos avasi laajan tutkimuksen Turing astetta, recursively enumerable asetetaan, joka osoittautui hallussaan hyvin monimutkainen ja ei-triviaali rakenne.

on olemassa laskemattomasti monia sarjoja, jotka eivät ole rekursiivisesti enumeroituvia, ja kaikkien sarjojen Turingin asteiden tutkiminen on rekursioteoriassa yhtä keskeistä kuin rekursiivisesti enumeroituvien Turingin asteiden tutkiminen. Konstruoitiin monta astetta, joilla oli erityisiä ominaisuuksia: hyperimmune-free-astetta, jossa jokainen funktio, joka on laskettavissa suhteessa kyseiseen asteeseen, on majorized by (unplativized) computable function; korkeat asteet, joihin suhteutettuna voidaan laskea funktio f, joka hallitsee jokaista laskettavissa olevaa funktiota g siinä mielessä, että on olemassa vakio C riippuen g siten, että g(x) < f(x) kaikille x > c; satunnaiset asteet, jotka sisältävät algoritmisesti satunnaisia joukkoja; 1-Yleiset asteet 1-Yleiset joukot; ja asteet, jotka ovat alle raja-rekursiivisten joukkojen pysäyttämisongelman.

mielivaltaisten (ei välttämättä rekursiivisesti lueteltujen) Turingin asteiden tutkimus liittyy Turingin hypyn tutkimiseen. Kun otetaan huomioon joukko a, Turingin hyppy A on joukko luonnollisia lukuja, jotka koodaavat ratkaisun pysäyttämisongelmaan oracle Turingin koneille, jotka toimivat oracle A: n kanssa.minkä tahansa joukon Turingin hyppy on aina korkeampi kuin alkuperäisen joukon, ja Friedburgin lause osoittaa, että mikä tahansa joukko, joka laskee Pysäyttämisongelman, voidaan saada toisen joukon Turingin hyppynä. Postin lause luo Turingin hyppyoperaation ja aritmeettisen hierarkian välille läheisen suhteen, joka on luonnollisten lukujen tiettyjen osajoukkojen luokittelu, joka perustuu niiden määritettävyyteen aritmetiikassa.

monet viimeaikaiset tutkimukset Turingin asteista ovat keskittyneet Turingin asteiden kokonaisrakenteeseen ja Turingin asteiden joukkoon, jotka sisältävät rekursiivisesti lueteltavia sarjoja. A deep theorem of Shore and Slaman (1999) toteaa, että funktio, joka kartoittaa asteen x sen Turing-hypyn asteelle, on määriteltävissä Turingin asteiden osittaisessa järjestyksessä. Ambos-Spies and Fejerin tuore tutkimus (2006) antaa yleiskuvan tästä tutkimuksesta ja sen historiallisesta etenemisestä.

muut reducibilitiesEdit

jatkuva tutkimusalue rekursio teoriassa tutkimukset reducibility suhteita muita kuin Turing reducibility. Post (1944) käyttöön useita vahvoja reducibilities, niin nimetty, koska ne merkitsevät totuus-taulukon reducibility. Vahvan reducibiliteetin toteuttava Turingin kone laskee kokonaisfunktion riippumatta siitä, minkä oraakkelin kanssa se esitetään. Heikot redukibiliteetit ovat niitä, joissa pelkistymisprosessi ei välttämättä pääty kaikille oraakkeleille; Turing reducibility on yksi esimerkki.

vahvoja reduktioita ovat:

yksi-yksi-reducibility A on yksi-yksi-reducibible (tai 1-reducible) B: ksi, jos on olemassa laskennallinen injektiivinen kokonaisfunktio f siten, että jokainen n on A: ssa, jos ja vain jos f(n) on B: ssä. A on monta-yksi reducible(tai m-reducible) B, jos on yhteensä computable funktio f siten, että jokainen n on a Jos ja vain jos f(n) on B. Totuustaulukon reducibility A on totuustaulukon reducible to B, Jos A on Turing reducible to b kautta oraakkeli Turingin kone, joka laskee kokonaisfunktion riippumatta oraakkelista sille annetaan. Cantorin avaruuden tiiviyden vuoksi tämä vastaa sitä, että reduktio esittää oraakkelille samanaikaisesti yhden kysymyslistan (riippuen vain syötteestä), jonka jälkeen nähtyään vastaukset pystyy tuottamaan ulostulon kysymättä lisäkysymyksiä riippumatta oraakkelin vastauksesta alkukyselyihin. Myös totuustaulukon reducibiliteetin monia variantteja on tutkittu.

muita reduktioita (positiivisia, disjunktiivisia, konjunktiivisia, lineaarisia ja niiden heikkoja ja rajattuja versioita) käsitellään artikkelissa reduktio (rekursioteoria).

suuri tutkimus vahvojen redukibiliteettien suhteen on ollut niiden teorioiden vertaileminen sekä kaikkien rekursiivisesti lueteltujen joukkojen että luonnollisten lukujen kaikkien osajoukkojen luokkien osalta. Lisäksi redukibiliteettien välisiä suhteita on tutkittu. Esimerkiksi tiedetään, että jokainen Turingin aste on joko totuustaulukon aste tai on äärettömän monen totuustaulukon asteen liitto.

Turing-redukibiliteettia heikompia Redukibiliteetteja (eli Turing-redukibiliteetin implisiittisiä redukibiliteetteja) on myös tutkittu. Tunnetuimpia ovat aritmeettinen reducibility ja hyperaritmeettinen reducibility. Nämä redukibiliteetit liittyvät läheisesti määriteltävyyteen aritmetiikan standardimallin suhteen.

Ricen lause ja aritmeettinen hierarkia

Rice osoitti, että jokaiselle Ei-r.e-luokalle (joka sisältää joitakin mutta ei kaikkia r. e-joukkoja) indeksijoukko E = {e: eth r.e. asettaa olemme C} on omaisuutta, että joko pysäyttäminen ongelma tai sen komplementti on monta-yksi reducible E, että on, voidaan kartoittaa käyttämällä monta-yksi vähentäminen e (katso riisin lause tarkemmin). Mutta monet näistä indeksijoukoista ovat vielä monimutkaisempia kuin pysäyttämisongelma. Tällaiset joukot voidaan luokitella aritmeettisen hierarkian avulla. Esimerkiksi kaikkien äärellisten joukkojen luokan indeksijoukko FIN on tasolla Σ2, kaikkien rekursiivisten joukkojen luokan indeksijoukko REC on tasolla Σ3, kaikkien kofiniittijoukkojen indeksijoukko COFIN on myös tasolla Σ3 ja kaikkien Turing-täydellisten joukkojen luokan indeksijoukko Comp Σ4. Nämä hierarkiatasot määritellään induktiivisesti, Σn+1 sisältää vain kaikki joukot, jotka ovat rekursiivisesti Enumeroituvia suhteessa Σn: ään; Σ1 sisältää rekursiivisesti enumeroituvia joukkoja. Tässä annetut indeksijoukot ovat tasoiltaan jopa täydellisiä, eli kaikki näiden tasojen sarjat voivat olla monia-yksi vähennettynä annettuihin indeksijoukkoihin.

Reverse mathematicsEdit

käänteisen matematiikan ohjelma kysyy, mitkä joukko-olemassaolon aksioomat ovat välttämättömiä, jotta voidaan todistaa tiettyjä matematiikan teoreemoja toisen kertaluvun aritmetiikan alijärjestelmissä. Tämän tutkimuksen pani alulle Harvey Friedman ja sitä tutkivat yksityiskohtaisesti Stephen Simpson ja muut; Simpson (1999) esittää yksityiskohtaisen keskustelun ohjelmasta. Kyseiset joukko-eksistenssiaksioomat vastaavat epävirallisesti aksioomia, joiden mukaan luonnollisten lukujen potenssijoukko on suljettu erilaisten redusoituvuuskäsitteiden nojalla. Heikoin tällainen käänteisessä matematiikassa tutkittu aksiooma on rekursiivinen ymmärtäminen, jonka mukaan naturaalien potenssijoukko on suljettu Turingin redukibiliteetin mukaan.

NumberingsEdit

a-numerointi on funktioiden joukko; siinä on kaksi parametria, e ja x, ja se tuottaa E-th-funktion arvon tulon X numeroinnissa. Numberings voi olla osittainen-rekursiivinen, vaikka jotkut sen jäsenistä ovat yhteensä rekursiivisia, eli laskennallisia funktioita. Hyväksyttäviä numeroita ovat ne, joihin kaikki muut voidaan kääntää. Friedberg-numerointi (nimetty löytäjänsä mukaan) on kaikkien osittaisrekursiivisten funktioiden yksi-yksi-numerointi; se ei välttämättä ole hyväksyttävä numerointi. Myöhemmin tutkimus käsitellään myös numerings muiden luokkien kuten luokkien recursively enumerable asetetaan. Goncharov löydetty esimerkiksi luokan recursively enumerable asetetaan, joille numerot kuuluvat täsmälleen kaksi luokkaa suhteessa rekursiivinen isomorphisms.

prioriteettimenetelmä edit

tarkempaa selitystä on artikkelissa Turing degree, Postin ongelma ja prioriteettimenetelmä.

Postin ongelma ratkaistiin menetelmällä, jota kutsutaan prioriteettimenetelmäksi; tätä menetelmää käyttävää todistetta kutsutaan prioriteettiargumentiksi. Tätä menetelmää käytetään ensisijaisesti konstruoimaan rekursiivisesti lueteltavia joukkoja, joilla on tiettyjä ominaisuuksia. Tätä menetelmää käytettäessä konstruoitavan joukon halutut ominaisuudet hajotetaan äärettömäksi tavoiteluetteloksi eli vaatimuksiksi, jolloin kaikkien vaatimusten täyttäminen aiheuttaa konstruoidulle joukolle halutut ominaisuudet. Jokainen vaatimus on annettu luonnolliselle luvulle, joka edustaa vaatimuksen prioriteettia; joten 0 on annettu tärkeimmälle prioriteetille, 1 toiseksi tärkeimmälle ja niin edelleen. Joukko on sitten rakennettu vaiheittain, jokainen vaihe yrittää täyttää yksi enemmän vaatimuksia joko lisäämällä numeroita asetettu tai kieltämällä numerot asetettu niin, että lopullinen joukko täyttää vaatimuksen. Voi käydä niin, että yhden vaatimuksen täyttäminen aiheuttaa toisen tyytymättömyyden; prioriteettijärjestystä käytetään sen päättämiseen, mitä tällaisessa tilanteessa tehdään.

ensisijaisia argumentteja on käytetty ratkaisemaan monia rekursioteorian ongelmia, ja ne on luokiteltu hierarkiaan niiden monimutkaisuuden perusteella (Soare 1987). Koska monimutkaiset prioriteettiväitteet voivat olla teknisiä ja vaikeaselkoisia, on perinteisesti pidetty suotavana tulosten todistamista ilman prioriteettiväitteitä tai sitä, voidaanko prioriteettiväitteillä todistetut tulokset todistaa myös ilman niitä. Esimerkiksi Kummer julkaisi paperin todiste siitä, että on olemassa Friedberg numerings ilman prioriteettimenetelmää.

the lattice of recursively enumerable setsEdit

When Post defined the conceptation of a simple set as an r. e. set with an infinite complement not continue any infinite r.e. set, hän alkoi tutkia rakennetta recursively enumerable asetetaan alle sisällyttämistä. Tämä ristikko tuli hyvin tutkittu rakenne. Rekursiiviset joukot voidaan määritellä tässä rakenteessa sillä perustuloksella, että joukko on rekursiivinen, jos ja vain jos joukko ja sen komplementti ovat molemmat rekursiivisesti enumeroituvia. Äärettömillä r. e. joukoilla on aina äärettömät rekursiiviset osajoukot, mutta toisaalta yksinkertaiset joukot ovat olemassa, mutta niillä ei ole koinfiniittistä rekursiivista superjoukkoa. Post (1944) käyttöön jo hypersimple ja hyperhypersimple asetetaan; myöhemmin maximal asetetaan rakennettiin, jotka ovat r.e. asetetaan siten, että jokainen r.e. superjoukko on joko annetun maksimijoukon äärellinen muunnos tai se on ko-äärellinen. Postin alkuperäinen motivaatio tutkimuksessa tämän lattice oli löytää rakenteellinen käsite sellainen, että jokainen asetettu, joka täyttää tämän omaisuuden ei ole Turing aste, rekursiivinen asetetaan eikä Turing aste, pysäyttäminen ongelma. Post ei löytänyt tällaista omaisuutta ja ratkaisu hänen ongelmaansa sovelletaan prioriteettimenetelmiä sen sijaan; Harrington and Soare (1991) löytyi lopulta tällainen ominaisuus.

Automorfismin problemsEdit

toinen tärkeä kysymys on automorfismien olemassaolo rekursio-teoreettisissa rakenteissa. Yksi näistä rakenteista on, että yksi rekursiivisesti enumerable asetetaan alle sisällyttämistä modulo rajallinen ero; tässä rakenteessa, A on alle B Jos ja vain jos joukko − ero B-A on rajallinen. Maksimijoukoilla (kuten edellisessä kappaleessa on määritelty) on se ominaisuus, että ne eivät voi olla automorfisia ei-maksimaalisten joukkojen kanssa, eli jos on olemassa rekursiivisten enumeroivien joukkojen automorfismi juuri mainitun rakenteen alla, niin jokainen maksimijoukko on kartoitettu toiselle maksimijoukolle. Soare (1974) osoitti, että myös converse pätee, eli joka toinen maksimijoukko on automorfinen. Maksimijoukot muodostavat siis kiertoradan, eli jokainen automorfismi säilyttää maksimaalisuuden ja mikä tahansa kaksi maksimijoukkoa muuntuu jollakin automorfismilla toisikseen. Harrington antoi vielä esimerkin automorfisesta ominaisuudesta: luovien sarjojen, sarjojen, joita on monta-yksi vastaa pysäyttävää ongelmaa.

rekursiivisesti enumeroituvien joukkojen hilan lisäksi tutkitaan myös automorfismeja kaikkien joukkojen Turingin asteiden rakenteesta sekä R.e. joukkojen Turingin asteiden rakenteesta. Molemmissa tapauksissa Cooper väittää rakentaneensa nontriviaalisia automorfismeja, jotka kartoittavat joitakin asteita toisiin asteisiin; tätä konstruktiota ei kuitenkaan ole tarkistettu, ja jotkut kollegat uskovat, että konstruktio sisältää virheitä ja että kysymys siitä, onko Turingin asteiden ei-triviaalinen automorfismi, on edelleen yksi tärkeimmistä ratkaisemattomista kysymyksistä tällä alalla (Slaman and Woodin 1986, Ambos-Spies and Fejer 2006).

Kolmogorov complexityEdit

Kolmogorovin kompleksisuuden ja algoritmisen satunnaisuuden kenttää kehittivät 1960-ja 1970-luvuilla Chaitin, Kolmogorov, Levin, Martin-Löf ja Solomonoff (nimet on esitetty tässä aakkosjärjestyksessä; suuri osa tutkimuksesta oli riippumatonta, eikä satunnaisuuden käsitteen yhtenäisyyttä tuolloin ymmärretty). Keskeisenä ajatuksena on pitää universaalia Turingin konetta U ja mitata luvun (tai merkkijonon) X monimutkaisuus lyhimmän tulon p pituutena siten, että U(p) tuottaa X: n. Tämä lähestymistapa mullisti aikaisemmat tavat määrittää, milloin ääretön jono (vastaavasti luonnollisten lukujen osajoukon ominaisfunktio) on satunnainen vai ei vetoamalla äärellisten kappaleiden satunnaisuuden käsitteeseen. Kolmogorov monimutkaisuus tuli paitsi aihe riippumattoman tutkimuksen, mutta on myös sovellettu muihin aiheisiin kuin väline saada todisteita.Tällä alalla on vielä paljon avoimia ongelmia. Tästä syystä asiaa koskeva tuore tutkimuskonferenssi pidettiin tammikuussa 2007, ja Joseph Miller ja Andre Nies pitävät yllä luetteloa avoimista ongelmista.

Frekvenssilaskennan edit

tämä rekursioteorian haara analysoi seuraavan kysymyksen: kiinteille m: lle ja n: lle 0 < m < n, joille funktioille A on mahdollista laskea mitä tahansa eri N-tuloille x1, x2, …, xn a tuple n numerot y1, y2,…, yn sellainen, että ainakin m yhtälöt A (xk) = yk ovat totta. Tällaisia joukkoja kutsutaan (m, n)-rekursiivisiksi joukoiksi. Ensimmäinen merkittävä tulos tässä Rekursioteorian haarassa on Trakhtenbrotin tulos, jonka mukaan joukko on laskettavissa, jos se on (m, n)-rekursiivinen joillekin m, n kanssa 2m > n. Toisaalta Jockuschin puolirekursiiviset joukot (jotka tunnettiin epävirallisesti jo ennen kuin Jockusch esitteli ne 1968) ovat esimerkkejä joukoista, jotka ovat (m, n)-rekursiivisia, jos ja vain jos 2m < n + 1. On uncountably monet näistä sarjoista ja myös joitakin recursively enumerable mutta noncomputable asetetaan tätä tyyppiä. Myöhemmin Degtev perusti hierarkian rekursiivisista joukoista, jotka ovat (1, n + 1)-rekursiivisia mutta eivät (1, n)-rekursiivisia. Kun pitkän vaiheen tutkimuksen Venäjän tutkijat, tämä aihe tuli repopularisoitu lännessä Beigel ‘ s thesis on rajattu kyselyt, joka liittyy taajuuslaskennan edellä mainittujen rajoittaa reducibilities ja muut siihen liittyvät käsitteet. Yksi tärkeimmistä tuloksista oli Kummer ‘ s Cardinality teoria, jossa todetaan, että joukko A on computable jos ja vain jos on olemassa n sellainen, että jotkut algoritmi luettelee kunkin tuple, n eri numerot jopa n monia mahdollisia valintoja, kardinality tämän joukon n numerot leikkaavat kanssa; näiden valintojen tulee sisältää todellinen kardinaalisuus, mutta jättää pois ainakin yksi väärä.

induktiivinen päättely

tämä on oppimisteorian rekursio-teoreettinen haara. Se perustuu E. Mark Goldin model of learning in the limit-malliin vuodelta 1967 ja on sen jälkeen kehittänyt yhä useampia oppimismalleja. Yleinen skenaario on seuraava: koska luokka s laskennallisia funktioita, on olemassa oppija (eli rekursiivinen funktio), joka tuottaa mitään tulo muodossa (f(0),f(1),…, f(n)) hypoteesi. Oppija m oppii funktion f, jos lähes kaikki hypoteesit ovat sama indeksi e f suhteessa aiemmin sovittuun hyväksyttävään numerointiin kaikkien laskettavissa funktioiden; M oppii S Jos M oppii jokaisen f: n S. Perustulokset ovat, että kaikki rekursiivisesti luettavat funktioluokat ovat opittavissa, kun taas kaikkien laskettavissa olevien funktioiden Luokka REC ei ole opittavissa. Monet liittyvät mallit on pidetty ja myös oppimisen luokkien recursively enumerable asetetaan myönteisiä tietoja on aihe tutkittu Gold ‘ s uraauurtava paperi vuonna 1967 alkaen.

yleistyksiä Turingin computabilityEdit

Rekursioteoria sisältää tutkimuksen yleistettyjä käsitteitä tällä alalla, kuten aritmeettinen reducibility, hyperaritmeettinen reducibility ja α-rekursioteoria, sellaisena kuin se on kuvattu Sacks (1990). Näihin yleistettyihin käsitteisiin kuuluvat redukibiliteetit, joita Turingin koneet eivät voi toteuttaa, mutta ovat kuitenkin Turingin redukibiliteetin luonnollisia yleistyksiä. Nämä tutkimukset sisältävät lähestymistapoja analyyttisen hierarkian tutkimiseen, joka eroaa aritmeettisesta hierarkiasta sallimalla kvantifioinnin luonnollisten lukujen joukoista yksittäisten lukujen kvantifioinnin lisäksi. Nämä alueet liittyvät hyvin järjestettyjen puiden ja puiden teorioihin; esimerkiksi rekursiivisten (ei-binääristen) puiden, joilla ei ole äärettömiä oksia, kaikkien indeksien joukko on täydellinen tasolla Π 1 1 {\displaystyle \Pi _{1}^{1}}

analyyttisen hierarkian. Sekä Turingin reducibility että hyperaritmeettinen reducibility ovat tärkeitä alalla tehokkaan deskriptiivinen joukko-oppi. Vielä yleisempää käsitettä konstruktiivisuuden asteista tutkitaan joukko-opissa.

jatkuva laskettavuusteoria

digitaalisen laskennan Laskettavuusteoria on hyvin kehittynyt. Laskennallisuusteoria on vähemmän kehittynyt analogisessa laskennassa, jota esiintyy analogisissa tietokoneissa, analogisessa signaalinkäsittelyssä, analogisessa elektroniikassa, neuroverkoissa ja jatkuvatoimisessa aikaohjausteoriassa, jota mallinnetaan differentiaaliyhtälöillä ja jatkuvatoimisilla dynaamisilla järjestelmillä (Orponen 1997; Moore 1996).