Berekenbaarheidstheorie

beginnend met de hierboven beschreven theorie van recursieve verzamelingen en functies, is het gebied van de recursietheorie uitgegroeid tot de studie van veel nauw verwante onderwerpen. Dit zijn geen onafhankelijke onderzoeksgebieden: elk van deze gebieden trekt ideeën en resultaten uit de andere, en de meeste recursie theoretici zijn bekend met de meerderheid van hen.

relatieve berekenbaarheid en de Turing degreesEdit

Recursietheorie in de wiskundige logica is traditioneel gericht op relatieve rekenbaarheid, een generalisatie van Turing computability gedefinieerd met behulp van Oracle Turing machines, geïntroduceerd door Turing (1939). Een Oracle Turing machine is een hypothetisch apparaat dat, naast het uitvoeren van de acties van een reguliere Turing machine, in staat is om vragen te stellen aan een oracle, dat is een bepaalde verzameling van natuurlijke getallen. De Oracle machine mag alleen vragen stellen van het formulier “Is n in de Oracle set?”. Elke vraag wordt onmiddellijk correct beantwoord, zelfs als de Oracle-set niet berekenbaar is. Zo zal een Oracle machine met een niet-compatibel Oracle in staat zijn om sets te berekenen die een Turing machine zonder oracle niet kan.

informeel is een verzameling natuurlijke getallen a Turing reduceerbaar tot een verzameling B als er een Oracle-machine is die correct vertelt of getallen in A zijn wanneer ze worden uitgevoerd met B als de Oracle-verzameling (in dit geval wordt ook gezegd dat de verzameling A (relatief) berekenbaar is vanuit B en recursief in B). Als een verzameling a Turing reduceerbaar is tot een verzameling B en B Turing reduceerbaar is tot A, dan wordt gezegd dat de Verzamelingen dezelfde Turinggraad hebben (ook wel graad van onoplosbaarheid genoemd). De Turinggraad van een verzameling geeft een precieze maat van hoe onrekenbaar de verzameling is.

de natuurlijke voorbeelden van Verzamelingen die niet berekenbaar zijn, waaronder veel verschillende verzamelingen die varianten van het stoppen probleem coderen, hebben twee eigenschappen gemeen:

1. ze zijn recursief enumerabel, en
2. elk kan worden vertaald in een andere via een veel-een reductie. Dat wil zeggen, gegeven zulke verzamelingen A en B, is er een totaal berekenbare functie f zodanig dat A = {x: f (x) ∈ b}. Van deze verzamelingen wordt gezegd dat ze veel-één equivalent (of M-equivalent) zijn.

veel-één reducties zijn “sterker” dan Turing reducties: als een verzameling a Veel-één reduceerbaar is tot een verzameling B, dan is A Turing reduceerbaar tot B, maar het omgekeerde geldt niet altijd. Hoewel de natuurlijke voorbeelden van niet-bruikbare verzamelingen allemaal veel-één-equivalent zijn, is het mogelijk recursief sombare verzamelingen A en B zo te construeren dat A Turing reduceerbaar is tot B, maar niet veel-één reduceerbaar tot B. Het kan worden aangetoond dat elke recursief enumerable verzameling veel-één reduceerbaar is tot het stoppen probleem, en dus is het stoppen probleem de meest gecompliceerde recursief enumerable verzameling met betrekking tot veel-één reduceerbaarheid en met betrekking tot Turing reduceerbaarheid. Post (1944) vroeg of elke recursief enumerable verzameling ofwel berekenbaar is of Turing equivalent is aan het stoppen probleem, dat wil zeggen of er geen recursief enumerable verzameling is met een Turing graad tussen deze twee.

