Számítási elmélet

a fent leírt rekurzív halmazok és függvények elméletétől kezdve a rekurzióelmélet területe számos szorosan kapcsolódó téma tanulmányozására nőtt. Ezek nem önálló kutatási területek: mindegyik terület ötleteket és eredményeket merít a többiektől, és a legtöbb rekurziós teoretikus ismeri a többségüket.

relatív kiszámíthatóság és a Turing-fokszerkesztés

a Rekurzióelmélet a matematikai logikában hagyományosan a relatív kiszámíthatóságra összpontosított, a Turing-számításhetőség általánosítása oracle Turing-gépekkel, amelyet Turing (1939) vezetett be. Az oracle Turing-gép egy hipotetikus eszköz, amely a szokásos Turing-gép műveleteinek végrehajtása mellett képes kérdéseket feltenni egy orákulumnak, amely egy adott természetes számkészlet. Az oracle gép csak az ” n az oracle készletben?”. Minden kérdésre azonnal helyesen válaszolunk, még akkor is, ha az oracle készlet nem kiszámítható. Így egy nem kiszámítható orákulummal rendelkező oracle gép képes lesz kiszámítani azokat a készleteket, amelyeket egy oracle nélküli Turing-gép nem tud.

informálisan az a természetes számok halmaza Turing redukálható B halmazra, ha van olyan orákulum gép, amely helyesen mondja meg, hogy a számok A-ban vannak-e, ha B-vel futtatják, mint az orákulumkészletet (ebben az esetben az a halmazról azt is mondják, hogy (viszonylag) kiszámítható B és rekurzív ban ben B). Ha EGY a halmaz Turing redukálható B halmazra, B pedig Turing redukálható A-ra, akkor azt mondják, hogy a halmazoknak ugyanaz a Turing-foka (más néven megoldhatatlansági fok). A Turing-fok egy halmaz pontos mérést ad arról, hogy a halmaz mennyire kiszámíthatatlan.

a nem kiszámítható halmazok természetes példái, beleértve a leállítási probléma változatait kódoló sokféle halmazt, két közös tulajdonsággal rendelkeznek:

1. rekurzív módon felsorolhatóak, és
2. mindegyik lefordítható bármely másra egy sok-egy redukcióval. Ez azt jelenti, hogy az ilyen a és B halmazok esetén van egy teljes kiszámítható függvény f oly módon, hogy a = {x : f(x) b}. Ezeket a halmazokat sok-egy ekvivalensnek (vagy m-ekvivalensnek) mondják.

a sok-egy redukció “erősebb”, mint a Turing-redukció: ha EGY a halmaz sok-egy redukálható B halmazra, akkor A Turing redukálható B-re, de az ellenkezője nem mindig áll fenn. Bár a nem számolható halmazok természetes példái sok-egy ekvivalensek, lehetséges rekurzívan felsorolható A és B halmazokat úgy felépíteni, hogy a Turing redukálható B-re, de nem sok-egy redukálható B-re. Megmutatható, hogy minden rekurzívan felsorolható halmaz sok-egy redukálható a megállási problémára, így a megállási probléma a legbonyolultabb rekurzívan felsorolható halmaz a sok-egy redukálhatóság és a Turing redukálhatóság tekintetében. Post (1944) megkérdezte, hogy minden rekurzívan felsorolható halmaz kiszámítható-e, vagy Turing egyenértékű-e a megállási problémával, vagyis nincs-e rekurzívan felsorolható halmaz Turing-fokozattal köztes e kettő között.

