Beregnelighedsteori

begyndende med teorien om rekursive sæt og funktioner beskrevet ovenfor er feltet rekursionsteori vokset til at omfatte studiet af mange nært beslægtede emner. Dette er ikke uafhængige forskningsområder: hvert af disse områder trækker ideer og resultater fra de andre, og de fleste rekursionsteoretikere kender de fleste af dem.

relativ beregningsevne og Turing-graderneredit

Rekursionsteori i matematisk logik har traditionelt fokuseret på relativ beregnelighed, en generalisering af Turing beregnelighed defineret ved hjælp af oracle Turing-maskiner, introduceret af Turing (1939). En oracle Turing-maskine er en hypotetisk enhed, der ud over at udføre handlingerne fra en almindelig Turing-maskine er i stand til at stille spørgsmål til et orakel, som er et bestemt sæt naturlige tal. Oracle-Maskinen må kun stille spørgsmål til formularen ” er n i oracle-Sættet?”. Hvert spørgsmål besvares straks korrekt, selvom oracle-sættet ikke kan beregnes. Således vil en orakelmaskine med et ikke-kompatibelt orakel være i stand til at beregne Sæt, som en Turing-maskine uden et orakel ikke kan.

uformelt kan et sæt naturlige tal a reduceres til et sæt B, hvis der er en orakelmaskine, der korrekt fortæller, om tal er i A, når de køres med B som orakelsættet (i dette tilfælde siges Sættet A også at være (relativt) beregneligt fra B og rekursivt i B). Hvis et sæt A er Turing reducerbar til et sæt B og B er Turing reducerbar til A, siges sætene at have den samme Turing-grad (også kaldet grad af uløselighed). Turing-graden af et sæt giver et præcist mål for, hvor ukomputabelt sættet er.

de naturlige eksempler på sæt, der ikke kan beregnes, inklusive mange forskellige sæt, der koder for varianter af stopproblemet, har to egenskaber til fælles:

1. de er rekursivt tællelige, og
2. hver kan oversættes til enhver anden via en mange-en reduktion. Det vil sige, givet sådanne sæt A og B, er der en total beregnelig funktion f sådan, at a = {h : f(h) b}. Disse sæt siges at være mange-en ækvivalent (eller m-ækvivalent).

mange-en-reduktioner er “stærkere” end Turing-reduktioner: hvis et sæt A er mange-en reducerbar til et sæt B, så er A Turing reducerbar til B, men det omvendte holder ikke altid. Selvom de naturlige eksempler på ikke-beregnelige sæt alle er mange-en ækvivalente, er det muligt at konstruere rekursivt tællelige sæt A og B således, at A er Turing reducerbar til B, men ikke mange-en reducerbar til B. Det kan vises, at ethvert rekursivt optælleligt sæt er mange-en reducerbart til standsningsproblemet, og dermed er standsningsproblemet det mest komplicerede rekursivt optællelige sæt med hensyn til mange-en reducerbarhed og med hensyn til Turing reducerbarhed. Post (1944) spurgte, om hvert rekursivt optælleligt sæt enten kan beregnes eller Turing svarer til stopproblemet, det vil sige, om der ikke er noget rekursivt optællbart sæt med en Turing-grad mellemliggende mellem disse to.

som mellemliggende resultater, post definerede naturlige typer af rekursivt enumerable Sæt som de enkle, hypersimple og hyperhypersimple sæt. Post viste, at disse sæt er strengt mellem de beregnelige sæt og stopproblemet med hensyn til mange-en reducerbarhed. Post viste også, at nogle af dem er strengt mellemliggende under andre reduktionsbegreber stærkere end Turing reducerbarhed. Men Post forlod det største problem med eksistensen af rekursivt opregnede sæt mellemliggende Turing-grad; dette problem blev kendt som posts problem. Efter ti år viste Kleene og Post i 1954, at der er mellemliggende Turing-grader mellem dem i de beregnelige sæt og stopproblemet, men de kunne ikke vise, at nogen af disse grader indeholder et rekursivt tælleligt sæt. Meget kort efter dette løste Friedberg og Muchnik uafhængigt posts problem ved at fastslå eksistensen af rekursivt opregnede sæt mellemliggende grad. Dette banebrydende resultat åbnede en bred undersøgelse af Turing-graderne i de rekursivt tællelige Sæt, som viste sig at have en meget kompliceret og ikke-triviel struktur.