als tussenresultaten, Post gedefinieerde natuurlijke types van recursief enumereerbare sets zoals de eenvoudige, hypersimple en hyperhypersimple sets. Post toonde aan dat deze verzamelingen strikt tussen de berekenbare verzamelingen en het stoppen probleem liggen met betrekking tot veel-één reduceerbaarheid. Post toonde ook aan dat sommige van hen strikt intermediair zijn onder andere reduceerbaarheidsbegrippen sterker dan Turing reduceerbaarheid. Maar Post liet het belangrijkste probleem van het bestaan van recursief opsommbare sets van intermediaire Turing graad open; dit probleem werd bekend als Post ‘ s probleem. Na tien jaar lieten Kleene en Post in 1954 zien dat er tussenliggende Turinggraden zijn tussen die van de berekenbare verzamelingen en het stoppen probleem, maar ze slaagden er niet in aan te tonen dat een van deze Graden een recursief opsommbare verzameling bevat. Al snel daarna losten Friedberg en Muchnik het probleem van Post zelfstandig op door het bestaan van recursief op te sommen sets van intermediaire graad vast te stellen. Dit baanbrekende resultaat opende een brede studie van de Turinggraden van de recursief opsommbare verzamelingen die een zeer ingewikkelde en niet-triviale structuur bleken te bezitten.

er zijn oneindig veel verzamelingen die niet recursief kwantificeerbaar zijn, en het onderzoek van de Turinggraden van alle verzamelingen staat net zo centraal in de recursietheorie als het onderzoek van de recursief kwantificeerbare Turinggraden. Vele graden met speciale eigenschappen werden geconstrueerd: hyperimmune-vrije graden waar elke functie berekenbaar ten opzichte van die graad wordt majorized door een (unrelativized) berekenbare functie; hoge graden ten opzichte waarvan men een functie f kan berekenen die elke berekenbare functie g domineert in de zin dat er een constante C afhankelijk is van g zodanig dat g (x) < f (x) voor alle x > c; willekeurige graden die algoritmisch willekeurige verzamelingen bevatten; 1-generieke graden van 1-generieke verzamelingen; en de graden onder het probleem van limit-recursieve verzamelingen.

de studie van willekeurige (niet noodzakelijkerwijs recursief op te tellen) Turinggraden omvat de studie van de Turingsprong. Gegeven een verzameling A, is de Turingsprong van A een verzameling natuurlijke getallen die een oplossing coderen voor het probleem van het stoppen van Oracle Turing machines die draaien met oracle A. De Turingsprong van een verzameling is altijd van hogere Turing graad dan de oorspronkelijke verzameling, en een stelling van Friedburg laat zien dat elke verzameling die het stoppen probleem berekent kan worden verkregen als de Turingsprong van een andere verzameling. De stelling van Post legt een nauwe relatie vast tussen de turingsprong operatie en de rekenkundige hiërarchie, die een classificatie is van bepaalde deelverzamelingen van de natuurlijke getallen gebaseerd op hun definieerbaarheid in de rekenkunde.Veel recent onderzoek naar Turinggraden heeft zich gericht op de algemene structuur van de verzameling Turinggraden en de verzameling Turinggraden die recursief opsommbare verzamelingen bevatten. Een diepe stelling van Shore and Slaman (1999) stelt dat de functie die een graad x in kaart brengt tot de graad van zijn Turingsprong, definieerbaar is in de partiële orde van de Turinggraden. Een recent onderzoek door Ambos-Spies en Fejer (2006) geeft een overzicht van dit onderzoek en de historische ontwikkeling ervan.

andere reductiededit

een lopend onderzoeksgebied in de recursietheorie studies reducibility relations other than Turing reducibility. Post (1944) introduceerde een aantal sterke reducties, zo genoemd omdat ze de reduceerbaarheid van de waarheidstabel impliceren. Een Turing machine met een sterke reduceerbaarheid berekent een totale functie ongeacht met welk oracle het wordt gepresenteerd. Zwakke reducties zijn die waarbij een reductieproces niet voor alle orakels kan worden beëindigd; Turing reductiebaarheid is een voorbeeld.

de sterke reducties omvatten:

