Turingova redukce - Turing reduction

V teorii vyčíslitelnosti , je snížení Turing z rozhodovací problém na rozhodovací problém je Oracle stroj , který rozhoduje problém vzhledem k tomu, Oracle pro (Rogers 1967, Soare 1987). To lze chápat jako algoritmus , který by mohl být použit k řešení , kdyby měl k tomu k dispozici podprogram pro řešení B . Koncept lze analogicky aplikovat na funkční problémy . ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$

Pokud Turingova redukce od do existuje, pak každý algoritmus pro může být použit k vytvoření algoritmu pro , vložením algoritmu pro na každém místě, kde výpočetní stroj Oracle dotazuje Oracle . Protože však stroj Oracle může dotazovat Oracle několikrát, výsledný algoritmus může vyžadovat více času asymptoticky než algoritmus pro výpočet nebo počítač Oracle . Turingova redukce, při které věštecký stroj běží v polynomiálním čase, se nazývá Cookova redukce . ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$

První formální definice relativní vyčíslitelnosti, která se tehdy nazývala relativní redukovatelnost, dal Alan Turing v roce 1939, pokud jde o věštecké stroje . Později v letech 1943 a 1952 Stephen Kleene definoval ekvivalentní koncept z hlediska rekurzivních funkcí . V roce 1944 použil Emil Post pojem „Turingova redukovatelnost“.

Definice

Vzhledem k tomu , že máme dvě sady přirozených čísel, říkáme, že je Turing redukovatelný na a zapisuje ${\ displaystyle A, B \ subseteq \ mathbb {N}}$${\ displaystyle A}$${\ displaystyle B}$

${\ displaystyle A \ leq _ {T} B}$

v případě, že je Oracle stroj , který počítá charakteristickou funkci z A, při spuštění s Oracle B . V tomto případě také říkáme, že A je B- rekurzivní a B- vypočítatelné .

Pokud existuje stroj Oracle, který při spuštění s Oracle B počítá částečnou funkci s doménou A , pak se říká, že A je B - rekurzivně vyčíslitelné a B - vypočítatelně vyčíslitelné .

Říkáme je Turing ekvivalentní k a psát , pokud jsou oba i se třídy ekvivalence na Turing ekvivalentních množin jsou nazývány Turing stupňů . Turingův stupeň sady je zapsán . ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A \ equiv _ {T} B \,}$${\ displaystyle A \ leq _ {T} B}$${\ displaystyle B \ leq _ {T} A.}$${\ displaystyle X}$${\ displaystyle {\ textbf {deg}} (X)}$

Vzhledem k množině se množina nazývá Turing hard for if for all . Pokud navíc pak se nazývá Turing kompletní pro . ${\ displaystyle {\ mathcal {X}} \ subseteq {\ mathcal {P}} (\ mathbb {N})}$${\ displaystyle A \ subseteq \ mathbb {N}}$${\ displaystyle {\ mathcal {X}}}$${\ displaystyle X \ leq _ {T} A}$${\ displaystyle X \ v {\ mathcal {X}}}$${\ displaystyle A \ v {\ mathcal {X}}}$${\ displaystyle A}$${\ displaystyle {\ mathcal {X}}}$

Vztah Turingovy úplnosti k výpočetní univerzálnosti

Turingova úplnost, jak byla právě definována výše, odpovídá Turingově úplnosti ve smyslu výpočetní univerzality jen částečně . Konkrétně je Turingův stroj univerzálním Turingovým strojem, pokud je jeho problém se zastavením (tj. Množina vstupů, pro které se nakonec zastaví) mnoho . Nutnou, ale nedostatečnou podmínkou pro to, aby byl počítač výpočetně univerzální, je to, že problém se zastavením stroje je Turing-complete pro sadu rekurzivně vyčíslitelných sad. ${\ displaystyle {\ mathcal {X}}}$

Příklad