köztes eredményként a Post definiálta a rekurzívan felsorolható halmazok természetes típusait, mint például az egyszerű, hipersimple és hiperhipersimple halmazokat. Post kimutatta, hogy ezek a halmazok szigorúan a kiszámítható halmazok és a leállítási probléma között vannak a sok-egy redukálhatóság tekintetében. A Post azt is kimutatta, hogy némelyikük szigorúan köztes más redukálhatósági fogalmak alatt, amelyek erősebbek, mint a Turing redukálhatóság. De Post nyitva hagyta a rekurzívan felsorolható közbenső Turing-fok halmazok létezésének fő problémáját; ez a probléma Post-problémaként vált ismertté. Tíz év után Kleene és Post 1954-ben megmutatta, hogy vannak köztes Turing-fokok a kiszámítható halmazok és a leállítási probléma között, de nem tudták kimutatni, hogy ezek közül bármelyik fok tartalmaz rekurzívan felsorolható halmazt. Nem sokkal ezután Friedberg és Muchnik egymástól függetlenül megoldotta Post problémáját a rekurzívan felsorolható középfokú halmazok létezésének megállapításával. Ez az úttörő eredmény széles körű tanulmányt nyitott a rekurzívan felsorolható halmazok Turing-fokairól, amelyekről kiderült, hogy nagyon bonyolult és nem triviális struktúrával rendelkeznek.

megszámlálhatatlanul sok olyan halmaz létezik, amelyek nem rekurzív módon felsorolhatók, és az összes halmaz Turing-fokának vizsgálata ugyanolyan központi szerepet játszik a rekurzióelméletben, mint a rekurzívan felsorolható Turing-fokok vizsgálata. Sok speciális tulajdonságú fok épült: hiperimmun-mentes fokok, ahol az adott fokhoz képest kiszámítható minden funkciót egy (nem relativizált) kiszámítható függvény majorizál; magas fokok, amelyekhez viszonyítva ki lehet számítani egy függvényt f amely uralja minden kiszámítható függvényt g abban az értelemben, hogy van egy állandó c attól függően g oly módon, hogy g(x) < f(x) minden x > c; véletlenszerű fokok algoritmikusan véletlenszerű halmazokat tartalmaz; 1-általános fokok 1-általános halmazok; és a határ-rekurzív halmazok megállási problémája alatti fokok.

az önkényes (nem feltétlenül rekurzívan felsorolható) Turing-fokok tanulmányozása magában foglalja a Turing-ugrás tanulmányozását. Adott egy halmaz a, A Turing-ugrás a természetes számok halmaza, amely megoldást kódol az Oracle Turing-gépekkel futó Oracle A. bármely halmaz Turing-ugrása mindig magasabb Turing-fokú, mint az eredeti halmaz, és Friedburg tétele azt mutatja, hogy bármely halmaz, amely kiszámítja a megállási problémát, megszerezhető egy másik halmaz Turing-ugrásaként. Post tétele szoros kapcsolatot teremt a Turing-ugrási művelet és az aritmetikai hierarchia között, amely a természetes számok bizonyos részhalmazainak osztályozása aritmetikai meghatározhatóságuk alapján.

a Turing-fokokkal kapcsolatos legújabb kutatások a Turing-fokok halmazának és a rekurzívan felsorolható halmazokat tartalmazó Turing-fokok halmazának általános szerkezetére összpontosítottak. A deep theorem of Shore and Slaman (1999) azt állítja, hogy a függvény leképezése fokú x a mértéke a Turing-ugrás meghatározható a részleges sorrendben a Turing-fok. Az Ambos-Spies és Fejer (2006) közelmúltbeli felmérése áttekintést ad erről a kutatásról és annak történelmi előrehaladásáról.

Egyéb csökkentésekszerkesztés

a rekurzióelmélet folyamatos kutatási területe a Turing redukción kívüli redukálhatósági kapcsolatokat vizsgálja. Post (1944) számos erős redukálhatóságot vezetett be, így nevezték el, mert az igazságtáblázat redukálhatóságát jelentik. Az erős redukálhatóságot megvalósító Turing-gép kiszámítja a teljes függvényt, függetlenül attól, hogy melyik orákulummal van bemutatva. Gyenge redukálhatóságok azok, ahol a redukciós folyamat nem fejeződhet be minden orákulum esetében; Turing redukálhatóság az egyik példa.

az erős redukálhatóságok a következők:

