Teorie výpočetnosti

počínaje teorií rekurzivních množin a funkcí popsaných výše se oblast teorie rekurze rozrostla o studium mnoha úzce souvisejících témat. Tyto nejsou nezávislé oblasti výzkumu: každá z těchto oblastí čerpá nápady a výsledky od ostatních, a většina rekurze teoretici jsou obeznámeni s většinou z nich.

relativní vypočítatelnost a stupeň Turingueditovat

Rekurze teorie v matematické logice se tradičně zaměřuje na relativní vyčíslitelnost, zobecnění Turingových vyčíslitelnosti definována pomocí oracle Turingovy stroje, zavedla Turing (1939). Stroj oracle Turing je hypotetické zařízení, které je kromě provádění akcí běžného Turingova stroje schopno klást otázky věštci, což je zvláštní sada přirozených čísel. Stroj oracle může klást otázky pouze ve tvaru ” je n v sadě oracle?”. Každá otázka bude okamžitě zodpovězena správně, i když sada oracle není vypočítatelná. Stroj oracle s nekomputovatelným oracle tak bude schopen vypočítat sady, které Turingův stroj bez oracle nemůže.

Neformálně množina přirozených čísel je Turinga zredukovat na sadu B, pokud je oracle stroj, který správně řekne, zda jsou čísla v při spuštění s B jako oracle nastavit (v tomto případě, nastavit je také řekl, aby byl (relativně) vypočitatelný z B a v rekurzivní B). Pokud nastavení je Turinga zredukovat na sadu B a B je Turing redukovatelné se pak nastaví se říká, že mají stejné Turing stupňů (také se nazývá stupeň nerozhodnutelnosti). Turingův stupeň množiny poskytuje přesné měřítko toho, jak je množina nespočitatelná.

přírodní příklady množin, které nejsou vyčíslitelné, včetně mnoha různých sad, které kódují variant problém zastavení, mají dvě společné vlastnosti:

1. jsou rekurzivně spočetné, a
2. Každý může být přeložen do jiného přes mnoho-jedna redukce. To znamená, že vzhledem k takovým množinám a A B existuje celková vypočítatelná funkce f taková, že A = {x : f(x) ∈ b}. O těchto množinách se říká, že jsou mnoho-jeden ekvivalent (nebo M-ekvivalent).

Mnoho-jeden snížení jsou “silnější” než Turingovy redukce: je-li nastavení je mnoho-jeden redukovat na množinu B, pak A je Turing redukovatelné na B, ale hovořit nemusí vždy držet. I když přírodní příklady noncomputable sady jsou mnoho-jeden ekvivalent, je možné sestrojit rekurzivně spočetné množiny a a B takové, že je Turing redukovatelné na B, ale ne mnoho-jeden redukovatelné na B. To může být prokázáno, že každý rekurzivně spočetné množiny je mnoho-jeden redukovat na problém zastavení, tedy problém zastavení je nejsložitější rekurzivně spočetné nastavit s ohledem na mnoho-jeden redukovatelnost a s ohledem na Turing redukovatelnost. Post (1944) se zeptal, zda každý rekurzivně spočetné množiny je buď vypočitatelný nebo ekvivalentní Turingův na problém zastavení, to znamená, zda není rekurzivně spočetný soubor s Turing střední stupeň mezi těmito dvěma.

Jako průběžné výsledky, Příspěvek definovanými přírodní typy rekurzivně spočetné množiny jako jednoduché, hypersimple a hyperhypersimple sady. Příspěvek ukázal, že tyto sady jsou přísně mezi vyčíslitelné soupravy a problém zastavení s ohledem na mnoho-jeden redukovatelnost. Post také ukázal, že některé z nich jsou přísně přechodné podle jiných pojmů redukovatelnosti silnějších než Turingova redukovatelnost. Ale Post opustil otevřete hlavní problém existence rekurzivně spočetné množiny přechodných Turing stupně; tento problém se stal známý jako Post je problém. Po deseti letech, Kleene a Post ukázala v roce 1954, že tam jsou intermediate Turing stupňů mezi ty vyčíslitelné soupravy a problém zastavení, ale nepodařilo se jim ukázat, že některý z těchto stupňů obsahuje rekurzivně spočetné nastavit. Velmi brzy poté Friedberg a Muchnik nezávisle vyřešili Postův problém stanovením existence rekurzivně vyčíslitelných množin středního stupně. Tento průlomový výsledek otevřel širokou studii Turingových stupňů rekurzivně vyčíslitelných množin, které se ukázaly jako velmi komplikované a netriviální struktury.

