Rekurzivně vyčíslitelná sada - Recursively enumerable set

v teorie vypočítatelnosti, tradičně nazývaná teorie rekurze, množina S z přirozená čísla je nazýván rekurzivně spočetné, vypočítatelně vyčíslitelné, semidecidable, prokazatelné nebo Turing rozpoznatelný li:

• Tady je algoritmus taková, že množina vstupních čísel, pro kterou se algoritmus zastaví, je přesně S.

Nebo ekvivalentně

• Tady je algoritmus, který stanoví výčet členové S. To znamená, že jeho výstupem je jednoduše seznam všech členů S: s₁, s₂, s₃, .... Li S je nekonečný, tento algoritmus poběží navždy.

První podmínka naznačuje, proč je termín semidecidable je někdy používán; druhý naznačuje proč vypočítatelně vyčíslitelné se používá. Zkratky re. a e.e. se často používají, dokonce i v tištěné podobě, místo celé fráze.

v teorie výpočetní složitosti, třída složitosti obsahující všechny rekurzivně vyčíslitelné sady je RE. V teorii rekurze je mříž z r.e. sady v zahrnutí jsou označeny ${ displaystyle { mathcal {E}}}$.

Formální definice

Sada S přirozených čísel rekurzivně spočetné pokud existuje částečná rekurzivní funkce jehož doména je přesně S, což znamená, že funkce je definována právě tehdy, když je její vstup členem S.

Ekvivalentní formulace

Následují všechny ekvivalentní vlastnosti sady S přirozených čísel:

Semidecidovatelnost:

• Sada S je rekurzivně vyčíslitelný. To znamená S je doména (společný rozsah) částečné rekurzivní funkce.
• Existuje částečná rekurzivní funkce F takové, že:

