Computability theory

begynner med teorien om rekursive sett og funksjoner beskrevet ovenfor, innen rekursjon teori har vokst til å omfatte studier av mange nært beslektede emner. Disse er ikke uavhengige forskningsområder: hvert av disse områdene trekker ideer og resultater fra de andre, og de fleste rekursjonsteoretikere er kjent med de fleste av dem.

Relativ beregningsevne og Turinggradenrediger

Rekursjonsteori i matematisk logikk har tradisjonelt fokusert på relativ computability, en generalisering Av Turing computability definert ved hjelp av oracle Turing machines, introdusert Av Turing (1939). En orakel-Turingmaskin er en hypotetisk enhet som, i tillegg til å utføre handlingene til en vanlig Turingmaskin, er i stand til å stille spørsmål til et orakel, som er et bestemt sett med naturlige tall. Oracle-maskinen kan bare stille spørsmål om skjemaet ” Er n i oracle-settet ?”. Hvert spørsmål blir umiddelbart besvart riktig, selv om oracle-settet ikke kan beregnes. Dermed vil en orakelmaskin med et ikke-computable oracle kunne beregne sett som En Turing-maskin uten et orakel ikke kan.

Uformelt Er et sett med naturlige tall a Turing reduserbart til et sett B hvis det er en orakelmaskin som korrekt forteller om tallene er I A når de kjøres Med B som orakelsettet(i dette tilfellet er settet A også sagt å være (relativt) beregningsbar fra B og rekursiv I B). Hvis et sett A er Turing reduserbart Til et sett B og B Er Turing reduserbart Til A, sies settene å ha samme Turinggrad (også kalt grad av unsolvability). Turing-graden til et sett gir et nøyaktig mål på hvor uforanderlig settet er.

de naturlige eksemplene på sett som ikke kan beregnes, inkludert mange forskjellige sett som koder for varianter av stoppproblemet, har to egenskaper til felles:

1. de er rekursivt nummererbare, og
2. hver kan oversettes til noen andre via en mange-en reduksjon. Det vil si, gitt slike sett A og B, er det en total beregningsbar funksjon f slik At A = {x: f(x) ∈ B}. Disse settene sies å være mange-en ekvivalent (eller m-ekvivalent).

Mange-en reduksjoner er “sterkere” enn Turing reduksjoner: hvis et sett A er mange-en reduksjons til et sett B, Så Er A Turing reduksjons til B, men det motsatte holder ikke alltid. Selv om de naturlige eksemplene på ikke-computable sett er alle mange-en ekvivalent, er det mulig å konstruere rekursivt nummererbare sett A og B slik At A Er Turing kan reduseres Til B, men ikke mange-en kan reduseres Til B. Det kan bli vist at hvert rekursivt nummererbart sett er mange-en-reduserbart til stoppproblemet, og dermed er stoppproblemet det mest kompliserte rekursivt nummererbart sett med hensyn til mange-en-reduksjonsevne og Med hensyn til Turing-reduksjonsevne. Post (1944) spurte om hvert rekursivt nummererbart sett enten er beregningsbart Eller Turing tilsvarende stoppeproblemet, det vil si om det ikke er noe rekursivt nummererbart sett med En Turing-grad mellom disse to.

Som mellomliggende resultater, Legg inn definerte naturlige typer rekursivt nummererbare sett som de enkle, hypersimple og hyperhypersimple settene. Post viste at disse settene er strengt mellom computable settene og stoppeproblemet med hensyn til mange-en reduksjonsevne. Post viste også at noen av dem er strengt mellomliggende under andre reduksjonsbegreper sterkere Enn Turing reducibility. Men Post igjen åpne hovedproblemet med eksistensen av rekursivt enumerable sett med mellomliggende Turing grad; dette problemet ble kjent Som Post problem. Etter ti år, Kleene og Post viste i 1954 at det er mellomliggende Turing grader mellom de av computable sett og stoppe problemet, men de klarte ikke å vise at noen av disse grader inneholder en rekursivt enumerable sett. Kort tid etter dette løste Friedberg og Muchnik Uavhengig Posts problem ved å etablere eksistensen av rekursivt nummererbare sett med mellomliggende grad. Dette banebrytende resultatet åpnet en bred studie Av Turing grader av rekursivt enumerable sett som viste seg å ha en svært komplisert og ikke-triviell struktur.