egy-egy redukálhatóság A egy-egy redukálható(vagy 1-redukálható) B-re, ha van egy teljes kiszámítható injektív függvény f oly módon, hogy mindegyik n csak akkor van A-ban, ha f (n) B-ben van. A sok-egy redukálható(vagy m-redukálható) B-re, ha van egy teljes kiszámítható függvény f oly módon, hogy minden n csak akkor van A-Ban, ha f (n) B-ben van. Igazság-táblázat redukálhatósága a az igazság-táblázat redukálható B ha a Turing redukálható B-re egy oracle Turing-gépen keresztül, amely kiszámítja a teljes függvényt, függetlenül a megadott orákulumtól. A Cantor tér tömörsége miatt ez egyenértékű azzal, hogy azt mondjuk, hogy a redukció egyetlen kérdéslistát mutat be (csak a bemenettől függően) az oracle-nek egyszerre, majd miután látta a válaszaikat, képes kimenetet előállítani anélkül, hogy további kérdéseket tenne fel, függetlenül az oracle válaszától a kezdeti lekérdezésekre. Az igazságtábla redukálhatóságának számos változatát is tanulmányozták.

további redukálhatóságokat (pozitív, diszjunktív, konjunktív, lineáris és ezek gyenge és korlátozott változatai) a redukció (rekurzióelmélet) című cikk tárgyalja.

az erős redukálhatósággal kapcsolatos legfontosabb kutatások elméleteik összehasonlítása volt, mind az összes rekurzívan felsorolható halmaz osztályára, mind a természetes számok összes részhalmazának osztályára. Ezenkívül tanulmányozták a redukálhatóságok közötti kapcsolatokat. Például ismert, hogy minden Turing-fok vagy igazság-asztal fok, vagy végtelen sok igazság-asztal fok egyesülése.

a Turing-redukálhatóságnál gyengébb Redukálhatóságokat (vagyis a Turing-redukálhatóság által implikált redukálhatóságot) szintén tanulmányozták. A legismertebbek az aritmetikai redukálhatóság és a hiperaritmetikai redukálhatóság. Ezek a redukálhatóságok szorosan kapcsolódnak a meghatározhatósághoz az aritmetika standard modelljével szemben.

Rice tétele és a számtani hierarchia

Rice megmutatta, hogy minden nem triviális osztály C (amely tartalmaz néhány, de nem az összes r.e. készletek) az index set E = {e: az eth r.e. set we is in C} megvan az a tulajdonsága, hogy vagy a megállási probléma, vagy annak kiegészítése sok-egy redukálható E-re, vagyis leképezhető egy sok-egy redukcióval E-re (lásd Rice tétele részletesebben). De ezek közül az indexkészletek közül sok még bonyolultabb, mint a leállítási probléma. Az ilyen típusú halmazok osztályozhatók a számtani hierarchia. Például az összes véges halmaz osztályának indexhalmaza fin szinten van 62, az indexhalmaz REC az összes rekurzív halmaz osztálya a szinten van 63, az indexhalmaz COFIN az összes cofin halmaz szintén a szinten van 6 és az indexhalmaz COMP az összes Turing-teljes halmaz Osztálya közül 64. Ezeket a hierarchiaszinteket induktívan definiáljuk, az Xhamn+1 csak az összes olyan halmazt tartalmazza, amelyek rekurzívan felsorolhatók az Xhamn-hez képest; az 61 tartalmazza a rekurzívan felsorolható halmazokat. Az itt megadott indexkészletek szintjük szempontjából is teljesek, vagyis ezeken a szinteken az összes halmaz sok lehet-az egyik az adott indexkészletre redukálható.

Reverse mathematicsEdit

a program a reverse mathematics kérdezi, amely set-létezés axiómák bizonyításához szükséges egyes tételek a matematika alrendszereiben másodrendű aritmetikai. Ezt a tanulmányt Harvey Friedman kezdeményezte, és Stephen Simpson és mások részletesen tanulmányozták; Simpson (1999) részletesen ismerteti a programot. A szóban forgó halmaz-lét axiómák informálisan megfelelnek azoknak az axiómáknak, amelyek szerint a természetes számok hatalma különféle redukálhatósági fogalmak alatt zárva van. A fordított matematikában vizsgált leggyengébb ilyen axióma a rekurzív megértés, amely kimondja, hogy a naturálok ereje Turing redukálhatósága alatt zárva van.

NumberingsEdit