Eén-één reduceerbaarheid A is één-één reduceerbaar(of 1-reduceerbaar) tot B als er een totaal berekenbare injectieve functie f is, zodat elke n in a is dan en alleen als f (n) in B. Veel-één reduceerbaarheid dit is in wezen één-één reduceerbaarheid zonder de beperking dat f injectief is. A is veel-één reduceerbaar (of m-reduceerbaar) tot B als er een totaal berekenbare functie f zodanig is dat elke n in a is dan en slechts dan als f (n) in B. Waarheidstabel reduceerbaarheid A is waarheidstabel reduceerbaar tot B als A Turing reduceerbaar is tot B via een Oracle Turing machine die een totale functie berekent ongeacht het Oracle dat het gegeven is. Vanwege de compactheid van Cantor ruimte, Dit is gelijk aan te zeggen dat de reductie presenteert een enkele lijst van vragen (alleen afhankelijk van de input) om het oracle tegelijkertijd, en dan hebben gezien hun antwoorden is in staat om een output te produceren zonder het stellen van extra vragen, ongeacht het antwoord van het Oracle op de eerste query ‘ s. Vele varianten van waarheid-tabel reduceerbaarheid zijn ook bestudeerd.

verdere reducties (positief, disjunctief, conjunctief, lineair en hun zwakke en begrensde versies) worden besproken in het artikel reductie (recursietheorie).

het belangrijkste onderzoek naar sterke reducties was het vergelijken van hun theorieën, zowel voor de klasse van alle recursief sombare Verzamelingen als voor de klasse van alle deelverzamelingen van de natuurlijke getallen. Bovendien is de relatie tussen de reducties onderzocht. Het is bijvoorbeeld bekend dat elke Turing graad ofwel een waarheidstabel graad is, ofwel de Vereniging van oneindig veel waarheidstabel graden.

reducties die zwakker zijn dan Turing-reduceerbaarheid (dat wil zeggen reducties die worden geïmpliceerd door Turing-reduceerbaarheid) zijn ook onderzocht. De meest bekende zijn rekenkundige reduceerbaarheid en hyperaritmische reduceerbaarheid. Deze reducties zijn nauw verbonden met de definieerbaarheid in vergelijking met het standaard rekenkundig model.De stelling van Rice en de rekenkundige hiërarchiedit

Rice toonden aan dat Voor elke niet-triviale klasse C (die enkele maar niet alle R.e. – verzamelingen bevat) de indexverzameling E = {e: de eth r.e. verzameling We is in C} heeft de eigenschap dat ofwel het probleem van stoppen of zijn complement veel-één reduceerbaar is tot E, dat wil zeggen, kan in kaart worden gebracht met behulp van een veel-één reductie tot E (zie de stelling van Rice voor meer details). Maar veel van deze indexsets zijn nog ingewikkelder dan het stoppen probleem. Dit type verzamelingen kan worden geclassificeerd met behulp van de rekenkundige hiërarchie. Bijvoorbeeld, de index FIN van de klasse van alle eindige verzamelingen op het niveau Σ2, de index REC van de klasse van alle recursieve verzamelingen op het niveau Σ3, de index COFIN van alle cofinite sets is ook op het niveau Σ3 en de index COMP van de klasse van alle Turing-complete sets Σ4. Deze hiërarchieniveaus worden inductief gedefinieerd, Σn+1 bevat slechts Alle verzamelingen die recursief enumereerbaar zijn ten opzichte van Σn; Σ1 bevat de recursief enumereerbare verzamelingen. De hier gegeven index sets zijn zelfs compleet voor hun niveaus, dat wil zeggen, alle sets in deze niveaus kunnen vele zijn-een gereduceerd tot de gegeven index sets.

Reverse mathematicsEdit

het programma van reverse mathematics vraagt welke verzameling-existentieaxioma ‘ s nodig zijn om bepaalde stellingen van de wiskunde in subsystemen van de tweede-orde-rekenkunde te bewijzen. Deze studie werd geïnitieerd door Harvey Friedman en werd in detail bestudeerd door Stephen Simpson en anderen; Simpson (1999) geeft een gedetailleerde bespreking van het programma. De axioma ‘s in kwestie komen informeel overeen met axioma’ s die zeggen dat de machtsverzameling van de natuurlijke getallen gesloten is onder verschillende reduceerbaarheidsbegrippen. Het zwakste axioma dat in de omgekeerde wiskunde wordt bestudeerd, is recursief begrip, dat stelt dat de krachtset van de natuurkundigen gesloten is onder Turing-reduceerbaarheid.

NumberingsEdit

