Beräkningsteori

från och med teorin om rekursiva uppsättningar och funktioner som beskrivs ovan har rekursionsteorin vuxit till att omfatta studier av många närbesläktade ämnen. Dessa är inte självständiga forskningsområden: vart och ett av dessa områden drar ideer och resultat från de andra, och de flesta rekursionsteoretiker känner till majoriteten av dem.

relativ beräkningsbarhet och Turing-gradenredigera

Rekursionsteori i matematisk logik har traditionellt fokuserat på relativ beräkningsbarhet, en generalisering av Turing-beräkningsbarhet definierad med oracle Turing-maskiner, introducerad av Turing (1939). En oracle Turing-maskin är en hypotetisk enhet som, förutom att utföra åtgärderna hos en vanlig Turing-maskin, kan ställa frågor till ett orakel, vilket är en viss uppsättning naturliga tal. Oracle-maskinen får bara ställa frågor i formuläret ” är n i oracle-uppsättningen?”. Varje fråga kommer omedelbart att besvaras korrekt, även om oracle-uppsättningen inte kan beräknas. Således kommer en oracle-maskin med ett icke-beräkningsbart oracle att kunna beräkna uppsättningar som en Turing-maskin utan ett oracle inte kan.

informellt är en uppsättning naturliga tal a Turing reducerbar till en uppsättning B om det finns en oracle-maskin som korrekt berättar om siffror är i A när de körs med B som oracle-uppsättningen (i detta fall sägs uppsättningen A också vara (relativt) beräkningsbar från B och rekursiv i B). Om en uppsättning A är Turing reducerbar till en uppsättning B och B är Turing reducerbar till A, sägs uppsättningarna ha samma Turing-grad (även kallad grad av olöslighet). Turing-graden för en uppsättning ger ett exakt mått på hur uncomputable uppsättningen är.

de naturliga exemplen på uppsättningar som inte kan beräknas, inklusive många olika uppsättningar som kodar varianter av stoppproblemet, har två egenskaper gemensamt:

1. de är rekursivt uppräknade, och
2. var och en kan översättas till någon annan via en många-en reduktion. Det vill säga, med tanke på sådana uppsättningar A och B, finns det en total beräkningsbar funktion f sådan att A = {x : f(x) xhamster b}. Dessa uppsättningar sägs vara många-en ekvivalent (eller m-ekvivalent).

många-en-minskningar är “starkare” än Turing-minskningar: om en uppsättning A är många-en reducerbar till en uppsättning B, är A Turing reducerbar till B, men det omvända håller inte alltid. Även om de naturliga exemplen på icke-beräkningsbara uppsättningar alla är många-en ekvivalent, är det möjligt att konstruera rekursivt uppräkningsbara uppsättningar A och B så att A är Turing reducerbar till B men inte många-en reducerbar till B. Det kan visas att varje rekursivt uppräkningsbar uppsättning är många-en reducerbar till stoppproblemet, och därmed är stoppproblemet den mest komplicerade rekursivt uppräkningsbara uppsättningen med avseende på många-en reducerbarhet och med avseende på Turing reducerbarhet. Post (1944) frågade om varje rekursivt uppräkningsbar uppsättning antingen är beräkningsbar eller Turing motsvarar stoppproblemet, det vill säga om det inte finns någon rekursivt uppräkningsbar uppsättning med en Turing grad mellanliggande mellan dessa två.

som mellanresultat definierade Post naturliga typer av rekursivt uppräkningsbara uppsättningar som de enkla, hypersimple och hyperhypersimple uppsättningarna. Post visade att dessa uppsättningar är strikt mellan de beräkningsbara uppsättningarna och stoppproblemet med avseende på många reducerbarhet. Post visade också att vissa av dem är strikt mellanliggande under andra reducerbarhet begrepp starkare än Turing reducerbarhet. Men Post lämnade Öppet huvudproblemet med förekomsten av rekursivt uppräkningsbara uppsättningar av mellanliggande Turing-grad; detta problem blev känt som posts problem. Efter tio år visade Kleene och Post 1954 att det finns mellanliggande Turing-grader mellan de beräkningsbara uppsättningarna och stoppproblemet, men de kunde inte visa att någon av dessa grader innehåller en rekursivt uppräkbar uppsättning. Mycket snart efter detta löste Friedberg och Muchnik självständigt posts problem genom att fastställa förekomsten av rekursivt uppräknade uppsättningar av mellanliggande grad. Detta banbrytande resultat öppnade en bred studie av Turing-graderna hos de rekursivt uppräknade uppsättningarna som visade sig ha en mycket komplicerad och icke-trivial struktur.

