Kleenova věta o rekurzi - Kleenes recursion theorem - Wikipedia

v teorie vypočítatelnosti, Kleenovy věty o rekurzi jsou dvojice základních výsledků o aplikaci vypočítatelné funkce podle jejich vlastních popisů. Věty byly poprvé prokázány Stephen Kleene v roce 1938 a objeví se v jeho knize z roku 1952 Úvod do matematiky. Příbuzná věta, která konstruuje pevné body vypočítatelné funkce, je známá jako Rogersova věta a je kvůli Hartley Rogers, Jr. (Rogers 1967 ).

Věty o rekurzi lze použít ke konstrukci pevné body některých operací dne vypočítatelné funkce, vygenerovat quines a konstruovat funkce definované pomocí rekurzivní definice.

Zápis

Výrok vět se vztahuje k přípustné číslování ${ displaystyle varphi}$ z částečné rekurzivní funkce, takže funkce odpovídající indexu ${ displaystyle e}$ je ${ displaystyle varphi _ {e}}$. Z programového hlediska ${ displaystyle e}$ představuje program a ${ displaystyle varphi _ {e}}$ představuje funkci vypočítanou tímto programem.

Li ${ displaystyle F}$ a ${ displaystyle G}$ jsou dílčí funkce na přirozených číslech, zápis ${ displaystyle F simeq G}$ znamená, že pro každého n, buď ${ displaystyle F (n)}$ a ${ displaystyle G (n)}$ jsou definovány a jsou stejné, nebo jinak ${ displaystyle F (n)}$ a ${ displaystyle G (n)}$ jsou nedefinované.

Rogersova věta o pevném bodě

Vzhledem k funkci ${ displaystyle F}$, a pevný bod z ${ displaystyle F}$ je index ${ displaystyle e}$ takhle ${ displaystyle varphi _ {e} simeq varphi _ {F (e)}}$. Rogers (Rogers 1967, §11.2) popisuje následující výsledek jako „jednodušší verzi“ Kleeneovy (druhé) věty o rekurzi.

Rogersova věta o pevném bodě. Li ${ displaystyle F}$ je celkem vypočítatelná funkce, má pevný bod.

Důkaz věty o pevném bodě

Důkaz používá konkrétní celkovou vypočítatelnou funkci ${ displaystyle h}$, definováno následovně. Vzhledem k přirozenému číslu ${ displaystyle x}$, funkce ${ displaystyle h}$ vypíše index částečné vypočítatelné funkce, která provede následující výpočet:

Vzhledem k tomu, vstup ${ displaystyle y}$, první pokus o výpočet ${ displaystyle varphi _ {x} (x)}$. Pokud tento výpočet vrátí výstup ${ displaystyle e}$, pak vypočítat ${ displaystyle varphi _ {e} (y)}$ a vrátit jeho hodnotu, pokud existuje.

Tedy pro všechny indexy ${ displaystyle x}$ částečných vypočítatelných funkcí, pokud ${ displaystyle varphi _ {x} (x)}$ je tedy definován ${ displaystyle varphi _ {h (x)} simeq varphi _ { varphi _ {x} (x)}}$. Li ${ displaystyle varphi _ {x} (x)}$ tedy není definován ${ displaystyle varphi _ {h (x)}}$ je funkce, která není nikde definována. Funkce ${ displaystyle h}$ lze zkonstruovat z částečné vypočítatelné funkce ${ displaystyle g (x, y)}$ popsáno výše a věta s-m-n: pro každého ${ displaystyle x}$, ${ displaystyle h (x)}$ je index programu, který počítá funkci ${ displaystyle y mapsto g (x, y)}$.