Tam jsou uncountably mnoho sad, které nejsou rekurzivně spočetné, a vyšetřování Turing stupňů všech sad je jako centrální v teorie rekurze jako vyšetřování rekurzivně spočetné Turing stupňů. Mnoho stupňů se speciálními vlastnostmi byly postaveny: hyperimunní-free stupňů, kde každá funkce vyčíslitelné relativní do té míry, je majorized (unrelativized) vyčíslitelné funkce; vysoký stupeň relativní, na které se dá vypočítat funkci f, která je dominantou každé vyčíslitelné funkce g v tom smyslu, že existuje konstanta c v závislosti na g taková, že g(x) < f(x) pro všechna x > c; náhodné stupňů obsahující algoritmicky náhodná; 1-generic stupňů 1-generické množiny; a stupňů níže, problém zastavení limit rekurzivní množiny.

studium libovolných (ne nutně rekurzivně vyčíslitelných) Turingových stupňů zahrnuje studium Turingova skoku. Vzhledem k tomu, sadu, Turing skok z je množina přirozených čísel, kódování, řešení na problém zastavení pro oracle Turingovy stroje běží s oracle A. Turing skočit na jakýkoliv soubor je vždy vyšší Turing míře než původní soubor, a věta Friedburg ukazuje, že každý soubor, který vypočítá problém Zastavení může být získána jako Turing skok na další soubor. Post věta vytváří blízký vztah mezi Turing skok provoz a aritmetická hierarchie, která je klasifikace určité podmnožiny přirozených čísel na základě jejich definovatelnost v aritmetice.

nedávný výzkum Turingových stupňů se zaměřil na celkovou strukturu množiny Turingových stupňů a množiny Turingových stupňů obsahujících rekurzivně vyčíslitelné množiny. Hluboká věta Shore a Slaman (1999) uvádí, že funkce mapující stupeň x na stupeň jeho Turingova skoku je definovatelná v částečném pořadí Turingových stupňů. Nedávný průzkum Ambos-Spies and Fejer (2006) poskytuje přehled tohoto výzkumu a jeho historického vývoje.

Ostatní reducibilityeditovat

probíhající oblast výzkumu teorie rekurze studuje vztahy redukovatelnosti jiné než Turingova redukovatelnost. Post (1944) zavedl několik silných redukovatelností, tak pojmenovaných, protože znamenají redukovatelnost tabulky pravdy. Turingův stroj implementující silnou redukovatelnost vypočítá celkovou funkci bez ohledu na to, s jakou oracle je prezentován. Slabé reducibility jsou ty, kde proces redukce nemusí skončit pro všechny věštce; Turing reducibility je jedním z příkladů.

mezi silné reducibility patří:

Jeden-jeden redukovatelnost je jeden-one reducible (nebo 1-redukovat) na B, pokud tam je celkem vypočitatelný injektivní funkce f taková, že každé n je v tehdy a jen tehdy pokud f(n) je v B. Mnoho-jeden redukovatelnost je To v podstatě jedno-jeden redukovatelnost bez omezení, že f je injektivní. A je mnoho-one reducible (nebo m-redukovat) na B, pokud existuje totální vyčíslitelné funkce f taková, že každé n je v tehdy a jen tehdy pokud f(n) je v B. Pravda-tabulka redukovatelnost je pravda-tabulka redukovatelné na B, pokud je Turing redukovatelné na B pomocí oracle Turingův stroj, který vypočítá celkovou funkci bez ohledu na to, oracle, to je dáno. Kvůli kompaktnosti Cantor prostor, toto je ekvivalent k říkat, že snížení představuje jeden seznam otázek (v závislosti pouze na vstupu) do oracle současně, a pak když jsem viděl jejich odpovědi je schopen produkovat výstup, aniž ptát doplňující otázky bez ohledu na oracle je odpověď na původní dotazy. Bylo také studováno mnoho variant redukovatelnosti tabulky pravdy.

další redukce (pozitivní, disjunktivní, konjunktivní, lineární a jejich slabé a ohraničené verze) jsou diskutovány v článku redukce (teorie rekurze).

hlavní výzkum na silné reducibilities bylo porovnat jejich teorie, a to jak pro třídu všech rekurzivně spočetné množiny, stejně jako pro třídu všech podmnožin přirozených čísel. Dále byly studovány vztahy mezi reducibilitami. Například je známo, že každý Turingův stupeň je buď stupněm tabulky pravdy, nebo je spojením nekonečně mnoha stupňů tabulky pravdy.

