Rekurzivní sada - Recursive set

v teorie vypočítatelnosti, a soubor z přirozená čísla je nazýván rekurzivní, vypočitatelný nebo rozhodnutelné pokud existuje algoritmus který vezme číslo jako vstup, ukončí se po konečné době (možná v závislosti na daném čísle) a správně rozhodne, zda číslo patří do množiny nebo ne.

Volá se sada, která není vypočítatelná nepočítatelné nebo nerozhodnutelný.

Obecnější třídu sad než ty, které lze rozhodnout, tvoří rekurzivně vyčíslitelné sady, také zvaný semidecidable sady. U těchto sad je vyžadováno pouze to, že existuje algoritmus, který správně rozhodne, kdy je číslo je v sadě; algoritmus nemusí dát žádnou odpověď (ale špatnou odpověď) pro čísla, která nejsou v sadě.

Formální definice

Podmnožina S z přirozená čísla je nazýván rekurzivní pokud existuje celkový vypočítatelná funkce F takhle F(X) = 1 pokud X∈S a F(X) = 0 pokud X∉S. Jinými slovy, sada S je rekurzivní kdyby a jen kdyby the funkce indikátoru 1_S je vypočitatelný.

Příklady a příklady

Příklady:

• Každý konečný nebo cofinite podmnožinu přirozených čísel lze vypočítat. To zahrnuje tyto speciální případy:
  • The prázdná sada je vypočítatelný.
  • Celá sada přirozených čísel je vypočítatelná.
  • Každé přirozené číslo (jak je definováno v teorii standardních množin ) je vypočítatelný; to znamená, že množinu přirozených čísel menších než dané přirozené číslo lze vypočítat.
• Sada prvočísla je vypočítatelný.
• A rekurzivní jazyk je rekurzivní podmnožina a formální jazyk.
• Soubor Gödelových čísel aritmetických důkazů popsaných v článku Kurta Gödela „O formálně nerozhodnutelných propozicích Principia Mathematica a souvisejících systémech I“ je vypočítatelný; vidět Gödelovy věty o neúplnosti.

Jiné příklady:

• Sada Turingovy stroje, které se zastaví není vypočítatelný.
• The třída izomorfismu dvou konečných zjednodušených komplexů nelze vypočítat.
• Sada zaneprázdnění bobří šampioni není vypočítatelný.

Vlastnosti

Li A je rekurzivní množina pak doplněk z A je rekurzivní množina. Li A a B jsou rekurzivní množiny A ∩ B, A ∪ B a obraz A × B pod Funkce párování Cantor jsou rekurzivní množiny.

Sada A je rekurzivní množina kdyby a jen kdyby A a doplněk z A jsou oba rekurzivně vyčíslitelné sady. The preimage rekurzivní množiny pod a celkový vypočítatelná funkce je rekurzivní množina. Obrázek vypočítatelné sady pod celkovou vypočítatelnou bijekce je vypočítatelný.

Sada je rekurzivní, právě když je na úrovni Δ⁰
₁ z aritmetická hierarchie.

Sada je rekurzivní tehdy a jen tehdy, pokud jde buď o rozsah neklesající celkové vypočítatelné funkce, nebo o prázdnou sadu. Vypočitatelný je obrázek vypočítatelné množiny pod neklesající celkovou vypočítatelnou funkcí.

Reference

• Cutland, N. Vyčíslitelnost. Cambridge University Press, Cambridge-New York, 1980. ISBN  0-521-22384-9; ISBN  0-521-29465-7
• 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ě vyčíslitelné množiny a stupně. Perspektivy v matematické logice. Springer-Verlag, Berlín, 1987. ISBN  3-540-15299-7

externí odkazy

• Sacharov, Alexi. "Rekurzivní sada". MathWorld.