Dovolit množinu vstupních hodnot, pro které je Turingův stroj se index e zastávek. Pak jsou množiny a jsou Turingovy ekvivalenty (zde označuje efektivní párovací funkci). Znázornění redukce lze zkonstruovat na základě toho . Vzhledem k dvojici lze nový index sestrojit pomocí věty s _mn tak, že program kódovaný pomocí ignoruje jeho vstup a pouze simuluje výpočet stroje s indexem e na vstupu n . Zejména stroj s indexem se zastaví na každém vstupu nebo se zastaví na žádném vstupu. Platí tedy pro všechna e a n . Protože funkce i je vypočítatelná, ukazuje to . Zde uvedená redukce nejsou jen Turingovy redukce, ale redukce mnoho-jedna , popsaná níže. ${\ displaystyle W_ {e}}$${\ displaystyle A = \ {e \ mid e \ ve W_ {e} \}}$${\ displaystyle B = \ {(e, n) \ střední n \ ve W_ {e} \}}$${\ displaystyle (-, -)}$${\ displaystyle A \ leq _ {T} B}$${\ displaystyle e \ v A \ Leftrightarrow (e, e) \ v B}$${\ displaystyle (e, n)}$${\ displaystyle i (e, n)}$${\ displaystyle i (e, n)}$${\ displaystyle i (e, n)}$${\ displaystyle i (e, n) \ v A \ Leftrightarrow (e, n) \ v B}$${\ displaystyle B \ leq _ {T} A}$

Vlastnosti

• Každá sada je Turing ekvivalentní jejím doplňkům.
• Každá vypočítatelná sada je Turingova redukovatelná na všechny ostatní sady. Protože jakoukoli vypočítatelnou sadu lze vypočítat bez věštce, lze ji vypočítat strojem Oracle, který dané věštce ignoruje.
• Vztah je tranzitivní: tehdy a potom . Navíc platí pro každou množinu A , a tedy vztah je předobjednávkou (nejedná se o dílčí řád, protože a nemusí nutně znamenat ).${\ displaystyle \ leq _ {T}}$${\ displaystyle A \ leq _ {T} B}$${\ displaystyle B \ leq _ {T} C}$${\ displaystyle A \ leq _ {T} C}$${\ displaystyle A \ leq _ {T} A}$${\ displaystyle \ leq _ {T}}$${\ displaystyle A \ leq _ {T} B}$${\ displaystyle B \ leq _ {T} A}$${\ displaystyle A = B}$
• Existuje párů množin tak, že není Turing redukovat na B a B není Turing redukovatelná na A . Proto není celkové pořadí .${\ displaystyle (A, B)}$${\ displaystyle \ leq _ {T}}$
• Existují nekonečné klesající sekvence sad pod . Tento vztah tedy není opodstatněný .${\ displaystyle \ leq _ {T}}$
• Každá sada je Turingova redukovatelná na svůj vlastní Turingův skok , ale Turingův skok sady nikdy není Turingův redukovatelný na původní sadu.

Použití redukce

Vzhledem k tomu, že každá redukce ze sady na sadu musí určit, zda je jeden prvek pouze v konečně mnoha krocích, může provádět jen konečně mnoho dotazů na členství v sadě . Když je diskutováno množství informací o sadě použité k výpočtu jediného bitu , je to pomocí funkce use upřesněno. Formálně je použití redukce funkce, která odesílá každé přirozené číslo na největší přirozené číslo, jehož členství v sadě B bylo dotazováno redukcí při určování členství v . ${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle A}$

Silnější redukce

Existují dva běžné způsoby, jak dosáhnout redukcí silnějších než Turingova redukovatelnost. Prvním způsobem je omezit počet a způsob Oracle dotazů.