det finns uncountably många uppsättningar som inte är rekursivt uppräkbara, och undersökningen av Turing grader av alla uppsättningar är lika central i rekursionsteorin som undersökningen av de rekursivt uppräkbara Turing grader. Många grader med speciella egenskaper konstruerades: hyperimmunfria grader där varje funktion som kan beräknas i förhållande till den graden majoriseras av en (orelativiserad) beräkningsbar funktion; höga grader i förhållande till vilken man kan beräkna en funktion f som dominerar varje beräkningsbar funktion g i den meningen att det finns en konstant c beroende på g så att g(x) < f(x) för alla x > c; slumpmässiga grader som innehåller algoritmiskt slumpmässiga uppsättningar; 1-generiska grader av 1-generiska uppsättningar; och graderna under stoppproblemet för gräns-rekursiva uppsättningar.

studien av godtyckliga (inte nödvändigtvis rekursivt uppräkbara) Turing-grader involverar studien av Turing-hoppet. Med tanke på en uppsättning A är Turing jump of a en uppsättning naturliga tal som kodar för en lösning på stoppproblemet för oracle Turing-maskiner som körs med oracle A. Turing-hoppet i vilken uppsättning som helst är alltid av högre Turing-grad än den ursprungliga uppsättningen, och en sats av Friedburg visar att alla uppsättningar som beräknar Stoppproblemet kan erhållas som Turing-hoppet i en annan uppsättning. Posts sats etablerar ett nära samband mellan Turing jump-operationen och den aritmetiska hierarkin, som är en klassificering av vissa delmängder av de naturliga talen baserat på deras definierbarhet i aritmetik.

mycket ny forskning om Turing-grader har fokuserat på den övergripande strukturen för uppsättningen Turing-grader och uppsättningen Turing-grader som innehåller rekursivt uppräknade uppsättningar. En djup sats av Shore and Slaman (1999) säger att funktionen som kartlägger en grad x till graden av dess Turing-hopp kan definieras i Turing-gradernas partiella ordning. En ny undersökning av Ambos-Spies och Fejer (2006) ger en översikt över denna forskning och dess historiska utveckling.

övriga minskningarredigera

ett pågående forskningsområde inom rekursionsteoristudier reducerbarhetsrelationer andra än Turing reducerbarhet. Post (1944) introducerade flera starka reducibilities, så kallade eftersom de innebär sanningstabell reducerbarhet. En Turing-maskin som implementerar en stark reducerbarhet kommer att beräkna en total funktion oavsett vilket oracle det presenteras med. Svaga minskningar är de där en reduktionsprocess kanske inte avslutas för alla orakel; Turing reducerbarhet är ett exempel.

de starka minskningarna inkluderar:

en-en reducerbarhet A är en-en reducerbar(eller 1-reducerbar) till B om det finns en total beräkningsbar injicerbar funktion f så att varje n är i A om och endast om f (n) är i B. Många-en reducerbarhet Detta är i huvudsak en-en reducerbarhet utan den begränsning som f är injicerbar. A är många-en reducerbar (eller m-reducerbar) till B om det finns en total beräkningsbar funktion f så att varje n är i A om och endast om f(n) är i B. Sanningstabell reducerbarhet A är sanningstabell reducerbar till B om A är Turing reducerbar till B via en oracle Turing-maskin som beräknar en total funktion oavsett oracle det ges. På grund av kompakthet av Cantor utrymme, Detta motsvarar att säga att minskningen presenterar en enda lista med frågor (beroende endast på input) till oracle samtidigt, och sedan ha sett deras svar kan producera en utgång utan att ställa ytterligare frågor oavsett oracle svar på de ursprungliga frågorna. Många varianter av sanningstabellreducerbarhet har också studerats.

ytterligare minskningar (positiva, disjunktiva, konjunktiva, linjära och deras svaga och begränsade versioner) diskuteras i artikeln reduktion (rekursionsteori).

den stora forskningen om starka minskningar har varit att jämföra deras teorier, både för klassen av alla rekursivt uppräknade uppsättningar såväl som för klassen av alla delmängder av de naturliga talen. Dessutom har relationerna mellan reducerbarheten studerats. Det är till exempel känt att varje Turing-grad antingen är en sanningstabellgrad eller är föreningen av oändligt många sanningstabellgrader.