een nummering is een opsomming van functies; het heeft twee parameters, e en x en geeft de waarde van de e-th functie uit in de nummering op de invoer x. Numberings kunnen partieel-recursief zijn, hoewel sommige leden totaal recursief zijn, dat wil zeggen, berekenbare functies. Toegestane nummers zijn die waarin alle andere kunnen worden vertaald. Een Friedberg-nummering (vernoemd naar de ontdekker) is een één-één-nummering van alle partieel-recursieve functies; het is noodzakelijkerwijs Geen toelaatbare nummering. Later onderzoek behandelde ook nummering van andere klassen zoals klassen van recursief opsommbare verzamelingen. Goncharov ontdekte bijvoorbeeld een klasse van recursief sombare verzamelingen waarvoor de getallen in precies twee klassen vallen met betrekking tot recursieve isomorfismen.

de prioriteitsmethode edit

voor verdere uitleg, zie het hoofdstuk Post ‘ s probleem en de prioriteitsmethode in het artikel Turing degree.

Post ‘ s probleem werd opgelost met een methode genaamd de priority method; een proof met behulp van deze methode wordt een priority argument genoemd. Deze methode wordt voornamelijk gebruikt om recursief enumereerbare sets met specifieke eigenschappen te construeren. Om deze methode te gebruiken, worden de gewenste eigenschappen van de te construeren verzameling opgesplitst in een oneindige lijst van doelen, bekend als vereisten, zodat het voldoen aan alle vereisten ervoor zorgt dat de geconstrueerde verzameling de gewenste eigenschappen heeft. Elke eis wordt toegewezen aan een natuurlijk getal dat de prioriteit van de eis vertegenwoordigt; dus 0 wordt toegewezen aan de belangrijkste prioriteit, 1 Aan de tweede belangrijkste, enzovoort. De verzameling wordt vervolgens in fasen opgebouwd, waarbij elke fase probeert te voldoen aan een van de vereisten door getallen aan de verzameling toe te voegen of getallen uit de verzameling te verbieden, zodat de uiteindelijke verzameling aan de eis voldoet. Het kan gebeuren dat het voldoen aan een bepaalde eis een andere niet tevreden zal stellen; de prioriteitsvolgorde wordt gebruikt om te beslissen wat te doen in een dergelijk geval.

Prioriteitsargumenten zijn gebruikt om veel problemen in de recursietheorie op te lossen en zijn ingedeeld in een hiërarchie op basis van hun complexiteit (Soare 1987). Omdat complexe prioriteitsargumenten technisch en moeilijk te volgen kunnen zijn, werd het van oudsher wenselijk geacht om resultaten zonder prioriteitsargumenten te bewijzen, of om te zien of resultaten die met prioriteitsargumenten zijn bewezen ook zonder deze resultaten kunnen worden bewezen. Zo publiceerde Kummer een artikel over een bewijs voor het bestaan van Friedberg-nummers zonder gebruik te maken van de prioriteitsmethode.

het rooster van recursief enumereerbare setsEdit

toen Post de notie van een eenvoudige verzameling definieerde als een r. e. verzameling met een oneindige complement die geen oneindige r.e.bevat. set, begon hij de structuur van de recursief opsommbare verzamelingen onder inclusie te bestuderen. Dit rooster werd een goed bestudeerde structuur. Recursieve Verzamelingen kunnen in deze structuur worden gedefinieerd door het basisresultaat dat een verzameling recursief is dan en alleen als de verzameling en zijn complement beide recursief enumerable zijn. Oneindige r. e. verzamelingen hebben altijd oneindige recursieve deelverzamelingen; maar aan de andere kant bestaan eenvoudige verzamelingen, maar hebben geen Co-Infinite recursieve superset. Post (1944) introduceerde reeds hypersimple en hyperhypersimple verzamelingen; later werden maximale verzamelingen geconstrueerd die r.e. Verzamelingen zijn, zodanig dat elke r.e. superverzameling is ofwel een eindige variant van de gegeven maximale verzameling of is co-eindig. Post ‘ s oorspronkelijke motivatie bij de studie van dit rooster was om een structureel begrip te vinden dat elke verzameling die aan deze eigenschap voldoet, noch in de Turinggraad van de recursieve verzamelingen, noch in de Turinggraad van het stilleggingsprobleem ligt. Post vond een dergelijke eigenschap niet en de oplossing voor zijn probleem paste in plaats daarvan prioriteitsmethoden toe; Harrington and Soare (1991) vond uiteindelijk zo ‘ n eigenschap.