byly také studovány Redukovatelnosti slabší než Turingova redukovatelnost (tj. redukovatelnost, která je implikována turingovou redukovatelností). Nejznámější jsou aritmetická redukovatelnost a hyperaritmetická redukovatelnost. Tyto redukovatelnosti jsou úzce spojeny s definovatelností oproti standardnímu modelu aritmetiky.

riceovy věty a aritmetický hierarchyEdit

Rýže ukázala, že pro každý netriviální třída C (který obsahuje některé, ale ne všechny r.e. sady) index nastavit E = {e: eth r.e. set Jsme je v C} má tu vlastnost, že buď problém zastavení nebo jeho doplnění, je mnoho-jeden redukovatelné na E, to znamená, že mohou být mapovány pomocí mnoho-jeden snížení E (viz riceovy věty pro více detailů). Ale mnoho z těchto indexových sad je ještě komplikovanější než problém zastavení. Tyto typy množin lze klasifikovat pomocí aritmetické hierarchie. Například index nastavit PLOUTEV třídě všech konečných množin je na úrovni Σ2, index set REC třídě všech rekurzivní množiny je na úrovni Σ3, index nastavit COFIN všech cofinite sady je také na úrovni, Σ3 a index set COMP třídě všech Turing-kompletní sady Σ4. Tyto hierarchické úrovně jsou definovány indukčně, Σn+1 obsahuje jen všechny množiny, které jsou rekurzivně vyčíslitelné vzhledem k Σn; Σ1 obsahuje rekurzivně vyčíslitelné množiny. Index sady jsou zde uvedeny i kompletní pro jejich úrovně, to znamená, že všechny soubory v těchto úrovních může být mnoho-jeden snížena na daný index sady.

Reverzní mathematicsEdit

program zpětného matematiky, která požaduje, set-existence axiomy jsou nezbytné prokázat konkrétní věty z matematiky na subsystémy druhého řádu aritmetiky. Tato studie byla zahájena Harvey Friedman a byla podrobně studována Stephenem Simpsonem a dalšími; Simpson (1999) poskytuje podrobnou diskusi o programu. Set-existence axiomy v otázce odpovídají neformálně axiomů říká, že powerset z přirozených čísel je uzavřená pod různými redukovatelnost pojmy. Nejslabší takový axiom studoval v opačném matematiky je rekurzivní porozumění, v němž se uvádí, že powerset domorodců je uzavřen pod Turing redukovatelnost.

NumberingsEdit

číslování je výčet funkcí; má dva parametry, e a x a výstupy hodnota e-tého funkce v číslování na vstup x. Číslování může být částečně rekurzivní, i když některé jeho členy jsou celkem rekurzivní, tj. Přípustná čísla jsou čísla, do kterých lze přeložit všechny ostatní. A Friedberg číslování (pojmenované po svém objeviteli)-číslování všech částečná rekurzivní funkce; je to nutně není přípustné číslování. Pozdější výzkum se zabýval také číslováním dalších tříd, jako jsou třídy rekurzivně vyčíslitelných množin. Goncharov objevil například třídu rekurzivně spočetné množiny, pro které číslování spadají přesně do dvou tříd s ohledem na rekurzivní izomorsmy.

prioritní metodaeditovat

další vysvětlení naleznete v části problém příspěvku a prioritní metoda v článku Turingův stupeň.

Postův problém byl vyřešen metodou zvanou prioritní metoda; důkaz používající tuto metodu se nazývá prioritní argument. Tato metoda se primárně používá pro konstrukci rekurzivně vyčíslitelných množin se specifickými vlastnostmi. Pro použití této metody jsou požadované vlastnosti sestavené sady rozděleny do nekonečného seznamu cílů, známých jako požadavky, takže splnění všech požadavků způsobí, že konstruovaná sada bude mít požadované vlastnosti. Každému požadavku je přiřazeno přirozené číslo představující priorita požadavku, takže 0 je přiřazena nejvyšší priorita, 1-druhý nejdůležitější, a tak dále. Sada je pak postavena v několika fázích, každá fáze se snaží uspokojit více požadavků buď přidání čísel do množiny nebo zákaz čísla z množiny, tak, že konečný soubor bude splňovat požadavek. Může se stát, že splnění jednoho požadavku způsobí nespokojenost druhého; prioritní objednávka se používá k rozhodnutí, co dělat v takové události.

prioritní argumenty byly použity k řešení mnoha problémů v teorii rekurze a byly klasifikovány do hierarchie na základě jejich složitosti (Soare 1987). Protože komplex prioritou argumenty mohou být technické a obtížné sledovat, to je tradičně považována za žádoucí, aby prokázat výsledky, aniž by prioritní argumenty, nebo zjistit, zda výsledky prokázaly, s prioritou argumenty mohou být také dokázal bez nich. Kummer například publikoval článek o důkazu o existenci Friedbergových čísel bez použití prioritní metody.