Chcete-li vyplnit důkaz, nechte ${ displaystyle F}$ být libovolnou celkovou vypočítatelnou funkcí a konstruovat ${ displaystyle h}$ jak je uvedeno výše. Nechat ${ displaystyle e}$ být indexem složení ${ Displaystyle F Cir h}$, což je celkem vypočítatelná funkce. Pak ${ displaystyle varphi _ {h (e)} simeq varphi _ { varphi _ {e} (e)}}$ podle definice ${ displaystyle h}$.Ale protože ${ displaystyle e}$ je index ${ Displaystyle F Cir h}$, ${ Displaystyle varphi _ {e} (e) = (F Circ h) (e)}$, a tudíž ${ displaystyle varphi _ { varphi _ {e} (e)} simeq varphi _ {F (h (e))}}$. Přechodností ${ displaystyle simeq}$, to znamená ${ displaystyle varphi _ {h (e)} simeq varphi _ {F (h (e))}}$. Proto ${ displaystyle varphi _ {n} simeq varphi _ {F (n)}}$ pro ${ displaystyle n = h (e)}$.

Tento důkaz je konstrukcí a částečná rekurzivní funkce který implementuje Y kombinátor.

Volné funkce s pevným bodem

Funkce ${ displaystyle F}$ takhle ${ displaystyle varphi _ {e} ne simeq varphi _ {F (e)}}$ pro všechny ${ displaystyle e}$ je nazýván pevný bod zdarma. Věta o pevném bodě ukazuje, že žádná celková vypočítatelná funkce není pevným bodem volná, ale existuje mnoho nevypočitatelných funkcí volného bodu. Arslanovovo kritérium úplnosti uvádí, že jediný rekurzivně spočetné Turingův stupeň který počítá funkci volného bodu s pevným bodem je 0′, stupeň zastavení problému (Soare 1987, str. 88).

Kleenova druhá věta o rekurzi

Druhá věta o rekurzi je zobecněním Rogersovy věty s druhým vstupem do funkce. Jedna neformální interpretace druhé věty o rekurzi spočívá v tom, že je možné konstruovat autoreferenční programy; viz níže „Aplikace do quines“.

Druhá věta o rekurzi. Pro jakoukoli částečnou rekurzivní funkci ${ displaystyle Q (x, y)}$ existuje index ${ displaystyle p}$ takhle ${ displaystyle varphi _ {p} simeq lambda y.Q (p, y)}$.

Věta může být prokázána z Rogersovy věty tím, že necháme ${ displaystyle F (p)}$ být funkcí takovou ${ displaystyle varphi _ {F (p)} (y) = Q (p, y)}$ (konstrukce popsaná v Věta S-m-n ). Jeden pak může ověřit, že pevný bod tohoto ${ displaystyle F}$ je index ${ displaystyle p}$ podle potřeby. Věta je konstruktivní v tom smyslu, že pevná vypočítatelná funkce mapuje index pro Q do indexu p.

Srovnání s Rogersovou větou

Druhá Kleenova věta o rekurzi a Rogersova věta mohou být navzájem poměrně jednoduše dokázány (Jones 1997, s. 229–230). Přímý důkaz Kleeneovy věty (Kleene 1952, s. 352–353) nevyužívá univerzální program, což znamená, že věta platí pro určité subrekurzivní programovací systémy, které univerzální program nemají.

Aplikace na quines

Klasickým příkladem použití druhé věty o rekurzi je funkce ${ displaystyle Q (x, y) = x}$. Odpovídající index ${ displaystyle p}$ v tomto případě získá vypočítatelnou funkci, která při použití na libovolnou hodnotu vydá svůj vlastní index (Cutland 1980, str. 204). Když jsou vyjádřeny jako počítačové programy, jsou tyto indexy známé jako quines.

Následující příklad v Lisp ilustruje, jak ${ displaystyle p}$ v důsledku může být efektivně vytvořen z funkce ${ displaystyle Q}$. Funkce s11 v kódu je funkce tohoto jména vytvořená Věta S-m-n.

Q lze změnit na libovolnou funkci se dvěma argumenty.