Automorfisme problemedit

een andere belangrijke vraag is het bestaan van automorfismen in recursie-theoretische structuren. Een van deze structuren is die van recursief sombare verzamelingen onder inclusie modulo eindig verschil; in deze structuur is A dan en slechts dan onder B als het verzameling verschil B − A eindig is. Maximale verzamelingen (zoals gedefinieerd in de vorige paragraaf) hebben de eigenschap dat ze niet automorfisch kunnen zijn naar niet-maximale verzamelingen, dat wil zeggen, als er een automorfisme is van de recursieve enumerable verzamelingen onder de zojuist genoemde structuur, dan wordt elke maximale verzameling toegewezen aan een andere maximale verzameling. Soare (1974) toonde aan dat ook het omgekeerde geldt, dat wil zeggen dat elke twee maximale verzamelingen automorf zijn. Dus de maximale verzamelingen vormen een baan, dat wil zeggen, elk automorfisme behoudt de maximaliteit en elke twee maximale Verzamelingen worden in elkaar getransformeerd door een of ander automorfisme. Harrington gaf een ander voorbeeld van een automorfe eigenschap: die van de creatieve Verzamelingen, de Verzamelingen die veel-één zijn, equivalent aan het stoppen probleem.

naast het rooster van recursief sombare Verzamelingen worden ook automorfismen bestudeerd voor de structuur van de Turinggraden van alle verzamelingen en voor de structuur van de Turinggraden van r.e. verzamelingen. In beide gevallen beweert Cooper niet-triviale automorfismen te hebben geconstrueerd die sommige graden naar andere graden in kaart brengen.; deze constructie is echter niet geverifieerd en sommige collega ‘ s geloven dat de constructie fouten bevat en dat de vraag of er een niet-triviale automorfisme van de Turinggraden is nog steeds een van de belangrijkste onopgeloste vragen op dit gebied (Slaman en Woodin 1986, Ambos-Spies en Fejer 2006).

Kolmogorov complexiteitedit

het gebied van Kolmogorov complexity and algorithmic randomness werd ontwikkeld in de jaren 1960 en 1970 door Chaitin, Kolmogorov, Levin, Martin-Löf en Solomonoff (de namen worden hier in alfabetische volgorde gegeven; veel van het onderzoek was onafhankelijk, en de eenheid van het concept van randomness werd op dat moment niet begrepen). Het belangrijkste idee is om een universele Turing machine U te beschouwen en de complexiteit van een getal (of string) x te meten als de lengte van de kortste input p zodanig dat U (p) x uitschakelt. Deze benadering bracht een revolutie teweeg in eerdere manieren om te bepalen wanneer een oneindige reeks (equivalently, karakteristieke functie van een deelverzameling van de natuurlijke getallen) willekeurig is of niet door een notie van willekeur voor eindige objecten aan te roepen. Kolmogorov complexiteit werd niet alleen een onderwerp van onafhankelijke studie, maar wordt ook toegepast op andere onderwerpen als een instrument voor het verkrijgen van bewijzen.Er zijn op dit gebied nog veel open problemen. Om die reden werd in januari 2007 een recente onderzoeksconferentie op dit gebied gehouden en wordt een lijst van open problemen bijgehouden door Joseph Miller en Andre Nies.

Frequentieberekening