Reducerbarhet svagare än Turing reducerbarhet (det vill säga reducerbarhet som antyds av Turing reducerbarhet) har också studerats. De mest kända är aritmetisk reducerbarhet och hyperaritmetisk reducerbarhet. Dessa minskningar är nära kopplade till definierbarhet över standardmodellen för aritmetik.

Rice ‘ s theorem and the aritmetical hierarchyEdit

Rice visade att för varje icke-trivial klass C (som innehåller några men inte alla r.e. – uppsättningar) indexuppsättningen E = {e: eth r.e. set vi är i C} har egenskapen att antingen stoppproblemet eller dess komplement är många-en reducerbar till E, det vill säga kan kartläggas med en många-en reduktion till E (se Rices sats för mer detaljer). Men många av dessa indexuppsättningar är ännu mer komplicerade än stoppproblemet. Dessa typer av uppsättningar kan klassificeras med hjälp av den aritmetiska hierarkin. Till exempel är indexuppsättningen FIN för klassen av alla ändliga uppsättningar på nivån 22, indexuppsättningen REC för klassen för alla rekursiva uppsättningar är på nivån 33, indexuppsättningen COFIN för alla kofinitsatser är också på nivån 33 och indexuppsättningen COMP för klassen för alla Turing-kompletta uppsättningar 24. Dessa hierarkinivåer definieras induktivt, innehåller bara alla uppsättningar som är rekursivt uppräkbara i förhållande till den; den innehåller de rekursivt uppräkbara uppsättningarna i enlighet med den; den innehåller de rekursivt uppräkbara uppsättningarna i enlighet med den. Indexuppsättningarna som ges här är till och med kompletta för sina nivåer, det vill säga alla uppsättningar i dessa nivåer kan vara många-en reducerad till de givna indexuppsättningarna.

omvänd mathematicsEdit

programmet för omvänd matematik frågar vilka axiom som är nödvändiga för att bevisa särskilda satser av matematik i delsystem av andra ordningens aritmetik. Denna studie initierades av Harvey Friedman och studerades i detalj av Stephen Simpson och andra; Simpson (1999) ger en detaljerad diskussion om programmet. De aktuella axiomerna motsvarar informellt axiom som säger att kraften hos de naturliga siffrorna är stängd under olika reducerbarhetsbegrepp. Det svagaste sådana axiomet som studeras i omvänd matematik är rekursiv förståelse, vilket säger att Naturals powerset är stängd under Turing reducerbarhet.

NumberingsEdit

en numrering är en uppräkning av funktioner; den har två parametrar, e och x och matar ut värdet på e-th-funktionen i numreringen på ingången x. Siffror kan vara delvis rekursiva även om vissa av dess medlemmar är totalt rekursiva, det vill säga beräkningsbara funktioner. Tillåtna siffror är de som alla andra kan översättas till. A Friedberg numrering (uppkallad efter dess upptäckare) är en en-en numrering av alla partiella rekursiva funktioner; det är nödvändigtvis inte en tillåten numrering. Senare forskning handlade också om siffror av andra klasser som klasser av rekursivt uppräknade uppsättningar. Goncharov upptäckte till exempel en klass av rekursivt uppräkbara uppsättningar för vilka numren faller i exakt två klasser med avseende på rekursiva isomorfismer.

priority methodEdit

för ytterligare förklaring, se avsnittet Postens problem och prioritetsmetoden i artikeln Turing degree.

posts problem löstes med en metod som kallas prioritetsmetoden; ett bevis med denna metod kallas ett prioritetsargument. Denna metod används främst för att konstruera rekursivt uppräkningsbara uppsättningar med särskilda egenskaper. För att använda denna metod delas de önskade egenskaperna hos uppsättningen som ska konstrueras upp i en oändlig lista över mål, så kallade krav, så att uppfyllandet av alla krav kommer att leda till att uppsättningen konstruerad har de önskade egenskaperna. Varje krav tilldelas ett naturligt tal som representerar Kravets prioritet; så 0 tilldelas den viktigaste prioriteten, 1 till den näst viktigaste, och så vidare. Satsen konstrueras sedan i steg, varje steg försöker uppfylla ett av flera av kraven genom att antingen lägga till siffror i uppsättningen eller förbjuda siffror från uppsättningen så att den slutliga uppsättningen uppfyller kravet. Det kan hända att uppfylla ett krav kommer att leda till att en annan blir missnöjd; prioritetsordningen används för att bestämma vad man ska göra i en sådan händelse.