der er utallige mange sæt, der ikke er rekursivt tællelige, og undersøgelsen af Turing-graderne for alle sæt er lige så central i rekursionsteori som undersøgelsen af de rekursivt tællelige Turing-grader. Mange grader med specielle egenskaber blev konstrueret: hyperimmunfrie grader, hvor hver funktion, der kan beregnes i forhold til den grad, er majoriseret af en (ikke-relativiseret) beregningsfunktion; høje grader i forhold til hvilken man kan beregne en funktion f som dominerer hver beregnelig funktion g i den forstand, at der er en konstant c afhængig af g sådan, at g (< f ( * ) for alle > c; tilfældige grader indeholdende algoritmisk tilfældige sæt; 1-generiske grader af 1-generiske sæt; og graderne under standsning problemet med grænse-rekursive sæt.

undersøgelsen af vilkårlige (ikke nødvendigvis rekursivt tællelige) Turing-grader involverer studiet af Turing-springet. Givet et sæt A, Turing jump of a er et sæt naturlige tal, der koder for en løsning på standsningsproblemet for oracle Turing-maskiner, der kører med oracle A. Turing-springet i ethvert sæt er altid af højere Turing-grad end det originale sæt, og en sætning af Friedburg viser, at ethvert sæt, der beregner Stopproblemet, kan opnås som Turing-springet i et andet sæt. Posts sætning etablerer et tæt forhold mellem Turing jump-operationen og det aritmetiske hierarki, som er en klassificering af visse undergrupper af de naturlige tal baseret på deres definerbarhed i aritmetik.

meget nyere forskning i Turing-grader har fokuseret på den overordnede struktur af sættet af Turing-grader og sættet af Turing-grader, der indeholder rekursivt tællelige sæt. En dyb sætning af Shore og Slaman (1999) siger, at funktionen, der kortlægger en grad til graden af dens Turing-Spring, kan defineres i den delvise rækkefølge af Turing-graderne. En nylig undersøgelse foretaget af Ambos-Spies and Fejer (2006) giver et overblik over denne forskning og dens historiske udvikling.

andre reduktionerrediger

et igangværende forskningsområde inden for rekursionsteori studerer reduktionsrelationer bortset fra Turing reducerbarhed. Post (1944) introducerede flere stærke reduktioner, så navngivet, fordi de indebærer sandhed-tabelreducerbarhed. En Turing-maskine, der implementerer en stærk reducerbarhed, beregner en total funktion uanset hvilket orakel det præsenteres for. Svage reduktioner er dem, hvor en reduktionsproces muligvis ikke afsluttes for alle orakler; Turing reducerbarhed er et eksempel.

de stærke reduktioner inkluderer:

en-en reducerbarhed A er en-en reducerbar (eller 1-reducerbar) til B, hvis der er en total beregnelig injektionsfunktion f, således at hver n er i en hvis og kun hvis f(n) er i B. mange-en reducerbarhed dette er i det væsentlige en-en reducerbarhed uden den begrænsning, at f er injektiv. A er mange-en reducerbar(eller m-reducerbar) til B, hvis der er en total beregningsfunktion f, således at hver n er i A, hvis og kun hvis f (n) er i B. Truth-table reducerbarhed A er truth-table reducerbar til B, hvis A er Turing reducerbar til B via en oracle Turing-maskine, der beregner en total funktion uanset det orakel, den er givet. På grund af Cantor-pladsens kompakthed svarer dette til at sige, at reduktionen præsenterer en enkelt liste med spørgsmål (afhængigt af input) til oraklet samtidigt, og efter at have set deres svar er det i stand til at producere et output uden at stille yderligere spørgsmål uanset oraklets svar på de oprindelige forespørgsler. Mange varianter af sandhedstabellens reducerbarhed er også blevet undersøgt.

yderligere reduktioner (positive, disjunktive, konjunktive, lineære og deres svage og afgrænsede versioner) diskuteres i artiklen reduktion (rekursionsteori).

den største forskning i stærke reduktioner har været at sammenligne deres teorier, både for klassen af alle rekursivt tællelige sæt såvel som for klassen af alle undergrupper af de naturlige tal. Desuden er forholdet mellem reduktionerne blevet undersøgt. For eksempel er det kendt, at enhver Turing-grad enten er en sandhedstabelgrad eller er foreningen af uendeligt mange sandhedstabelgrader.

reduktioner svagere end Turing reducerbarhed (det vil sige reduktioner, der antydes af Turing reducerbarhed) er også blevet undersøgt. De mest kendte er aritmetisk reducerbarhed og hyperaritmisk reducerbarhed. Disse reduktioner er tæt forbundet med definerbarhed over standardmodellen for aritmetik.

Rice ‘ s sætning og det aritmetiske hierarkidit

Rice viste, at for hver nontrivial klasse C (som indeholder nogle, men ikke alle r.E. sæt) indekset sæt E = {e: eth r.e. sæt vi er i C} har den egenskab, at enten stopproblemet eller dets komplement er mange-en reducerbar til E, det vil sige, kan kortlægges ved hjælp af en mange-en reduktion til E (se Rice ‘ s sætning for flere detaljer). Men mange af disse indekssæt er endnu mere komplicerede end stopproblemet. Denne type sæt kan klassificeres ved hjælp af det aritmetiske hierarki. For eksempel er indekssættet FIN af klasse af alle endelige sæt på niveauet Lus2, indekssættet REC for klassen af alle rekursive sæt er på niveauet Lus3, indekssættet COFIN for alle medfinite sæt er også på niveauet Lus3 og indekssættet COMP for klassen af alle Turing-komplette sæt Lus4. Disse hierarkiniveauer er defineret induktivt, Pristn + 1 indeholder bare alle sæt, der er rekursivt tællelige i forhold til Pristn; Prist1 indeholder rekursivt tællelige sæt. Indekssættene, der er angivet her, er endda komplette for deres niveauer, det vil sige, at alle sæt i disse niveauer kan være mange-en reduceret til de givne indekssæt.

Reverse mathematicsEdit

programmet for reverse mathematics spørger, hvilke sæt-eksistens aksiomer der er nødvendige for at bevise bestemte sætninger af matematik i delsystemer af andenordens aritmetik. Denne undersøgelse blev indledt af Harvey Friedman og blev undersøgt detaljeret af Stephen Simpson m.fl.; Simpson (1999) giver en detaljeret diskussion af programmet. De pågældende sæteksistensaksiomer svarer uformelt til aksiomer, der siger, at kraften i de naturlige tal er lukket under forskellige reduktionsbegreber. Det svageste sådant aksiom, der studeres i omvendt matematik, er rekursiv forståelse, der siger, at naturalernes kraftsæt er lukket under Turing-reducerbarhed.

NumberingsEdit

en nummerering er en optælling af funktioner; den har to parametre, e og H og udsender værdien af e-TH-funktionen i nummereringen på input h. Nummereringer kan være delvis rekursive, selvom nogle af dets medlemmer er samlede rekursive, det vil sige beregnelige funktioner. Antagelige tal er dem, som alle andre kan oversættes til. En Friedberg nummerering (opkaldt efter dens opdager) er en en-en nummerering af alle delvise rekursive funktioner; det er nødvendigvis ikke en tilladt nummerering. Senere forskning behandlede også nummereringer af andre klasser som klasser af rekursivt tællelige sæt. Goncharov opdagede for eksempel en klasse af rekursivt optællelige sæt, for hvilke antallet falder i nøjagtigt to klasser med hensyn til rekursive isomorfier.

prioritetsmetodendit

For yderligere forklaring, se afsnittet Postens problem og prioritetsmetoden i artiklen Turing grad.

posts problem blev løst med en metode kaldet prioritetsmetoden; et bevis ved hjælp af denne metode kaldes et prioritetsargument. Denne metode bruges primært til at konstruere rekursivt optællelige sæt med særlige egenskaber. For at bruge denne metode opdeles de ønskede egenskaber for det sæt, der skal konstrueres, i en uendelig liste over mål, kendt som krav, således at opfyldelse af alle kravene får det konstruerede sæt til at have de ønskede egenskaber. Hvert krav tildeles et naturligt tal, der repræsenterer kravets prioritet; så 0 tildeles den vigtigste prioritet, 1 til den næstvigtigste osv. Sættet konstrueres derefter i etaper, hvor hvert trin forsøger at opfylde et af flere af kravene ved enten at tilføje numre til sættet eller forbyde numre fra sættet, så det endelige sæt opfylder kravet. Det kan ske, at opfyldelse af et krav vil få en anden til at blive utilfreds; prioritetsordren bruges til at beslutte, hvad de skal gøre i en sådan begivenhed.

prioriterede argumenter er blevet anvendt til at løse mange problemer i rekursionsteori og er blevet klassificeret i et hierarki baseret på deres kompleksitet (Soare 1987). Fordi komplekse prioriterede argumenter kan være tekniske og vanskelige at følge, har det traditionelt været anset for ønskeligt at bevise resultater uden prioriterede argumenter eller for at se, om resultater bevist med prioriterede argumenter også kan bevises uden dem. For eksempel offentliggjorde Kummer et papir om et bevis for eksistensen af Friedberg-nummereringer uden at bruge prioritetsmetoden.

gitteret af rekursivt tællelige sætredit

når Post definerede begrebet et simpelt sæt som et r.e. sæt med et uendeligt komplement, der ikke indeholder nogen uendelig r.e. set begyndte han at studere strukturen af de rekursivt tællelige sæt under optagelse. Dette gitter blev en velstuderet struktur. Rekursive sæt kan defineres i denne struktur ved det grundlæggende resultat, at et sæt er rekursivt, hvis og kun hvis sættet og dets komplement begge er rekursivt tællelige. Uendelige r.e. sæt har altid uendelige rekursive undergrupper; men på den anden side findes der enkle sæt, men har ikke et coinfinit rekursivt supersæt. Post (1944) introducerede allerede hypersimple og hyperhypersimple sæt; senere blev der konstrueret maksimale sæt, som er r.e. sæt, således at hver r.e. superset er enten en endelig variant af det givne maksimale sæt eller er co-endelig. Posts oprindelige motivation i studiet af dette gitter var at finde en strukturel opfattelse, således at hvert sæt, der opfylder denne egenskab, hverken er i Turing-graden af de rekursive sæt eller i Turing-graden af stopproblemet. Post fandt ikke en sådan ejendom, og løsningen på hans problem anvendte prioriterede metoder i stedet; Harrington og Soare (1991) fandt til sidst en sådan ejendom.

Automorfisme problemsEdit

et andet vigtigt spørgsmål er eksistensen af automorfier i rekursionsteoretiske strukturer. En af disse strukturer er den ene af rekursivt optællelige sæt under inklusionsmodulo endelig forskel; i denne struktur er A under B, hvis og kun hvis den indstillede forskel B − A er endelig. Maksimale sæt (som defineret i det foregående afsnit) har den egenskab, at de ikke kan være automorfe til ikke-maksimale sæt, det vil sige, hvis der er en automorfisme af de rekursive tællbare sæt under den netop nævnte struktur, kortlægges hvert maksimalt sæt til et andet maksimalt sæt. Soare (1974) viste, at også det omvendte holder, det vil sige hvert to maksimale sæt er automorfe. Så de maksimale sæt danner en bane, det vil sige, hver automorfisme bevarer maksimalitet, og to maksimale sæt omdannes til hinanden af en eller anden automorfisme. Harrington gav et yderligere eksempel på en automorf egenskab: den af de kreative sæt, de sæt, der er mange-en svarende til stopproblemet.

udover gitteret af rekursivt tællelige sæt studeres automorfier også for strukturen af Turing-graderne i alle sæt såvel som for strukturen af Turing-graderne i r.E. sæt. I begge tilfælde, Cooper hævder at have konstrueret ikke-trivielle automorfier, der kortlægger nogle grader til andre grader; denne konstruktion er imidlertid ikke blevet verificeret, og nogle kolleger mener, at konstruktionen indeholder fejl, og at spørgsmålet om, hvorvidt der er en ikke-privat automorfisme i Turing-graderne, stadig er et af de vigtigste uløste spørgsmål på dette område (Slaman og Træi 1986, Ambos-Spies og Fejer 2006).

Kolmogorov kompleksitetrediger

feltet Kolmogorov kompleksitet og algoritmisk tilfældighed blev udviklet i løbet af 1960 ‘erne og 1970’ erne af Chaitin, Kolmogorov, Levin, Martin-L Larf og Solomonoff (navnene er angivet her i alfabetisk rækkefølge; meget af forskningen var uafhængig, og enheden i begrebet tilfældighed blev ikke forstået på det tidspunkt). Hovedideen er at overveje en universel Turing-maskine U og at måle kompleksiteten af et tal (eller streng) H som længden af den korteste indgang p sådan at U(p) udgange h. Denne tilgang revolutionerede tidligere måder at bestemme, hvornår en uendelig sekvens (ækvivalent, karakteristisk funktion af en delmængde af de naturlige tal) er tilfældig eller ej ved at påberåbe sig en forestilling om tilfældighed for endelige objekter. Kolmogorov kompleksitet blev ikke kun et emne for uafhængig undersøgelse, men anvendes også til andre emner som et redskab til at opnå bevis.Der er stadig mange åbne problemer på dette område. Af den grund blev der for nylig afholdt en forskningskonference på dette område i januar 2007, og en liste over åbne problemer opretholdes af Joseph Miller og Andre Nies.

Frekvensberegningredit

denne gren af rekursionsteori analyserede følgende spørgsmål: for fast m og n med 0 < m < n, for hvilke funktioner A er det muligt at beregne for forskellige N-indgange H1, H2, …, en tupel af N-numre y1, y2,…,yn sådan, at mindst m af ligningerne a(KK) = yk er sande. Sådanne sæt er kendt som (m, n)-rekursive sæt. Det første store resultat i denne gren af Rekursionsteori er Trakhtenbrots resultat, at et sæt kan beregnes, hvis det er (m, n)-rekursivt for nogle m, n med 2m > n. På den anden side er Jockuschs semirecursive Sæt (som allerede var kendt uformelt før Jockusch introducerede dem 1968) eksempler på et sæt, der er (m, n)-rekursiv hvis og kun hvis 2m < n + 1. Der er utallige mange af disse sæt og også nogle rekursivt tællelige, men ikke-beregnelige sæt af denne type. Senere etablerede Degtev et hierarki af rekursivt optællelige sæt, der er (1, n + 1)-rekursive, men ikke (1, n)-rekursive. Efter en lang fase af forskning fra russiske forskere blev dette emne genpopulariseret i Vesten af Beigels afhandling om afgrænsede forespørgsler, som forbandt frekvensberegning med de ovennævnte afgrænsede reduktioner og andre relaterede forestillinger. Et af de største resultater var Kummer ‘ s Kardinalitetsteori, der siger, at et sæt A kan beregnes, hvis og kun hvis der er en n sådan, at en algoritme opregner for hver tupel af n forskellige tal op til n mange mulige valg af kardinaliteten af dette sæt n-numre krydset med en; disse valg skal indeholde den sande kardinalitet, men udelade mindst en falsk.

Induktiv inferenceredit

dette er den rekursionsteoretiske gren af læringsteori. Det er baseret på E. Mark Golds læringsmodel i grænsen fra 1967 og har siden da udviklet flere og flere læringsmodeller. Det generelle scenario er følgende: givet en klasse S af beregnelige funktioner, er der en elev (det vil sige rekursiv funktionel), der udsender for ethvert input af formularen (f(0), f(1),…, f(n)) en hypotese. En elev m lærer en funktion f Hvis næsten alle hypoteser er det samme indeks e for f med hensyn til en tidligere aftalt acceptabel nummerering af alle beregnelige funktioner; m lærer S Hvis M lærer hver f I S. grundlæggende resultater er, at alle rekursivt opregnede klasser af funktioner kan læres, mens klassen REC for alle beregnelige funktioner ikke kan læres. Mange relaterede modeller er blevet overvejet, og også læring af klasser af rekursivt tællelige sæt fra positive data er et emne studeret fra Gold ‘ s banebrydende papir i 1967 og fremefter.

generaliseringer af Turing computabilityEdit

Rekursionsteori inkluderer studiet af generaliserede forestillinger om dette felt, såsom aritmetisk reducerbarhed, hyperaritmetisk reducerbarhed og kur-rekursionsteori, som beskrevet af Sacks (1990). Disse generaliserede forestillinger inkluderer reduktioner, der ikke kan udføres af Turing-maskiner, men ikke desto mindre er naturlige generaliseringer af Turing-reducerbarhed. Disse undersøgelser inkluderer tilgange til at undersøge det analytiske hierarki, der adskiller sig fra det aritmetiske hierarki ved at tillade kvantificering over sæt naturlige tal ud over kvantificering over individuelle tal. Disse områder er knyttet til teorierne om velordrer og træer; for eksempel er sættet med alle indekser af rekursive (ikke-binære) træer uden uendelige grene komplet til niveau 1 1 {\displaystyle \ Pi _{1}^{1}}

det analytiske hierarki. Både Turing reducerbarhed og hyperaritetisk reducerbarhed er vigtige inden for effektiv beskrivende sætteori. Den endnu mere generelle opfattelse af grader af konstruktion er undersøgt i sætteori.

Continuous computability theoryEdit

Computability teori for digital beregning er veludviklet. Beregningsteori er mindre veludviklet til analog beregning, der forekommer i analoge computere, analog signalbehandling, analog elektronik, neurale netværk og kontinuerlig tidskontrolteori, modelleret af differentialligninger og kontinuerlige dynamiske systemer (Orponen 1997; Moore 1996).