Sada indexů (teorie rekurze) - Index set (recursion theory)
V oblasti teorie rekurze, sady indexů popsat třídy částečné rekurzivní funkce, konkrétně dávají všechny indexy funkcí v dané třídě podle pevného výčtu částečných rekurzivních funkcí (a Gödelovo číslování ).
Definice
Opravte výčet všech částečných rekurzivních funkcí nebo ekvivalentně rekurzivně spočetné nastavuje, kterým Etaková sada je a Etato funkce (jejíž doména je ) je .
Nechat být třídou částečných rekurzivních funkcí. Li pak je sada indexů z . Obecně je sada indexů, pokud pro každý s (tj. indexují stejnou funkci), máme . Intuitivně se jedná o množiny přirozených čísel, které popisujeme pouze s odkazem na funkce, které indexují.
Sady indexů a Riceova věta
Většina sad indexů je kromě dvou triviálních výjimek nepočitatelná (nerekurzivní). To je uvedeno v Riceova věta:
Nechat být třídou částečných rekurzivních funkcí se sadou indexů . Pak je rekurzivní právě tehdy je prázdný nebo je vše z .
kde je sada přirozená čísla, počítaje v to nula.
Riceova věta říká „jakákoli netriviální vlastnost částečných rekurzivních funkcí je nerozhodná“[1]
Poznámky
- ^ Odifreddi, P. G. Teorie klasické rekurze, svazek 1.; strana 151
Reference
- Odifreddi, P. G. (1992). Teorie klasické rekurze, svazek 1. Elsevier. str. 668. ISBN 0-444-89483-7.
- Rogers Jr., Hartley (1987). Teorie rekurzivních funkcí a efektivní vypočítatelnost. MIT Stiskněte. str. 482. ISBN 0-262-68052-1.