a számozás a függvények felsorolása; két paramétere van, e és x, és az e-edik függvény értékét adja ki az x bemenet számozásában. A számozás lehet részleges rekurzív bár néhány tagja teljes rekurzív, Vagyis kiszámítható függvények. Elfogadható számok azok, amelyekbe az összes többi lefordítható. A Friedberg számozás (felfedezőjéről nevezték el) az összes részleges rekurzív függvény egy-egy számozása; szükségszerűen nem elfogadható számozás. A későbbi kutatások más osztályok számozásával is foglalkoztak, például rekurzívan felsorolható halmazok osztályaival. Goncsarov felfedezte például a rekurzívan felsorolható halmazok osztályát, amelyek számozása pontosan két osztályba tartozik a rekurzív izomorfizmusok tekintetében.

a prioritási módszerszerkesztés

további magyarázatért lásd a Post ‘ s problem and the priority method című cikket a Turing-fokozatban.

Post problémáját a prioritás metódusnak nevezett módszerrel oldottuk meg; az ezt a módszert használó bizonyítékot prioritási argumentumnak nevezzük. Ezt a módszert elsősorban rekurzívan felsorolható, meghatározott tulajdonságokkal rendelkező halmazok felépítésére használják. Ennek a módszernek a használatához a felépítendő halmaz kívánt tulajdonságait a célok végtelen listájára, az úgynevezett követelményekre bontják, így az összes követelmény kielégítése miatt a felépített halmaz megkapja a kívánt tulajdonságokat. Minden követelményt egy természetes számhoz rendelnek, amely a követelmény prioritását képviseli; tehát 0 a legfontosabb prioritáshoz, 1 a második legfontosabbhoz stb. Ezután a halmazt szakaszokban építik fel, mindegyik szakasz megpróbálja kielégíteni a követelmények egyikét azáltal, hogy számokat ad hozzá a halmazhoz, vagy kitiltja a számokat a halmazból, hogy a végső halmaz kielégítse a követelményt. Előfordulhat, hogy az egyik követelmény kielégítése a másik elégedetlenségét okozza; az elsőbbségi sorrendet használják annak eldöntésére, hogy mit kell tenni egy ilyen esetben.

a rekurzióelmélet számos problémájának megoldására prioritás argumentumokat alkalmaztak, és komplexitásuk alapján hierarchiába sorolták őket (Soare 1987). Mivel a komplex prioritási érvek technikai jellegűek és nehezen követhetők, hagyományosan kívánatosnak tartották az eredmények elsőbbségi érvek nélküli bizonyítását, vagy annak megvizsgálását, hogy az elsőbbségi érvekkel bizonyított eredmények nélkül is bizonyíthatók-e. Kummer például közzétett egy cikket a Friedberg-számok létezésének igazolásáról a prioritási módszer használata nélkül.

a rekurzívan felsorolható halmazok rácsa

amikor Post meghatározta az egyszerű halmaz fogalmát r.e. végtelen komplementtel rendelkező halmaz, amely nem tartalmaz végtelen r.e. set, elkezdte tanulmányozni a rekurzívan felsorolható halmazok felépítését a befogadás alatt. Ez a rács jól tanulmányozott struktúrává vált. A rekurzív halmazok ebben a struktúrában definiálhatók azzal az alapvető eredménnyel, hogy egy halmaz akkor és csak akkor rekurzív, ha a halmaz és annak komplementere egyaránt rekurzívan felsorolható. Végtelen r. e. a halmazok mindig végtelen rekurzív részhalmazokkal rendelkeznek; de másrészt léteznek egyszerű halmazok, de nincs coinfinite rekurzív szuperszettjük. Post (1944) már bevezette a hypersimple és a hyperhypersimple halmazokat; később olyan maximális halmazokat hoztak létre, amelyek r.e. halmazok, hogy minden r.e. a szuperset vagy az adott maximális halmaz véges változata, vagy együtt véges. Post eredeti motivációja ennek a rácsnak a tanulmányozásában egy olyan szerkezeti fogalom megtalálása volt, hogy minden olyan halmaz, amely kielégíti ezt a tulajdonságot, sem a rekurzív halmazok Turing-fokában, sem a megállási probléma Turing-fokában nincs. Post nem talált ilyen tulajdonságot, és problémájának megoldása helyett prioritási módszereket alkalmazott; Harrington and Soare (1991) végül ilyen tulajdonságot talált.