deze tak van recursie theorie analyseerde de volgende vraag: voor vaste m en n met 0 < m < n, waarvoor functies A het mogelijk is om te berekenen voor verschillende n inputs x1, x2, …, xn een tupel van n nummers y1,y2,…, yn zodanig dat ten minste m van de vergelijkingen A(xk) = yk waar zijn. Dergelijke verzamelingen staan bekend als (M, n)-recursieve verzamelingen. Het eerste belangrijke resultaat in deze tak van de Recursietheorie is Trakhtenbrot ‘ s resultaat dat een verzameling berekenbaar is als ze (m, n)-recursief is voor sommige m, n met 2m > n. Aan de andere kant zijn de semirecursieve verzamelingen van Jockusch (die al informeel bekend waren voordat Jockusch ze in 1968 introduceerde) voorbeelden van een verzameling die (m, n)-recursief is dan en slechts dan als 2m < n + 1. Er zijn ontelbaar veel van deze sets en ook enkele recursief opsommbare maar niet-bruikbare sets van dit type. Later stelde Degtev een hiërarchie op van recursief enumereerbare verzamelingen die (1, n + 1)-recursief zijn maar niet (1, n)-recursief. Na een lange fase van onderzoek door Russische wetenschappers, werd dit onderwerp opnieuw gepopulariseerd in het westen door beigels thesis over begrensde queries, die frequentieberekening verbond met de hierboven genoemde beperkte reducties en andere gerelateerde noties. Een van de belangrijkste resultaten was Kummer ‘ s Kardinaliteitstheorie, die stelt dat een verzameling A berekenbaar is dan en alleen als er een n zodanig is dat sommige algoritmen voor elke tupel van n verschillende getallen tot n vele mogelijke keuzes van de kardinaliteit van deze verzameling van n getallen doorsneden met A opsommen; deze keuzes moeten de ware kardinaliteit bevatten, maar ten minste één valse weglaten.

inductieve inferentiedit

Dit is de recursie-theoretische tak van de leertheorie. Het is gebaseerd op E. Mark Gold ‘ s leermodel in the limit uit 1967 en heeft sindsdien meer en meer leermodellen ontwikkeld. Het algemene scenario is het volgende: gegeven een klasse S van berekenbare functies, is er een leerling (dat is, recursieve functionele) die uitgangen voor elke invoer van de vorm (f (0), f(1),…, f (n)) een hypothese. Een leerling M leert een functie f als bijna alle hypothesen dezelfde index e van f zijn met betrekking tot een eerder overeengekomen aanvaardbare nummering van alle berekenbare functies; M leert S als M leert elke f in S. De basisresultaten zijn dat alle recursief opsommbare klassen van functies leerbaar zijn, terwijl de klasse REC van alle berekenbare functies niet leerbaar is. Veel gerelateerde modellen zijn overwogen en ook het leren van klassen van recursief opsets van positieve gegevens is een onderwerp dat bestudeerd is vanaf Gold ‘ s baanbrekende paper in 1967.

generalisaties van Turing computabilityEdit

Recursietheorie omvat de studie van veralgemeende noties van dit gebied, zoals de rekenkundige reduceerbaarheid, hyperarithmetische reduceerbaarheid en α-recursietheorie, zoals beschreven door Sacks (1990). Deze veralgemeende noties omvatten reducties die niet kunnen worden uitgevoerd door Turing machines, maar zijn niettemin natuurlijke generalisaties van Turing reduceerbaarheid. Deze studies omvatten benaderingen om de analytische hiërarchie te onderzoeken die verschilt van de rekenkundige hiërarchie door kwantificering over sets van natuurlijke getallen toe te staan naast kwantificering over individuele getallen. Deze gebieden zijn gelinkt aan de theorieën van goedordingen en bomen; bijvoorbeeld de verzameling van alle indices van recursieve (niet-binaire) bomen zonder oneindige takken is compleet voor niveau Π 1 1 {\displaystyle \ Pi _{1}^{1}}

van de analytische hiërarchie. Zowel de Turing-reduceerbaarheid als de hyperaritmische reduceerbaarheid zijn belangrijk op het gebied van de effectieve beschrijvende verzamelingenleer. De nog algemenere notie van constructiegraden wordt bestudeerd in de verzamelingenleer.

Continuous computability theoryEdit

Computability theory for digital computation is goed ontwikkeld. Computability theory is minder goed ontwikkeld voor analoge berekening die voorkomt in analoge computers, analoge signaalverwerking, analoge elektronica, neurale netwerken en continue-tijd controle theorie, gemodelleerd door differentiaalvergelijkingen en continue dynamische systemen (Orponen 1997; Moore 1996).