• Sada je redukovatelná na mnoho, pokud existuje celková vypočítatelná funkce , takže prvek je v právě tehdy, pokud je v . Takovou funkci lze použít ke generování Turingovy redukce (výpočtem , dotazováním na Oracle a následnou interpretací výsledku).${\ displaystyle A}$${\ displaystyle B}$ ${\ displaystyle f}$${\ displaystyle n}$${\ displaystyle A}$${\ displaystyle f (n)}$${\ displaystyle B}$${\ displaystyle f (n)}$
• Snížení pravdivostní tabulka nebo slabý pokles pravdivostní tabulka musí předložit všechny jeho věšteckých dotazů najednou. Při redukci pravdivostní tabulky redukce dává také booleovskou funkci ( pravdivostní tabulku ), která po zodpovězení dotazů vytvoří konečnou odpověď redukce. Při slabé redukci tabulky pravdivosti používá redukce odpovědi Oracle jako základ pro další výpočet v závislosti na daných odpovědích (ale nepoužívá Oracle). Ekvivalentně je slabá redukce pravdivostní tabulky ta, u které je použití redukce omezeno vypočítatelnou funkcí. Z tohoto důvodu se slabé redukční tabulky pravdy někdy nazývají „omezené Turingovy“ redukce.

Druhým způsobem, jak vytvořit silnější představu o redukovatelnosti, je omezit výpočetní zdroje, které může program implementující Turingovu redukci použít. Tyto limity na výpočetní složitosti redukce jsou důležité při studiu subrecursive tříd, jako je P . Sada A je polynomiálně časově redukovatelná na množinu, pokud existuje Turingova redukce na, která běží v polynomiálním čase. Koncept zmenšení log-prostoru je podobný. ${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$

Tyto redukce jsou silnější v tom smyslu, že poskytují jemnější rozlišení do tříd ekvivalence a uspokojují přísnější požadavky než Turingovy redukce. V důsledku toho je takové snížení těžší najít. Je možné, že neexistuje způsob, jak vytvořit redukci typu jedna z jedné sady do druhé, i když pro stejné sady existuje Turingova redukce.

Slabší redukce

Podle teze Church-Turing je Turingova redukce nejobecnější formou efektivně vypočítatelné redukce. Uvažuje se však i o slabších redukcích. Sada se říká, že aritmetická v případě, je definovat pomocí vzorce z Peanovy aritmetiky se jako parametr. Souprava je hyperarithmetical v případě, že je rekurzivní pořadové tak, že je vypočitatelný z , a-zopakováno Turing skoku . Pojem relativní konstruovatelnost je v teorii množin důležitým pojmem redukovatelnosti. ${\ displaystyle A}$ ${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle \ alpha}$${\ displaystyle A}$${\ displaystyle B ^ {(\ alpha)}}$${\ displaystyle B}$

Viz také

• Karp redukce

Poznámky

Reference

• M. Davis, ed., 1965. The Undecidable — Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven, New York. Dotisk, Dover, 2004. ISBN  0-486-43228-9 .
• SC Kleene, 1952. Úvod do metamatematiky. Amsterdam: Severní Holandsko.
• SC Kleene a EL Post, 1954. „Horní semi-mřížka stupňů rekurzivní neřešitelnosti“. Annals of Mathematics v. 2 č. 59, 379–407.
• Post, EL (1944). "Rekurzivně vyčíslitelné množiny kladných celých čísel a jejich problémy s rozhodováním" ( PDF ) . Bulletin of the American Mathematical Society . 50 : 284–316. doi : 10.1090 / s0002-9904-1944-08111-1 . Citováno 2015-12-17 .
• A. Turing, 1939. „Logické systémy založené na řadových číslech.“ Proceedings of the London Mathematics Society , ser. 2 v. 45, s. 161–228. Přetištěno v „The Undecidable“, M. Davis ed., 1965.
• H. Rogers, 1967. Teorie rekurzivních funkcí a efektivní vypočítatelnost. McGraw-Hill.
• R. Soare, 1987. Rekurzivně nespočetné množiny a stupně, Springer.
• Davis, Martin (listopad 2006). „Co je ... Turingova Reducibilita?“ ( PDF ) . Oznámení Americké matematické společnosti . 53 (10): 1218–1219 . Citováno 2008-01-16 .

externí odkazy

• Slovník NIST algoritmů a datových struktur: Turingova redukce