(setq Q '(lambda (X y) X))(setq s11 '(lambda (F X) (seznam 'lambda '(y) (seznam F X 'y))))(setq n (seznam 'lambda '(X y) (seznam Q (seznam s11 'X 'X) 'y)))(setq p (eval (seznam s11 n n)))

Výsledky následujících výrazů by měly být stejné. ${ displaystyle varphi}$ p (nula)

(eval (seznam p nula))

Q (p, nula)

(eval (seznam Q p nula))

Aplikace na eliminaci rekurze

Předpokládejme to ${ displaystyle g}$ a ${ displaystyle h}$ jsou celkem vypočítatelné funkce, které se používají v rekurzivní definici funkce ${ displaystyle f}$:

${ displaystyle f (0, y) simeq g (y),}$

${ displaystyle f (x + 1, y) simeq h (f (x, y), x, y),}$

Druhá věta o rekurzi může být použita k ukázce, že takové rovnice definují vypočítatelnou funkci, kde pojem vypočítatelnost nemusí, prima facie, umožňovat rekurzivní definice (například ji může definovat μ-rekurze nebo Turingovy stroje ). Tuto rekurzivní definici lze převést na vypočítatelnou funkci ${ displaystyle varphi _ {F} (e, x, y)}$ to předpokládá ${ displaystyle e}$ je index sám o sobě, pro simulaci rekurze:

${ displaystyle varphi _ {F} (e, 0, y) simeq g (y),}$

${ displaystyle varphi _ {F} (e, x + 1, y) simeq h ( varphi _ {e} (x, y), x, y).}$

Věta o rekurzi zakládá existenci vypočítatelné funkce ${ displaystyle varphi _ {f}}$ takhle ${ displaystyle varphi _ {f} (x, y) simeq varphi _ {F} (f, x, y)}$. Tím pádem ${ displaystyle f}$ splňuje danou rekurzivní definici.

Reflexivní programování

Reflexní, nebo reflexní, programování odkazuje na použití vlastního odkazu v programech. Jones (Jones 1997 ) představuje pohled na druhou větu o rekurzi na základě reflexivního jazyka. Ukázalo se, že definovaný reflexivní jazyk není silnější než jazyk bez reflexe (protože tlumočník pro reflexivní jazyk může být implementován bez použití reflexe); pak se ukazuje, že věta o rekurzi je v reflexivním jazyce téměř triviální.

První věta o rekurzi

Zatímco druhá věta o rekurzi je o pevných bodech vypočítatelných funkcí, první věta o rekurzi souvisí s pevnými body určenými operátory výčtu, které jsou vypočítatelným analogem indukčních definic. An operátor výčtu je sada párů (A,n) kde A je (kód pro a) konečná množina čísel a n je jediné přirozené číslo. Často, n se bude zobrazovat jako kód pro uspořádanou dvojici přirozených čísel, zvláště když jsou funkce definovány pomocí operátorů výčtu. Operátoři výčtu mají při studiu klíčový význam redukovatelnost výčtu.

Každý operátor výčtu Φ určuje funkci od sad přirozených po sady přirozených daných

${ displaystyle Phi (X) = {n střední existuje A subseteq X [(A, n) v Phi] }.}$

A rekurzivní operátor je operátor výčtu, který při zadání grafu částečné rekurzivní funkce vždy vrátí graf částečné rekurzivní funkce.

Pevný bod operátoru výčtu Φ je množina F takové, že Φ (F) = F. První teorém výčtu ukazuje, že pevné body lze efektivně získat, pokud je vypočítatelný samotný operátor výčtu.

První věta o rekurzi. Následující tvrzení platí.

1. Pro jakýkoli vypočítatelný operátor výčtu Φ existuje rekurzivně vyčíslitelná sada F takové, že Φ (F) = F a F je nejmenší sada s touto vlastností.
2. Pro jakýkoli rekurzivní operátor Ψ existuje částečná vypočítatelná funkce φ tak, že Ψ (φ) = φ a φ je nejmenší částečná vypočítatelná funkce s touto vlastností.

Příklad

Stejně jako druhá věta o rekurzi lze první větu o rekurzi použít k získání funkcí splňujících systémy rekurzních rovnic. Chcete-li použít první větu o rekurzi, je třeba nejprve rekurzivní rovnice přepracovat jako rekurzivní operátor.

Zvažte rekurzní rovnice pro faktoriál funkce F:

${ displaystyle f (0) = 1}$

${ Displaystyle f (n + 1) = (n + 1) cdot f (n)}$

Odpovídající rekurzivní operátor Φ bude mít informace, které řeknou, jak se dostat na další hodnotu F z předchozí hodnoty. Rekurzivní operátor však ve skutečnosti definuje graf F. Nejprve the bude obsahovat dvojici ${ displaystyle ( varnothing, (0,1))}$. To naznačuje F(0) je jednoznačně 1, a tedy dvojice (0,1) je v grafu F.

Dále pro každého n a m, Φ bude obsahovat dvojici ${ displaystyle ( {(n, m) }, (n + 1, (n + 1) cdot m))}$. To naznačuje, že pokud F(n) je m, pak F(n +1) je (n + 1)m, takže dvojice (n + 1, (n + 1)m) je v grafu F. Na rozdíl od základního případu F(0) = 1, rekurzivní operátor vyžaduje určité informace o F(n), než definuje hodnotu F(n + 1).

První věta o rekurzi (zejména část 1) uvádí, že existuje množina F takové, že Φ (F) = F. Sada F bude sestávat výhradně z uspořádaných dvojic přirozených čísel a bude grafem faktorové funkce F, podle přání.

Omezení na rekurzivní rovnice, které lze přepracovat jako rekurzivní operátory, zajišťuje, že rekurzní rovnice skutečně definují nejméně pevný bod. Zvažte například sadu rekurzních rovnic:

${ displaystyle g (0) = 1}$

${ displaystyle g (n + 1) = 1}$

${ displaystyle g (2n) = 0}$

Neexistuje žádná funkce G uspokojení těchto rovnic, protože z nich vyplývá G(2) = 1 a také implikovat G(2) = 0. Neexistuje tedy žádný pevný bod G splnění těchto rekurzních rovnic. Je možné vytvořit operátor výčtu odpovídající těmto rovnicím, ale nebude to rekurzivní operátor.

Důkazní skica pro první větu o rekurzi

Důkaz části 1 první věty o rekurzi se získá iterací operátoru výčtu Φ začínajícího prázdnou množinou. Nejprve sekvence F_k je konstruován pro ${ displaystyle k = 0,1, ldots}$. Nechat F₀ být prázdná množina. Pro každého postupujeme indukčně k, nechť F_{k + 1} být ${ displaystyle F_ {k} pohár Phi (F_ {k})}$. Konečně, F se považuje za ${ displaystyle bigcup F_ {k}}$. Zbývající část důkazu spočívá v ověření, že F je rekurzivně vyčíslitelný a je nejméně pevným bodem Φ. Sekvence F_k použitý v tomto dokladu odpovídá řetězci Kleene v dokladu o Kleeneova věta o pevném bodě.

Druhá část první věty o rekurzi vyplývá z první části. Předpoklad, že Φ je rekurzivní operátor, se používá k prokázání, že pevný bod Φ je graf částečné funkce. Klíčovým bodem je, že pokud je pevný bod F není graf funkce, pak tam je nějaký k takhle F_k není graf funkce.

Srovnání s druhou větou o rekurzi

Ve srovnání s druhou větou o rekurzi vytváří první věta o rekurzi silnější závěr, ale pouze pokud jsou splněny užší hypotézy. Rogers (Rogers 1967 ) používá tento výraz věta o slabé rekurzi pro první větu o rekurzi a věta o silné rekurzi pro druhou větu o rekurzi.

Jeden rozdíl mezi první a druhou větou o rekurzi spočívá v tom, že pevné body získané první větou o rekurzi jsou zaručeně nejméně pevné body, zatímco body získané z druhé věty o rekurzi nemusí být nejméně pevnými body.

Druhým rozdílem je, že první věta o rekurzi platí pouze pro systémy rovnic, které lze přepracovat jako rekurzivní operátory. Toto omezení je podobné omezení na nepřetržité provozovatele v EU Kleeneova věta o pevném bodě z teorie objednávek. Druhý teorém rekurze lze použít na jakoukoli celkovou rekurzivní funkci.

Zobecněná věta

V souvislosti s jeho teorií číslování Ershov ukázal, že Kleenova věta o rekurzi platí pro všechny precomplete číslování (Barendregt & Terwijn 2019, str. 1151). Gödelovo číslování je předkompletní číslování na množině vypočítatelných funkcí, takže zobecněná věta poskytuje teorém o rekurzi Kleene jako speciální případ. Viz (Ershov 1999, §4.14) pro průzkum v angličtině.

Vzhledem k předem dokončenému číslování ${ displaystyle nu}$ pak pro jakoukoli částečnou vypočítatelnou funkci ${ displaystyle f}$ se dvěma parametry existuje celkem vypočítatelná funkce ${ displaystyle t}$ s jedním takovým parametrem

${ displaystyle forall n in mathbb {N}: nu circ f (n, t (n)) = nu circ t (n).}$

Viz také

• Denotační sémantika, kde se pro stejný účel jako věta o první rekurzi používá další věta s nejméně pevným bodem.
• Kombinátory s pevným bodem, které se používají v lambda kalkul pro stejný účel jako první věta o rekurzi.

Reference

• Barendregt, Henk; Terwijn, Sebastiaan A. (2019). "Věty o pevném bodě pro předkompletní číslování". Annals of Pure and Applied Logic. 170 (10): 1151–1161. doi:10.1016 / j.apal.2019.04.013. hdl:2066/205967. ISSN  0168-0072. Citováno 6. května 2020.
• Cutland, Nigel J. (1980). Vypočítatelnost: Úvod do teorie rekurzivních funkcí. Cambridge University Press. doi:10.1017 / cbo9781139171496. ISBN  9781139935609. OCLC  488175597. Citováno 6. května 2020.
• Ershov, Yuri L. (1999). „Část 4: Matematika a teorie vypočítatelnosti. 14. Teorie číslování“. V Griffor, Edward R (ed.). Příručka teorie vypočítatelnosti. Studium logiky a základy matematiky. 140. Amsterdam: Elsevier. 473–503. ISBN  9780444898821. OCLC  162130533. Citováno 6. května 2020.
• Kleene, S. C. (1938). „Na notaci pro pořadová čísla“ (PDF). Journal of Symbolic Logic. 3 (4): 150–155. doi:10.2307/2267778. ISSN  0022-4812. JSTOR  2267778. Citováno 6. května 2020.
• Kleene, S. C. (1952). Úvod do matematiky. Bibliotheca Mathematica. North-Holland Publishing. ISBN  9780720421033. OCLC  459805591. Citováno 6. května 2020.
• Jockusch, C. G.; Lerman, M .; Soare, R. I.; Solovay, R. M. (1989). "Rekurzivně vyčíslitelné sady modulo iterovaných skoků a rozšíření kritéria úplnosti Arslanova". The Journal of Symbolic Logic. 54 (4): 1288–1323. doi:10.1017 / S0022481200041104. ISSN  0022-4812. JSTOR  2274816.
• Jones, Neil D. (1997). Vyčíslitelnost a složitost: Z pohledu programování. Cambridge, Massachusetts: MIT Stiskněte. ISBN  9780262100649. OCLC  981293265.
• Rogers, Hartley (1967). Teorie rekurzivních funkcí a efektivní vypočítatelnost. Cambridge, Massachusetts: MIT Stiskněte. ISBN  9780262680523. OCLC  933975989. Citováno 6. května 2020.
• Soare, R. I. (1987). Rekurzivně vyčíslitelné množiny a stupně: Studie vypočítatelných funkcí a vypočítatelně generovaných množin. Perspektivy v matematické logice. Berlín; New York: Springer-Verlag. ISBN  9780387152998. OCLC  318368332.

externí odkazy

• "Rekurzivní funkce" vstup od Piergiorgio Odifreddi v Stanfordská encyklopedie filozofie, 2012.