Automorfizmus problemsEdit

egy másik fontos kérdés az automorfizmusok létezése a rekurzióelméleti struktúrákban. Ezen struktúrák egyike az egyik rekurzívan felsorolható halmaz inklúzió alatt modulo véges különbség; ebben a struktúrában A csak akkor van B alatt, ha a halmaz különbség B − a véges. A maximális halmazok (az előző bekezdésben meghatározottak szerint) azzal a tulajdonsággal rendelkeznek, hogy nem lehetnek automorfak a nem maximális halmazokkal szemben, vagyis ha a rekurzív felsorolható halmazok automorfizmusa van az imént említett struktúra alatt, akkor minden maximális halmaz egy másik maximális halmazra van leképezve. Soare (1974) kimutatta, hogy az ellenkezője is fennáll, vagyis minden két maximális halmaz automorf. Tehát a maximális halmazok pályát alkotnak, vagyis minden automorfizmus megőrzi a maximalitást, és bármely két maximális halmaz átalakul egymásba valamilyen automorfizmus által. Harrington további példát adott egy automorf tulajdonságra: a kreatív halmazok, azok a halmazok, amelyek sok-egy egyenértékűek a megállási problémával.

a rekurzívan felsorolható halmazok rácsán kívül az automorfizmusokat az összes halmaz Turing-fokának szerkezetére, valamint az r.E. halmazok Turing-fokának szerkezetére is tanulmányozzák. Mindkét esetben Cooper azt állítja, hogy nem triviális automorfizmusokat épített fel, amelyek bizonyos fokokat más fokokra térképeznek; ezt a konstrukciót azonban nem ellenőrizték, és néhány kolléga úgy véli, hogy az építkezés hibákat tartalmaz, és hogy a Turing-fokozatok nem triviális automorfizmusa továbbra is az egyik fő megoldatlan kérdés ezen a területen (Slaman and Woodin 1986, Ambos-Spies and Fejer 2006).

Kolmogorov komplexitás

a Kolmogorov-komplexitás és az algoritmikus véletlenszerűség területét az 1960-as és 1970-es években fejlesztette ki Chaitin, Kolmogorov, Levin, Martin-L. A. és Solomonoff (a neveket itt ábécé sorrendben adják meg; a kutatás nagy része független volt, és a véletlenszerűség fogalmának egységét akkoriban nem értették). A fő gondolat az, hogy egy univerzális Turing-gépet U-nak tekintsünk, és egy szám (vagy húr) bonyolultságát mérjük x mint a legrövidebb bemenet hossza p oly módon, hogy U(p) kimenetek x. Ez a megközelítés forradalmasította a korábbi módszereket annak meghatározására, hogy mikor végtelen szekvencia (ekvivalensen a természetes számok részhalmazának jellemző funkciója) véletlenszerű vagy nem a véges objektumok véletlenszerűségének fogalmára hivatkozva. A Kolmogorov-komplexitás nemcsak független tanulmány tárgyává vált, hanem más tantárgyakra is alkalmazható, mint a bizonyítékok megszerzésének eszköze.Még mindig sok nyitott probléma van ezen a területen. Ezért 2007 januárjában egy újabb kutatási konferenciát tartottak ezen a területen, és a nyitott problémák listáját Joseph Miller és Andre Nies vezeti.

Frequency computationEdit

