Rekurze pruhů - Bar recursion

Rekurze pruhů je zobecněná forma rekurze vyvinutá C. Spectorem v jeho práci z roku 1962.[1] Souvisí to s bar indukce stejným způsobem primitivní rekurze souvisí s obyčejným indukce nebo transfinitní rekurze je spojen s transfinitní indukce.

Technická definice

Nechat PROTI, R, a Ó být typy, a i být libovolné přirozené číslo představující posloupnost parametrů převzatých z PROTI. Poté funkční sekvence F funkcí Fn z PROTIi+n → R na Ó je definována rekurzí pruhů z funkcí Ln : R → Ó a B s Bn : ((PROTIi+n → R) X (PROTIn → R)) → Ó li:

  • Fn((λα:PROTIi+n)r) = Ln(r) pro všechny r dost dlouho na to Ln+k na jakémkoli rozšíření r rovná se Ln. Za předpokladu L je spojitá sekvence, musí existovat r, protože spojitá funkce může využívat jen konečně mnoho dat.
  • Fn(str) = Bn(str, (λX:PROTI)Fn+1(kočka(str, X))) pro všechny str v PROTIi+n → R.

Tady je „kočka“ zřetězení funkce, odesílání str, X k posloupnosti, která začíná str, a má X jako jeho poslední termín.

(Tato definice je založena na definici Escardó a Olivy.[2])

Za předpokladu, že pro každou dostatečně dlouhou funkci (λα)r typu PROTIi → R, některé jsou n s Ln(r) = Bn((λα)r, (λX:PROTI)Ln+1(r)), pravidlo indukce sloupců to zajišťuje F je dobře definovaný.

Myšlenka je, že jeden rozšíří sekvenci libovolně pomocí rekurzního termínu B určit účinek, dokud dostatečně dlouhý uzel stromu sekvencí neskončí PROTI je dosaženo; pak základní termín L určuje konečnou hodnotu F. Podmínka dobře definované definice odpovídá požadavku, že každá nekonečná cesta musí nakonec projít dostatečně dlouhým uzlem: stejný požadavek, který je potřeba k vyvolání indukce pruhu.

Principy indukce tyče a rekurze tyče jsou intuitivní ekvivalenty axiomu závislé volby.[3]

Reference

  1. ^ C. Spector (1962). „Prokazatelně rekurzivní funkcionály analýzy: důkaz konzistence analýzy rozšířením principů v současné intuitivní matematice“. F. D. E. Dekker (ed.). Teorie rekurzivních funkcí: Proc. Symposia in Pure Mathematics. 5. Americká matematická společnost. s. 1–27.
  2. ^ Martín Escardó; Paulo Oliva. "Výběrové funkce, rekurze pruhů a zpětná indukce" (PDF). Matematika. Struct. v Comp.Science.
  3. ^ Jeremy Avigad; Solomon Feferman (1999). „VI: Gödelova funkční interpretace („ Dialectica “)“. v S. R. Buss (vyd.). Příručka teorie důkazů (PDF).