det er utallige mange sett som ikke er rekursivt nummererbare, og undersøkelsen Av Turing-grader av alle sett er like sentral i rekursjonsteori som undersøkelsen av de rekursivt nummererbare Turing-grader. Mange grader med spesielle egenskaper ble konstruert: hyperimmune-fri grader hvor hver funksjon computable i forhold til den graden er majorized av en (unrelativized) computable funksjon; høye grader i forhold til hvilken man kan beregne en funksjon f som dominerer hver beregningsbar funksjon g i den forstand at det er en konstant c avhengig av g slik at g(x) < f (x) for alle x > c; tilfeldige grader som inneholder algoritmisk tilfeldige sett; 1-generiske grader av 1-generiske sett; og grader under stoppproblemet med grense-rekursive sett.

studiet av vilkårlig (ikke nødvendigvis rekursivt enumerable) Turing grader innebærer studiet Av Turing hopp. Gitt et sett a, Er Turinghoppet til a et sett med naturlige tall som koder for en løsning på stoppproblemet for oracle Turing-maskiner som kjører med oracle A. Turinghoppet til et sett er alltid av høyere Turing-grad enn det opprinnelige settet, og Et teorem av Friedburg viser at et sett som beregner Stoppproblemet kan oppnås som Turinghoppet til et annet sett. Posts teorem etablerer et nært forhold Mellom Turing jump-operasjonen og aritmetisk hierarki, som er en klassifisering av visse undergrupper av de naturlige tallene basert på deres definabilitet i aritmetikk.

Mye nyere forskning På Turing grader har fokusert på den generelle strukturen i settet Av Turing grader og settet Av Turing grader som inneholder rekursivt enumerable sett. En dyp teorem Av Shore Og Slaman (1999) sier at funksjonen kartlegging en grad x til graden Av Sin Turing hopp er definerbar i den delvise rekkefølgen Av Turing grader. En nylig undersøkelse Av Ambos-Spies and Fejer (2006) gir en oversikt over denne forskningen og dens historiske progresjon.

Andre reduksjonsbiliteterrediger

et pågående forskningsområde i rekursjonsteoristudier, reducibility relations other than Turing reducibility. Post (1944) introduserte flere sterke reduksjonsordninger, så kalt fordi de innebærer truth-table reducibility. En Turing-maskin som implementerer en sterk reduksjonsevne, vil beregne en total funksjon uavhengig av hvilket oracle den presenteres med. Svake reduksjonsordninger er de hvor en reduksjonsprosess ikke kan opphøre for alle orakler; Turing reducibility er et eksempel.

de sterke reduksjonsanleggene inkluderer:

en-en-reduserbarhet A er en-en-reduserbar (eller 1-reduserbar) Til B hvis det er en total beregningsbar injektiv funksjon f slik at hver n er i a hvis og bare hvis f (n) er I B. Mange-en-reduksjonsevne Dette er i hovedsak en-en reduksjonsevne uten begrensningen at f er injektiv. A er mange-en reduserbar (eller m-reduserbar) til B hvis det er en total beregningsbar funksjon f slik at hver n er i a hvis og bare hvis f (n) er I B. Truth-table reducibility A er truth-table reducible til B hvis A er Turing reducible til B via en oracle Turing maskin som beregner en total funksjon uavhengig av oracle det er gitt. På grunn Av kompaktiteten Til Cantor-rommet, svarer dette til å si at reduksjonen presenterer en enkelt liste over spørsmål (avhengig av inngangen) til orakelet samtidig, og da de har sett svarene deres, kan de produsere en utgang uten å stille flere spørsmål uavhengig av orakelens svar på de første spørringene. Mange varianter av truth-table reducibility har også blitt studert.

Ytterligere reduksjonsegenskaper (positiv, disjunktiv, konjunktiv, lineær og deres svake og avgrensede versjoner) er omtalt i Artikkelen Reduksjon (rekursjonsteori).

hovedforskningen på sterke reduksjonsverdier har vært å sammenligne deres teorier, både for klassen av alle rekursivt nummererbare sett så vel som for klassen av alle undergrupper av de naturlige tallene. Videre har forholdet mellom reduksjonsanleggene blitt studert. For eksempel er det kjent at Hver Turing-grad er enten en sannhetstabellgrad eller er foreningen av uendelig mange sannhetstabellgrader.

Reduksjonsverdier svakere Enn Turing-reduksjonsverdier (det vil si reduksjonsverdier som impliseres Av Turing-reduksjonsverdier) har også blitt studert. De mest kjente er aritmetisk reduktivitet og hyperaritmetisk reduktivitet. Disse reduksjonene er nært knyttet til definerbarhet over standardmodellen av aritmetikk.