prioriterade argument har använts för att lösa många problem i rekursionsteori och har klassificerats i en hierarki baserat på deras komplexitet (Soare 1987). Eftersom komplexa prioriterade argument kan vara tekniska och svåra att följa har det traditionellt ansetts önskvärt att bevisa resultat utan prioriterade argument eller att se om resultat som bevisats med prioriterade argument också kan bevisas utan dem. Till exempel publicerade Kummer ett papper om ett bevis för förekomsten av Friedberg-nummer utan att använda prioriteringsmetoden.

gitteret av rekursivt enumerable setsEdit

när Post definierade begreppet en enkel uppsättning som en r. e. uppsättning med ett oändligt komplement som inte innehåller någon oändlig r.e. set började han studera strukturen för de rekursivt uppräknade uppsättningarna under inkludering. Denna gitter blev en väl studerad struktur. Rekursiva uppsättningar kan definieras i denna struktur med det grundläggande resultatet att en uppsättning är rekursiv om och endast om uppsättningen och dess komplement båda är rekursivt uppräknade. Oändliga r. e. uppsättningar har alltid oändliga rekursiva delmängder; men å andra sidan finns enkla uppsättningar men har inte en coinfinite rekursiv superset. Post (1944) introducerade redan hypersimple och hyperhypersimple uppsättningar; senare maximala uppsättningar konstruerades som är r.E. uppsättningar så att varje r.e. superset är antingen en ändlig variant av den givna maximala uppsättningen eller är samändad. Posts ursprungliga motivation i studien av denna gitter var att hitta en strukturell uppfattning så att varje uppsättning som uppfyller denna egenskap varken är i Turing-graden av de rekursiva uppsättningarna eller i Turing-graden av stoppproblemet. Post hittade inte en sådan egenskap och lösningen på hans problem tillämpade istället prioriterade metoder; Harrington och Soare (1991) hittade så småningom en sådan egenskap.

Automorfismproblemsedit

en annan viktig fråga är förekomsten av automorfismer i rekursionsteoretiska strukturer. En av dessa strukturer är att en av rekursivt uppräkningsbara uppsättningar under inkluderingsmodulo ändlig skillnad; i denna struktur är A under B om och endast om den inställda skillnaden B − A är ändlig. Maximala uppsättningar (enligt definitionen i föregående stycke) har egenskapen att de inte kan vara automorfa till icke-maximala uppsättningar, det vill säga om det finns en automorfism av de rekursiva uppräkningsbara uppsättningarna under den struktur som just nämnts, mappas varje maximal uppsättning till en annan maximal uppsättning. Soare (1974) visade att även converse håller, det vill säga varannan maximala uppsättningar är automorfa. Så de maximala uppsättningarna bildar en bana, det vill säga varje automorfism bevarar maximalitet och alla två maximala uppsättningar omvandlas till varandra av någon automorfism. Harrington gav ytterligare ett exempel på en automorfisk egenskap: den för de kreativa uppsättningarna, uppsättningarna som är många-en motsvarar stoppproblemet.

förutom gitteret av rekursivt uppräknade uppsättningar studeras också automorfismer för strukturen för Turing-graderna för alla uppsättningar såväl som för strukturen för Turing-graderna för r.e. – uppsättningar. I båda fallen, Cooper påstår sig ha konstruerat icke-triviala automorfismer som kartlägger vissa grader till andra grader; denna konstruktion har dock inte verifierats och vissa kollegor tror att konstruktionen innehåller fel och att frågan om det finns en icke-trivial automorfism av Turing-graderna fortfarande är en av de viktigaste olösta frågorna på detta område (Slaman och Woodin 1986, Ambos-Spies and Fejer 2006).

Kolmogorov komplexitetedit

fältet Kolmogorov complexity and algorithmic randomness utvecklades under 1960-och 1970-talet av Chaitin, Kolmogorov, Levin, Martin-L Jacobf och Solomonoff (namnen ges här i alfabetisk ordning; mycket av forskningen var oberoende, och enheten i begreppet slumpmässighet förstod inte vid den tiden). Huvudideen är att överväga en universell Turing-maskin U och att mäta komplexiteten hos ett tal (eller sträng) x som längden på den kortaste ingången p så att U(p) matar ut x. Detta tillvägagångssätt revolutionerade tidigare sätt att bestämma när en oändlig sekvens (ekvivalent, karakteristisk funktion av en delmängd av de naturliga talen) är slumpmässig eller inte genom att åberopa en uppfattning om slumpmässighet för ändliga objekt. Kolmogorov komplexitet blev inte bara ett ämne för självständig studie men tillämpas också på andra ämnen som ett verktyg för att få bevis.Det finns fortfarande många öppna problem på detta område. Av den anledningen hölls en ny forskningskonferens på detta område i januari 2007 och en lista över öppna problem upprätthålls av Joseph Miller och Andre Nies.

