Rýže – Shapiro věta - Rice–Shapiro theorem

v teorie vypočítatelnosti, Rýže – Shapiro věta je zobecněním Riceova věta, a je pojmenována po Henry Gordon Rice a Norman Shapiro.^[1]

Formální prohlášení

Nechat A být množinou částečné rekurzivní unární funkce na doméně přirozená čísla takové, že soubor ${displaystyle Ix (A): = {nmid varphi _ {n} v A}}$ je rekurzivně spočetné, kde ${displaystyle varphi _ {n}}$ označuje ${displaystyle n}$ -tá částečná rekurzivní funkce v a Gödelovo číslování.

Pak pro jakoukoli unární částečnou rekurzivní funkci ${displaystyle psi}$ , my máme:

{displaystyle psi v ALeftrightarrow existuje}

konečná funkce

{displaystyle heta subseteq psi}

takhle

{displaystyle heta v A.}

V daném příkazu je konečnou funkcí funkce s konečnou doménou ${displaystyle x_ {1}, x_ {2}, ..., x_ {m}}$ a ${displaystyle heta subseteq psi}$ znamená to pro každého ${displaystyle xin {x_ {1}, x_ {2}, ..., x_ {m}}}$ to platí ${displaystyle psi (x)}$ je definováno a rovno ${displaystyle heta (x)}$ .

Perspektiva efektivní topologie

Pro jakoukoli konečnou unární funkci ${displaystyle heta}$ na celá čísla, nechť ${displaystyle C (heta)}$ označit „frustum“ všech částečných rekurzivních funkcí, které jsou definovány, a souhlasit s nimi ${displaystyle heta}$ ,na ${displaystyle heta}$ doména.

Vybavte sadu všech částečných rekurzivních funkcí topologií generovanou Thesefrusta as základna. Všimněte si, že pro každé frustum ${displaystyle C}$ , ${displaystyle Ix (C)}$ je rekurzivně vyčíslitelný. Obecněji platí pro každou sadu ${displaystyle A}$ částečných rekurzivních funkcí:

${displaystyle Ix (A)}$ je rekurzivně vyčíslitelný iff ${displaystyle A}$ je rekurzivně vyčíslitelné spojení frusta.

Poznámky

^ Rogers Jr., Hartley (1987). Teorie rekurzivních funkcí a efektivní vypočítatelnost. MIT Stiskněte. ISBN 0-262-68052-1.

Reference

Cutland, Nigel (1980). Vyčíslitelnost: úvod do teorie rekurzivních funkcí. Cambridge University Press.; Věta 7-2.16.
Rogers Jr., Hartley (1987). Teorie rekurzivních funkcí a efektivní vypočítatelnost. MIT Stiskněte. p. 482. ISBN 0-262-68052-1.
Odifreddi, Piergiorgio (1989). Teorie klasické rekurze. Severní Holandsko.

Tento počítačový článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[rogers_1987-1] Rogers Jr., Hartley (1987). Teorie rekurzivních funkcí a efektivní vypočítatelnost. MIT Stiskněte. ISBN 0-262-68052-1.

[1]