Rice teorem og aritmetisk hierarkirediger

rice viste at for hver nontrivial klasse C (som inneholder noen, men ikke alle r.e. sett) indekssettet E = {e: eth r.e. sett Vi er I C} har egenskapen at enten stoppproblemet eller komplementet er mange-en reduserbar Til E, det vil si, kan kartlegges ved hjelp av en mange-en reduksjon Til E (se Ris teorem for mer detalj). Men mange av disse indekssettene er enda mer kompliserte enn stoppproblemet. Denne typen sett kan klassifiseres ved hjelp av aritmetisk hierarki. For eksempel er indekssettet FIN av klasse av alle endelige sett på nivå Σ2, indekssettet REC av klassen av alle rekursive sett på nivå@3, indekssettet COFIN av alle cofinite sett er også på nivå@3 og indekssettet COMP av klassen Av Alle Turing-komplette sett Σ4. Disse hierarkinivåene er definert induktivt, Σ+1 inneholder bare alle sett som er rekursivt nummererbare i forhold til Σ; Σ1 inneholder rekursivt nummererbare sett. Indekssettene gitt her er til og med komplette for deres nivåer, det vil si at alle settene i disse nivåene kan være mange-en redusert til de oppgitte indekssettene.

Omvendt matematikk [rediger / rediger kilde]

programmet for omvendt matematikk spør hvilke seteksistensaksiomer som er nødvendige for å bevise bestemte teoremer i matematikk i delsystemer av annenordens aritmetikk. Denne studien ble initiert Av Harvey Friedman og ble studert i detalj Av Stephen Simpson og andre; Simpson (1999) gir en detaljert diskusjon av programmet. De aktuelle seteksistensaksiomene svarer uformelt til aksiomer som sier at kraften til de naturlige tallene er stengt under ulike reduksjonsbegreper. Den svakeste aksiom studert i omvendt matematikk er rekursiv forståelse, som sier at powerset av naturals er stengt Under Turing reducibility.

Tallrediger

en nummerering er en opplisting av funksjoner; den har to parametere, e og x og gir ut verdien av e-th-funksjonen i nummereringen på inngangen x. Numberings kan være delvis rekursive selv om noen av medlemmene er totalt rekursive, det vil si beregningsbare funksjoner. Avtakbare tall er de som alle andre kan oversettes til. En Friedberg-nummerering (oppkalt etter oppdageren) er en en-en-nummerering av alle partielle rekursive funksjoner; det er nødvendigvis ikke en tillatelig nummerering. Senere forskning behandlet ogsa numberings av andre klasser som klasser av rekursivt enumerable sett. Goncharov oppdaget for eksempel en klasse av rekursivt enumerable sett hvor tallene faller inn i nøyaktig to klasser med hensyn til rekursive isomorfismer.

prioritetsmetodendit

for ytterligere forklaring, se avsnittet Postens problem og prioritetsmetoden i Artikkelen Turing degree.

Posts problem ble løst med en metode som kalles prioritetsmetoden; et bevis som bruker denne metoden kalles et prioritetsargument. Denne metoden brukes primært til å konstruere rekursivt nummererbare sett med bestemte egenskaper. For å bruke denne metoden brytes de ønskede egenskapene til settet som skal bygges opp i en uendelig liste over mål, kjent som krav, slik at det tilfredsstiller alle kravene vil føre til at settet konstruert har de ønskede egenskapene. Hvert krav er tildelt et naturlig tall som representerer prioriteten til kravet; så 0 er tildelt den viktigste prioriteten, 1 til den nest viktigste, og så videre. Settet blir deretter konstruert i etapper, hvert trinn forsøker å tilfredsstille en av flere av kravene ved enten å legge til tall til settet eller forby tall fra settet slik at det endelige settet vil tilfredsstille kravet. Det kan hende at å tilfredsstille et krav vil føre til at en annen blir utilfreds; prioritetsordren brukes til å bestemme hva du skal gjøre i en slik hendelse.

Prioriterte argumenter har blitt benyttet for å løse mange problemer i rekursjonsteori, og har blitt klassifisert i et hierarki basert på deres kompleksitet (Soare 1987). Fordi komplekse prioriterte argumenter kan være tekniske og vanskelige å følge, har det tradisjonelt vært ansett som ønskelig å bevise resultater uten prioriterte argumenter, eller for å se om resultater bevist med prioriterte argumenter også kan bevises uten dem. For eksempel publiserte Kummer et papir om et bevis på Eksistensen Av Friedberg-nummereringer uten å bruke prioritetsmetoden.