Frekvensberäknaredit

denna gren av rekursionsteori analyserade följande Fråga: för fast m och n med 0 < m < n, för vilka funktioner A är det möjligt att beräkna för olika n-ingångar x1, x2, …, xn en tupel av n nummer y1, y2,…, yn så att minst m av ekvationerna A (xk) = yk är sanna. Sådana uppsättningar är kända som (m, n)-rekursiva uppsättningar. Det första stora resultatet i denna gren av Rekursionsteori är Trakhtenbrots resultat att en uppsättning kan beräknas om den är (m, n)-rekursiv för vissa m, n med 2m > n. Å andra sidan är Jockuschs halvrekursiva uppsättningar (som redan var kända informellt innan Jockusch introducerade dem 1968) exempel på en uppsättning som är (m, n)-rekursiv om och endast om 2m < n + 1. Det finns uncountably många av dessa uppsättningar och även några rekursivt uppräkningsbara men icke-beräkningsbara uppsättningar av denna typ. Senare etablerade Degtev en hierarki av rekursivt uppräknade uppsättningar som är (1, n + 1)-rekursiva men inte (1, n)-rekursiva. Efter en lång fas av forskning av ryska forskare blev detta ämne repopulariserat i väst av Beigels avhandling om begränsade frågor, som kopplade frekvensberäkning till ovan nämnda begränsade minskningar och andra relaterade begrepp. Ett av de viktigaste resultaten var Kummer ‘ s Kardinalitetsteori som säger att en uppsättning A kan beräknas om och endast om det finns en n sådan att någon algoritm räknar upp för varje tupel av n olika nummer upp till N många möjliga val av kardinaliteten hos denna uppsättning n-nummer korsade med A; dessa val måste innehålla den sanna kardinaliteten men utelämna minst en falsk.

Induktiv inferensredigera

detta är den rekursionsteoretiska grenen av inlärningsteori. Den bygger på E. Mark Golds modell för lärande i gränsen från 1967 och har sedan dess utvecklat fler och fler modeller av lärande. Det allmänna scenariot är följande: Med tanke på en klass S av beräkningsbara funktioner, finns det en elev (det vill säga rekursiv funktionell) som matar ut för någon inmatning av formuläret (f(0), f(1),…, f(n)) en hypotes. En elev m lär sig en funktion f om nästan alla hypoteser är samma index e av f med avseende på en tidigare överenskommen acceptabel numrering av alla beräkningsbara funktioner; M lär sig S om M lär sig varje f i S. grundläggande resultat är att alla rekursivt uppräknade klasser av funktioner är lärbara medan klassen REC av alla beräkningsbara funktioner inte är Lärbar. Många relaterade modeller har beaktats och även inlärning av klasser av rekursivt uppräknade uppsättningar från positiva data är ett ämne som studerats från Gulds banbrytande papper 1967 och framåt.

generaliseringar av Turing computabilityEdit

Rekursionsteori inkluderar studier av generaliserade föreställningar om detta område, såsom aritmetisk reducerbarhet, hyperaritmetisk reducerbarhet och Sacks (1990). Dessa generaliserade begrepp inkluderar reducibiliteter som inte kan utföras av Turing-maskiner men är ändå naturliga generaliseringar av Turing-reducerbarhet. Dessa studier inkluderar metoder för att undersöka den analytiska hierarkin som skiljer sig från den aritmetiska hierarkin genom att tillåta kvantifiering över uppsättningar av naturliga tal utöver kvantifiering över enskilda tal. Dessa områden är kopplade till teorierna om välordningar och träd; till exempel är uppsättningen av alla index av rekursiva (icke-binära) träd utan oändliga grenar komplett för Nivå 1 1 1 {\displaystyle \ Pi _{1}^{1}}

den analytiska hierarkin. Både Turing reducerbarhet och hyperaritmetisk reducerbarhet är viktiga inom området effektiv beskrivande uppsättningsteori. Den ännu mer allmänna uppfattningen om konstruktionsgrader studeras i uppsättningsteori.

kontinuerlig beräkningsteoriredigera

beräkningsteori för digital beräkning är väl utvecklad. Beräkningsteori är mindre välutvecklad för analog beräkning som förekommer i analoga datorer, analog signalbehandling, analog elektronik, neurala nätverk och kontinuerlig tidskontrollteori, modellerad av differentialekvationer och kontinuerliga dynamiska system (Orponen 1997; Moore 1996).