a rekurzióelméletnek ez az ága a következő kérdést elemezte: rögzített m és n esetén 0 < m < n esetén, mely függvények esetében lehetséges kiszámítani bármely különböző n bemenetet x1, x2, …, xn egy n szám tuple y1, y2,…, yn olyan, hogy az egyenletek közül legalább m a (xk) = yk igazak. Az ilyen halmazokat (m, n)-rekurzív halmazoknak nevezzük. A Rekurzióelmélet ezen ágának első fő eredménye az Trakhtenbrot eredménye, hogy egy halmaz kiszámítható, ha (m, n)-rekurzív egyeseknél m, n val vel 2m > n. Másrészt Jockusch félkörív halmazai (amelyek informálisan már ismertek voltak, mielőtt Jockusch 1968-ban bevezette őket) példák egy olyan halmazra, amely (m, n) – rekurzív csak akkor, ha 2m < n + 1. Megszámlálhatatlanul sok ilyen halmaz van, valamint néhány rekurzívan felsorolható, de nem kiszámítható ilyen típusú halmaz. Később Degtev létrehozta a rekurzívan felsorolható halmazok hierarchiáját, amelyek (1, n + 1)-rekurzív, de nem (1, n)-rekurzív. Az orosz tudósok hosszú kutatási fázisa után ez a téma nyugaton újratelepült Beigel korlátozott lekérdezésekről szóló tézisével, amely összekapcsolta a frekvenciaszámítást a fent említett korlátozott redukálhatóságokkal és más kapcsolódó fogalmakkal. Az egyik fő eredmény Kummer Kardinalitáselmélete volt, amely kimondja, hogy egy halmaz a csak akkor számítható ki, ha van n olyan, hogy egyes algoritmusok felsorolják n különböző számok mindegyikéhez n ennek a halmaznak a kardinalitásának számos lehetséges választása n számok metszi A; ezeknek a választásoknak tartalmazniuk kell az igazi kardinalitást, de legalább egy hamisat ki kell hagyniuk.

induktív következtetésszerkesztés

ez a tanuláselmélet rekurzióelméleti ága. E. Mark Gold 1967-es limit tanulási modelljén alapul, és azóta egyre több tanulási modellt fejlesztett ki. Az általános forgatókönyv a következő: Adott egy osztály s kiszámítható függvények, van egy tanuló (azaz rekurzív funkcionális), amely kimenetek bármely bemenet a forma (f (0), f(1),…, f(n)) hipotézis. A tanuló M megtanul egy függvényt f ha szinte az összes hipotézis azonos index e nak, – nek f az összes kiszámítható függvény elfogadható számozásáról korábban megállapodtak; M megtanulja S ha M mindent megtanul f ban ben S. alapvető eredmények az, hogy az összes rekurzívan felsorolható függvényosztály megtanulható, míg az osztály REC az összes kiszámítható függvény nem tanulható. Számos kapcsolódó modellt vettek figyelembe, valamint a rekurzívan felsorolható halmazok osztályainak pozitív adatokból történő megtanulását Gold úttörő tanulmányából tanulmányozták 1967-től kezdve.

általánosítások Turing computabilityEdit

rekurzió elmélet magában foglalja a tanulmány az általánosított fogalmak ezen a területen, mint például aritmetikai redukálhatóság, hiperaritmetikai redukálhatóság, valamint a kb-rekurzió elmélet, amint azt Sacks (1990). Ezek az általánosított fogalmak olyan redukálhatóságokat tartalmaznak, amelyeket a Turing-gépek nem hajthatnak végre, de ennek ellenére a Turing-redukálhatóság természetes általánosításai. Ezek a tanulmányok olyan megközelítéseket tartalmaznak az analitikai hierarchia vizsgálatára, amely eltér a számtani hierarchiától azáltal, hogy lehetővé teszi a természetes számok halmazainak számszerűsítését az egyes számok számszerűsítése mellett. Ezek a területek kapcsolódnak a jól elrendezett fák és fák elméletéhez; például a végtelen ágak nélküli rekurzív (nem bináris) fák összes indexének halmaza teljes a szinthez! 1 1 {\displaystyle \ Pi _{1}^{1}}

az analitikus hierarchia. Mind a Turing redukálhatóság, mind a hiperaritmetikai redukálhatóság fontos a hatékony leíró halmazelmélet területén. A konstruktibilitás fokozatainak még általánosabb fogalmát a halmazelméletben tanulmányozzák.

folyamatos számítási elmélet

a digitális számítás számítási elmélete jól fejlett. A számítási elmélet kevésbé fejlett az analóg számításokhoz, amelyek az analóg számítógépekben, az analóg jelfeldolgozásban, az analóg elektronikában, a neurális hálózatokban és a folyamatos idővezérlési elméletben fordulnak elő, differenciálegyenletekkel és folyamatos dinamikus rendszerekkel modellezve (Orponen 1997; Moore 1996).