gitteret av rekursivt enumerable setsEdit

Når Post definerte begrepet et enkelt sett som et r. e.sett med et uendelig komplement som ikke inneholder noen uendelig r.e. set, begynte han å studere strukturen av rekursivt enumerable settene under inkludering. Denne gitteret ble en godt studert struktur. Rekursive sett kan defineres i denne strukturen av det grunnleggende resultatet at et sett er rekursivt hvis og bare hvis settet og dets komplement er begge rekursivt nummererbare. Uendelige re-sett har alltid uendelige rekursive undergrupper; men på den annen side eksisterer enkle sett, men har ikke et coinfinite rekursivt supersett. Post (1944) introduserte allerede hypersimple og hyperhypersimple sett; senere ble maksimale sett konstruert som er r. e.sett slik at hver r.e. superset er enten en endelig variant av det gitte maksimale settet eller er co-endelig. Posts opprinnelige motivasjon i studiet av dette gitteret var å finne en strukturell oppfatning slik at hvert sett som tilfredsstiller denne egenskapen ikke er i Turing-graden av de rekursive settene eller I Turing-graden av stoppproblemet. Post fant ikke en slik eiendom, og løsningen på hans problem brukte prioriterte metoder i stedet; Harrington og Soare (1991) fant til slutt en slik eiendom.

Automorphism problemsEdit

Et annet viktig spørsmål er eksistensen av automorphisms i rekursjonsteoretiske strukturer. En av disse strukturene er at en av rekursivt enumerable sett under inkludering modulo endelig forskjell; i denne strukturen er a under B hvis og bare hvis settforskjellen B-A er endelig. Maksimale sett (som definert i forrige avsnitt) har egenskapen at de ikke kan være automorfe til ikke-maksimale sett, det vil si hvis det er en automorfisme av de rekursive nummererbare settene under strukturen som nettopp er nevnt, blir hvert maksimalt sett kartlagt til et annet maksimalt sett. Soare (1974) viste at også converse holder, det vil si at hver to maksimale sett er automorfe. Så de maksimale settene danner en bane, det vil si at hver automorfisme bevarer maksimalitet og noen to maksimale sett forvandles til hverandre av noen automorfisme. Harrington ga et ytterligere eksempel på en automorphic eiendom: det av de kreative settene, settene som er mange-en tilsvarer halting problem.

Foruten gitteret av rekursivt nummererbare sett, studeres automorfismer også for strukturen Av Turing-grader av alle sett, så vel som for strukturen Av Turing-grader av r.e. sett. I begge tilfeller, Cooper hevder å ha konstruert trivielle automorphisms som kartlegge noen grader til andre grader; denne konstruksjonen har imidlertid ikke blitt verifisert ,og noen kolleger mener at konstruksjonen inneholder feil, og at spørsmålet om Det er En ubehagelig automorfisme Av Turing-grader, fortsatt er et av de viktigste uløste spørsmålene på dette området (Slaman and Woodin 1986, Ambos-Spies and Fejer 2006).

Kolmogorov kompleksitetrediger

Feltet Kolmogorov kompleksitet og algoritmisk tilfeldighet ble utviklet i løpet Av 1960-og 1970 – tallet Av Chaitin, Kolmogorov, Levin, Martin-Lö Og Solomonoff (navnene er gitt her i alfabetisk rekkefølge; mye av forskningen var uavhengig, og enheten i begrepet tilfeldighet ble ikke forstått på den tiden). Hovedideen er å vurdere en universell Turing maskin U Og å måle kompleksiteten til et tall (eller streng) x som lengden på den korteste inngangen p slik At U (p) utganger x. Denne tilnærmingen revolusjonerte tidligere måter å bestemme når en uendelig sekvens (ekvivalent, karakteristisk funksjon av en delmengde av de naturlige tallene) er tilfeldig eller ikke ved å påkalle et begrep om tilfeldighet for endelige objekter. Kolmogorov kompleksitet ble ikke bare et emne for selvstudium, men er også brukt til andre fag som et verktøy for å skaffe bevis.Det er fortsatt mange åpne problemer på dette området. Av den grunn ble en nylig forskningskonferanse på dette området holdt i januar 2007, Og En liste over åpne problemer opprettholdes Av Joseph Miller og Andre Nies.

