Vyjmenovaná sada

Enumerovatelná množina ( efektivně enumerovatelná , rekurzivně enumerovatelná , semi-rozhodnutelná množina [1] ) je množina konstruktivních objektů (například přirozených čísel ), jejíž všechny prvky lze získat pomocí nějakého algoritmu . Doplněk spočetné množiny se nazývá korekurzivně spočetný [2] . Každá vyčíslitelná množina je aritmetická . Korekurzivně vyčíslitelná množina nemusí být vyčíslitelná, ale je vždy aritmetická. množiny odpovídají hierarchie

Každá řešitelná množina je spočetná. Vyčíslitelná množina je rozhodnoutelná právě tehdy, když je spočetný i její doplněk. Jinými slovy, množina je rozhodnoutelná tehdy a pouze tehdy, je-li spočetná i korekurzivně spočetná. Podmnožina vyčíslitelné množiny nemusí být spočetná (a nemusí být ani aritmetická).

Množina všech nevyčíslitelných podmnožin je spočetná množina a množina všech nevyčíslitelných podmnožin  je nespočitatelná .

Varianty definice

Různé formalizace pojmu algoritmus odpovídají různým formálním definicím pojmu spočetné množiny, které se ukazují jako ekvivalentní. Na základě konceptu rekurzivní funkce lze tedy spočetné množiny přirozených čísel definovat jako obrazy částečně rekurzivních funkcí jedné proměnné (proto se spočetné množiny přirozených čísel někdy nazývají „rekurzivně spočetné množiny“). Podobně lze vyčíslitelné množiny slov v některé abecedě A zavést jako množiny výstupů Turingových strojů s externí abecedou A nebo jako množiny slov v abecedě A výstupů normálních algoritmů v abecedě A .

V teorii algoritmů je dokázáno tvrzení, že jako domény algoritmů mohou sloužit spočetné množiny a pouze spočetné množiny. To nám umožňuje zavést další ekvivalentní způsob definování pojmu spočetné množiny. Za vyčíslitelné množiny přirozených čísel lze tedy považovat rozsahy rekurzivních funkcí, množiny slov - oblasti použitelnosti Turingových strojů nebo normálních algoritmů s odpovídajícími abecedami.

Příklady

• Prázdná množina je vyčíslitelná.
• Jakákoli rozhodnoutelná množina (zejména jakákoli konečná množina ) je spočetná.
• Soubor čísel Turingových strojů zastavujících se na prázdném vstupu je také vyčíslitelný (ačkoli nelze rozhodnout , protože jeho doplněk je nevyčíslitelný).
• Projekce spočetné množiny je spočetná.
• Spočetné je i sjednocení a průnik konečného počtu spočetných množin.
• Množina přirozených čísel, jejichž desítkový zápis se vyskytuje jako podřetězec v desítkovém zápisu čísla π , je spočetná, a pokud je π normální , i triviálně řešitelná (celá množina přirozených čísel).
• Množina racionálních čísel menších než Khaitinova konstanta Ω je vyčíslitelná, ale nerozhodnutelná.
• Ale množina racionálních čísel větších než Khaitinova konstanta Ω je nevyčíslitelná (ačkoli je aritmeticky a korekurzivně spočetná).
• Množina prokazatelných tvrzení v aritmetice prvního řádu je početná.
• Ale množina pravdivých tvrzení v aritmetice prvního řádu není ani spočetná, ani korekurzivně spočítatelná (a není ani aritmetická, což představuje tvrzení Tarského věty o nevyjádřitelnosti pravdy v aritmetice).

Diophantine

Libovolná spočítatelná množina celých čísel (nebo n-tic celých čísel) má diofantinskou reprezentaci , to znamená, že je projekcí množiny všech řešení nějaké algebraické diofantické rovnice.

To konkrétně znamená, že jakákoliv vyčíslitelná množina se shoduje s množinou kladných hodnot nabraných pro celočíselné parametry nějakým polynomem s celočíselnými koeficienty. Tento výsledek stanovil Yuri Matiyasevich .

Viz také

• Imunitní sada

Poznámky

1. ↑ A. E. Pentus, M. R. Pentus, Matematická teorie formálních jazyků, Přednáška 14: Algoritmické problémy // Intuit.ru, 07/09/2007
2. ↑ Barwise, Kenneth John. Referenční kniha o matematické logice. Část 3: teorie rekurze. — M .: Nauka, 1982.

Literatura

• Rogers H. Teorie  rekurzivních funkcí a efektivní vyčíslitelnost : [přel. z  angličtiny. ] / ed. V. A. Uspenský: per. z angličtiny. V. A. Dushsky, M. I. Kanovich, E. Yu. Nogina. — M  .: Mir, 1972.