mřížky rekurzivně spočetné setsEdit

Když Post definován pojem jednoduché nastavit jako r.e. sada s nekonečnou doplňují neobsahující žádné nekonečné r.e. set, začal studovat strukturu rekurzivně vyčíslitelných množin pod zahrnutím. Tato mřížka se stala dobře studovanou strukturou. Rekurzivní množiny mohou být v této struktuře definovány základním výsledkem, že množina je rekurzivní pouze tehdy, jsou-li množina i její doplněk rekurzivně vyčísleny. Nekonečné r. e. množiny mají vždy nekonečné rekurzivní podmnožiny; ale na druhé straně existují jednoduché množiny, ale nemají coinfinite rekurzivní nadmnožinu. Po (1944) byly zavedeny již hypersimple a hyperhypersimple množiny, později byly konstruovány maximální množiny, které jsou r. e. množiny tak, že každý r.e. superset je buď konečná varianta vzhledem k maximální sadu nebo je co-konečný. Příspěvek je původní motivace ve studii této mřížky bylo najít strukturální představa taková, že každá množina, která splňuje tuto vlastnost, není ani v Turing stupeň rekurzivní množiny ani v Turing stupeň problém zastavení. Post nenašel takovou vlastnost a řešení jeho problému místo toho použilo prioritní metody; Harrington a Soare (1991) nakonec našli takovou vlastnost.

Automorfizmu problemsEdit

Další důležitou otázkou je existence automorfizmy v rekurzi-teoretických konstrukcí. Jedna z těchto konstrukcí je, že jeden z rekurzivně spočetné množiny podle zařazení modulo konečných diferencí; v této struktuře, je nižší než B tehdy a jen tehdy, pokud rozdíl B − A je konečný. Maximální sad (jak je definováno v předchozím odstavci) mají tu vlastnost, že je nelze automorphic non-nastaví maximální, to znamená, že pokud je automorfizmu z rekurzivní spočetné množiny podle struktury se právě zmínil, potom každé maximální stanovené je mapován na jiný maximální nastavení. Soare (1974) ukázal, že také converse drží, to znamená, že každé dvě maximální sady jsou automorfní. Takže maximální soupravy tvoří oběžné dráhy, to znamená, že každý automorfizmu zachovává maximality a jakýmikoli dvěma maximální sady jsou transformovány do sebe nějakým automorfizmu. Harrington dal další příklad automorfní vlastnosti: to tvůrčích množin, množin, kterých je mnoho-jedna ekvivalentní problému zastavení.

Kromě mřížky rekurzivně spočetné množiny, automorfizmy jsou také studoval strukturu Turing stupňů ze všech sad, stejně jako pro struktury Turing stupňů r.e. nastaví. V obou případech, Cooper tvrdí, že vytvořil netriviální automorfismy, které mapují některé stupně do jiných stupňů; tato stavba má, nicméně, nebyla ověřena a někteří kolegové se domnívají, že stavba obsahuje chyby, a že otázka, zda existuje netriviální automorfizmu Turingův stupňů je stále jedním z hlavních nevyřešených otázek v této oblasti (Slaman a Woodin 1986, Ambos-Špioni a Fejer 2006).

komplexnost Kolmogoroveditovat

oblasti Kolmogorovy složitosti a algoritmické náhodnosti byl vyvinut během 1960 a 1970, Chaitin, Kolmogorovovův, Levin, Martin-Löf a Solomonoff (jména jsou zde uvedena v abecedním pořadí; mnohem výzkumu bylo nezávislých, a jednota pojem náhodnost není zřejmé, v té době). Hlavní myšlenkou je zvážit univerzální Turingův stroj U a měřit složitost čísla (nebo řetězce) x jako délku nejkratšího vstupu p tak, že u (p) výstupy x. Tento přístup revoluci dříve způsobů, jak určit, kdy nekonečnou posloupnost (ekvivalentně, charakteristická funkce podmnožiny přirozených čísel) je náhodná nebo ne vyvoláním pojem náhodnosti na konečných objektů. Kolmogorov složitost se stal nejen předmětem nezávislého studia, ale je také aplikován na jiné předměty jako nástroj pro získání důkazů.V této oblasti je stále mnoho otevřených problémů. Z tohoto důvodu se v lednu 2007 konala nedávná výzkumná konference v této oblasti a seznam otevřených problémů vedou Joseph Miller a Andre Nies.