Frekvensberegningrediger

denne grenen av rekursjonsteori analyserte følgende spørsmål: for faste m og n med 0 < m < n, for hvilke funksjoner a er Det mulig å beregne for forskjellige n-innganger x1, x2,…, xn en tuple av n tall y1, y2,…, yn slik at minst m av ligningene A (xk) = yk er sanne. Slike sett er kjent som (m, n)-rekursive sett. Det første hovedresultatet i Denne grenen Av Rekursjonsteorien er Trakhtenbrot ‘ s resultat at et sett kan beregnes hvis det er (m, n)-rekursivt for noen m, n med 2m > n. På Den annen side er jockuschs semirecursive sett (som allerede var kjent uformelt før Jockusch introduserte dem 1968) eksempler på et sett som er (m, n)-rekursiv hvis og bare hvis 2m < n + 1. Det er utallige mange av disse settene og også noen rekursivt nummererbare, men ikke-computable sett av denne typen. Senere etablerte Degtev et hierarki av rekursivt nummererbare sett som er (1, n + 1)-rekursiv, men ikke (1, n)-rekursiv. Etter en lang fase av forskning av russiske forskere ble dette emnet repopularisert i vesten Av Beigels avhandling om avgrensede spørringer, som koblet frekvensberegning til de ovennevnte avgrensede reduksjonsverdiene og andre relaterte forestillinger. En av de store resultatene var Kummer Kardinalitet Teori som sier at et sett A er computable hvis og bare hvis det er en n slik at noen algoritme nummererer for hver tuple av n forskjellige tall opp til n mange mulige valg av kardinalitet av dette settet av n tall krysses Med A; disse valgene må inneholde den sanne kardinaliteten, men utelate minst en falsk.

Induktiv slutningrediger

dette er den rekursjonsteoretiske grenen av læringsteori. Den er basert På E. Mark Golds modell for læring i grensen fra 1967 og har utviklet seg siden da flere og flere modeller for læring. Det generelle scenariet er følgende: Gitt en klasse S av beregningsbare funksjoner, er det en elev (det vil si rekursiv funksjonell) som utganger for enhver inngang av skjemaet(f (0), f(1),…, f (n)) en hypotese. En elev m lærer en funksjon f hvis nesten alle hypoteser er den samme indeksen e av f med hensyn til en tidligere avtalt akseptabel nummerering av alle beregningsbare funksjoner; M lærer s hvis M lærer hver f I S. Grunnleggende resultater er at alle rekursivt nummererbare klasser av funksjoner kan læres mens klassen REC av alle beregningsbare funksjoner ikke kan læres. Mange relaterte modeller har blitt vurdert, og også læring av klasser av rekursivt nummererbare sett fra positive data er et emne studert Fra Golds banebrytende papir i 1967 og fremover.

Generaliseringer Av turing computabilityEdit

Rekursjonsteori omfatter studiet av generaliserte forestillinger om dette feltet som aritmetisk reduksjonsevne, hyperaritmetisk reduksjonsevne og α-rekursjonsteori, som beskrevet Av Sacks (1990). Disse generaliserte forestillingene inkluderer reduksjoner som Ikke kan utføres Av Turing-maskiner, men som likevel er naturlige generaliseringer av Turing-reduksjonsevne. Disse studiene inkluderer tilnærminger for å undersøke det analytiske hierarkiet som avviker fra det aritmetiske hierarkiet ved å tillate kvantifisering over sett med naturlige tall i tillegg til kvantifisering over individuelle tall. Disse områdene er knyttet til teorier om brønnorderinger og trær; for eksempel er settet av alle indekser av rekursive (ikke-binære) trær uten uendelige grener fullført for nivå Π 1 1 {\displaystyle \ Pi _{1}^{1}}

det analytiske hierarkiet. Både Turing reducibility og hyperaritmetical reducibility er viktig innen effektiv beskrivende mengdelære. Den enda mer generelle oppfatningen av grader av konstruktivitet studeres i settteori.

Kontinuerlig beregningsteorirediger

Beregningsteori for digital beregning er godt utviklet. Computability theory er mindre godt utviklet for analog beregning som forekommer i analoge datamaskiner, analog signalbehandling, analog elektronikk, nevrale nettverk og kontinuerlig tidskontrollteori, modellert av differensialligninger Og kontinuerlige dynamiske systemer (Orponen 1997; Moore 1996).