${ displaystyle f (x) = left {{ begin {matrix} 1 & { mbox {if}} x in S { mbox {undefined / does not halt}} {{mbox { if}} x notin S end {matrix}} right.}$

Vyčíslitelnost:

• Sada S je rozsah částečné rekurzivní funkce.
• Sada S je rozsah celkové rekurzivní funkce nebo je prázdný. Li S je nekonečný, lze zvolit funkci injekční.
• Sada S je rozsah a primitivní rekurzivní funkce nebo prázdné. I kdyby S je nekonečný, může být v tomto případě nutné opakovat hodnoty.

Diophantin:

• Existuje polynom p s celočíselnými koeficienty a proměnnými X, A, b, C, d, E, F, G, h, i přes přirozená čísla taková

${ Displaystyle x v S Leftrightarrow existuje a, b, c, d, e, f, g, h, i (p (x, a, b, c, d, e, f, g, h, i) = 0).}$

(Počet vázaných proměnných v této definici je dosud nejznámější; je možné, že k definování všech diofantinových sad lze použít nižší počet.)

• Existuje polynom z celých čísel na celá čísla tak, že množina S obsahuje přesně nezáporná čísla ve svém rozsahu.

Ekvivalence semidecidability a enumerability lze získat technikou rybinování.

Diophantine charakterizace rekurzivně spočetné množiny, i když ne tak přímočaré nebo intuitivní jako první definice, byly nalezeny Jurij Matijasevič jako součást záporného řešení Hilbertův desátý problém. Diophantine množiny předcházejí teorii rekurze, a proto jsou historicky prvním způsobem, jak tyto sady popsat (ačkoli tato rovnocennost byla zaznamenána až více než tři desetiletí po zavedení rekurzivně vyčíslitelných množin).

Rekurzivní výčet množiny všech Turingových strojů, které se zastaví na pevném vstupu: Simulujte všechny Turingovy stroje (vyčíslené na svislé ose) krok za krokem (vodorovná osa), pomocí zobrazeného harmonogramu diagonalizace. Pokud se stroj ukončí, vytiskněte jeho číslo. Tímto způsobem se nakonec vytiskne číslo každého ukončovacího stroje. V příkladu algoritmus vytiskne „9, 13, 4, 15, 12, 18, 6, 2, 8, 0, ...“

Příklady

• Každý rekurzivní množina je rekurzivně vyčíslitelný, ale není pravda, že každá rekurzivně vyčíslitelná sada je rekurzivní. U rekurzivních sad musí algoritmus také říci, zda je vstup ne v sadě - toto se nevyžaduje od rekurzivně spočetných množin.
• A rekurzivně vyčíslitelný jazyk je rekurzivně vyčíslitelná podmnožina a formální jazyk.
• Sada všech prokazatelných vět v efektivně prezentovaném axiomatickém systému je rekurzivně spočetnou množinou.
• Matijasevičova věta uvádí, že každá rekurzivně vyčíslitelná množina je a Diophantine set (obráceně platí triviálně).
• The jednoduché sady jsou rekurzivně vyčíslitelné, ale ne rekurzivní.
• The kreativní sady jsou rekurzivně vyčíslitelné, ale ne rekurzivní.
• Žádný produktivní sada je ne rekurzivně spočetné.
• Vzhledem k Gödelovo číslování ${ displaystyle phi}$ vypočítatelných funkcí, množiny ${ displaystyle { langle i, x rangle mid phi _ {i} (x) downarrow }}$ (kde ${ displaystyle langle i, x rangle}$ je Funkce párování Cantor a ${ displaystyle phi _ {i} (x) downarrow}$ označuje ${ displaystyle phi _ {i} (x)}$ je definován) je rekurzivně vyčíslitelný (srov. obrázek pro pevnou X). Tato sada kóduje zastavení problému protože popisuje vstupní parametry, pro které každý Turingův stroj zastaví.
• Vzhledem k číslování podle Gödela ${ displaystyle phi}$ vypočítatelných funkcí, množiny ${ Displaystyle lbrace levá langle x, y, z pravá rangle střední phi _ {x} (y) = z rbrace}$ je rekurzivně vyčíslitelný. Tato sada kóduje problém rozhodování o hodnotě funkce.
• Vzhledem k částečné funkci F od přirozených čísel do přirozených čísel, F je částečná rekurzivní funkce právě tehdy, když je graf F, tj. množina všech párů ${ displaystyle langle x, f (x) rangle}$ takhle f (x) je definováno, je rekurzivně vyčíslitelné.

Vlastnosti

Li A a B jsou rekurzivně spočetné množiny A ∩ B, A ∪ B a A × B (s uspořádanou dvojicí přirozených čísel mapovaných na jediné přirozené číslo pomocí Funkce párování Cantor ) jsou rekurzivně vyčíslitelné množiny. The preimage rekurzivně spočetné množiny pod částečnou rekurzivní funkcí je rekurzivně spočetná množina.

Sada je rekurzivně vyčíslitelná, právě když je na úrovni ${ displaystyle Sigma _ {1} ^ {0}}$ z aritmetická hierarchie.

Sada ${ displaystyle T}$ je nazýván ko-rekurzivně vyčíslitelné nebo jádro. Pokud je to doplněk ${ displaystyle mathbb {N} setminus T}$ je rekurzivně vyčíslitelný. Ekvivalentně je sada co-r.e. právě když je na úrovni ${ displaystyle Pi _ {1} ^ {0}}$ aritmetické hierarchie. Třída složitosti ko-rekurzivně vyčíslitelných množin je označena co-RE.

Sada A je rekurzivní (synonymum: computable) právě tehdy, pokud obojí A a doplněk A jsou rekurzivně vyčíslitelné. Sada je rekurzivní právě tehdy, pokud jde buď o rozsah rostoucí celkové rekurzivní funkce, nebo o konečnou hodnotu.

Některé páry rekurzivně vyčíslitelných sad jsou efektivně oddělitelné a některé nejsou.

Poznámky

Podle Církev – Turingova teze, kteroukoli efektivně vypočítatelnou funkci lze vypočítat pomocí a Turingův stroj, a tedy sada S je rekurzivně vyčíslitelný právě tehdy, když nějaký existuje algoritmus který dává výčet S. To však nelze brát jako formální definici, protože teze Church-Turing je spíše neformální domněnkou než formálním axiomem.

Definice rekurzivně vyčíslitelné množiny jako doména spíše částečné funkce než rozsah totální rekurzivní funkce, je v současných textech běžný. Tato volba je motivována skutečností, že v obecných teoriích rekurze, jako je teorie α-rekurze, bylo zjištěno, že definice odpovídající doménám je přirozenější. Jiné texty používají definici, pokud jde o výčty, což je ekvivalentní pro rekurzivně vyčíslitelné množiny.

Reference

• Rogers, H. Teorie rekurzivních funkcí a efektivní vypočítatelnost, MIT Stiskněte. ISBN  0-262-68052-1; ISBN  0-07-053522-1.
• Soare, R. Rekurzivně nespočetné množiny a stupně. Perspektivy v matematické logice. Springer-Verlag, Berlín, 1987. ISBN  3-540-15299-7.
• Soare, Robert I. Rekurzivně nespočetné množiny a stupně. Býk. Amer. Matematika. Soc. 84 (1978), č. 3. 6, 1149–1181.