Frekvence computationEdit

Tato větev rekurze teorie analyzovány následující otázku: Pro pevné m a n, 0 < m < n, pro které funkce je možné vypočítat pro jakýkoliv jiný n vstupů x1, x2, …, xn n-tice n čísel y1,y2,…, yn tak, že alespoň m rovnic A(xk) = yk jsou pravdivé. Takové množiny jsou známé jako (m, n)-rekurzivní množiny. Prvním významným výsledkem v této větvi teorie rekurze je Trakhtenbrotův výsledek, že množina je vypočítatelná, pokud je (m, n)-rekurzivní pro některé m, n s 2m > n. Na druhou stranu, Jockusch je semirecursive sady (které již byly neformálně známé před Jockusch představil jim 1968) jsou příklady nastavit, která je (m, n)-rekurzivní tehdy a jen tehdy, pokud 2m < n + 1. Existuje nespočetně mnoho z těchto množin a také některé rekurzivně vyčíslitelné, ale nevypočítatelné množiny tohoto typu. Později, Degtev stanovena hierarchie rekurzivně spočetné množiny, které jsou (1, n + 1)-rekurzivní, ale není (1, n)-rekurzivní. Po dlouhé fázi výzkumu ruských vědců, toto téma se stal repopularized na západě Beigel práce na ohraničené dotazy, které souvisí frekvence výpočtu výše uvedených ohraničené reducibilities a další související pojmy. Jedním z hlavních výsledků bylo Kummer je Mohutnost Teorie, která říká, že soubor je vypočitatelný, pokud a pouze tehdy, pokud existuje n takové, že nějaký algoritmus vypočítává pro každý n-tice z n různých čísel po n, je mnoho možných voleb mohutnost této množiny n čísel protíná s; tyto volby musí obsahovat skutečnou kardinalitu, ale vynechat alespoň jednu falešnou.

induktivní inferenceEdit

Toto je rekurzivně-teoretická větev teorie učení. Je založen na modelu učení e. Marka Golda v limitu z roku 1967 a od té doby vyvinul stále více modelů učení. Obecný scénář je následující: Vzhledem k tomu, třídy S vyčíslitelné funkce, je žák (to znamená, že rekurzivní funkční), který vypíše pro každý vstupní formuláře (f(0),f(1),…, f (n)) hypotéza. Student M se učí funkce f, pokud téměř všechny hypotézy jsou stejné, index e f s ohledem na dříve dohodli na přijatelné číslování všech vyčíslitelných funkcí; M učí se S pokud M se učí každý f v S. Základní výsledky jsou, že všechny rekurzivně spočetné třídy funkcí, které jsou poznatelné, zatímco třída REC všech vyčíslitelných funkcí není poznatelné. Mnoho příbuzných modelů byly zváženy a také učení třídy rekurzivně spočetné množiny z pozitivních dat je téma, studoval od Zlata je průkopnickou knihu v roce 1967 a dále.

Zobecnění Turingových computabilityEdit

Rekurze teorie zahrnuje studium generalizované pojmy z této oblasti, jako je aritmetický redukovatelnost, hyperarithmetical redukovatelnost a α-teorie rekurze, jak bylo popsáno Pytle (1990). Tyto zobecněné pojmy patří reducibilities, které nemohou být spuštěn pomocí Turingova stroje, ale přesto jsou přirozené zobecnění Turingových redukovatelnost. Tyto studie zahrnují přístupy k vyšetřování analytické hierarchie, která se liší od aritmetické hierarchii tím, že umožňuje kvantifikaci přes množiny přirozených čísel kromě vyčíslení po jednotlivých čísel. Tyto oblasti jsou spojeny s teorií no-uspořádání rotorů a stromy, například množina všech indexů rekurzivní (nonbinary) stromy bez nekonečné větve je úplný pro úroveň Π 1 1 {\displaystyle \Pi _{1}^{1}}

analytické hierarchie. Turingova redukovatelnost i hyperaritmetická redukovatelnost jsou důležité v oblasti efektivní deskriptivní teorie množin. Ještě obecnější pojem stupňů konstruovatelnosti je studován v teorii množin.

teorie spojité výpočetníedit

teorie Výpočetnosti pro digitální výpočty je dobře rozvinutá. Teorie vyčíslitelnosti je méně vyvinut pro analogové výpočty, které se vyskytuje v analogových počítačích, analogové zpracování signálů, analogové elektroniky, neuronových sítí a kontinuální kontrolu teorie, modeluje tím, že diferenciální rovnice a spojité dynamické systémy (Orponen 1997; Moore, 1996).