Luettelosarja

Numeroitava joukko ( tehokkaasti numeroitava , rekursiivisesti numeroitava , puoliratkettava joukko [1] ) on joukko konstruktiivisia objekteja (esimerkiksi luonnollisia lukuja ), joiden kaikki elementit voidaan saada jollain algoritmilla . Luettelojoukon komplementtia kutsutaan corecursively numerable [2] . Jokainen numeroitava joukko on aritmeettinen . Koekursiivisesti numeroitava joukko ei välttämättä ole numeroitavissa, mutta se on aina aritmeettinen. Luetteloidut vastaavat hierarkian

Jokainen ratkaistava joukko on luettavissa. Luettelojoukko on päätettävissä, jos ja vain jos sen komplementti on myös numeroituva. Toisin sanoen joukko on päätettävissä, jos ja vain jos se on sekä numeroitavissa että ydinkursiivisesti numeroitavissa. Numeroitavan joukon osajoukko ei välttämättä ole numeroitavissa (eikä välttämättä edes aritmeettinen).

Kaikkien numeroitavien osajoukkojen joukko on laskettava joukko , ja kaikkien ei-numeroitavien osajoukkojen joukko  on laskematon .

Määritelmän muunnelmia

Algoritmin käsitteen erilaiset formalisaatiot vastaavat numeroitavan joukon käsitteen erilaisia ​​muodollisia määritelmiä, jotka osoittautuvat vastaaviksi. Siten rekursiivisen funktion käsitteen perusteella luonnollisten lukujen numeroitavat joukot voidaan määritellä kuviksi yhden muuttujan osittain rekursiivisista funktioista (siksi luonnollisten lukujen numeroitavia joukkoja kutsutaan joskus "rekursiivisesti numeroitaviksi joukoiksi"). Vastaavasti joidenkin aakkosten A numeroitavia sanajoukkoja voidaan ottaa käyttöön Turingin koneiden tulosten sarjoina ulkoisella aakkosella A tai aakkoston A sanajoukkoina normaalien aakkoston A tulosteiden aakkosissa A.

Algoritmien teoriassa on todistettu väite, että numeroitavat joukot ja vain numeroitavat joukot voivat toimia algoritmien alueina. Tämän ansiosta voimme ottaa käyttöön toisen vastaavan tavan määritellä numeroitavan joukon käsite. Luetteloitavia luonnollisten lukujen joukkoja voidaan siis pitää rekursiivisten funktioiden alueina, sanajoukkoina - Turingin koneiden tai normaaleiden algoritmien sovellettavuusalueina vastaavilla aakkosilla.

Esimerkkejä

• Tyhjä joukko on luettavissa.
• Mikä tahansa päätettävissä oleva joukko (erityisesti mikä tahansa äärellinen joukko ) on numeroitu.
• Tyhjään syötteeseen pysähtyvien Turingin koneiden lukujoukko on myös numeroituva (vaikkakaan ei päätettävissä , koska sen komplementti on ei-numeroitava).
• Numeroitavan joukon projektio on numeroituva.
• Myös äärellisen numeroitavien joukkojen liitto ja leikkauspiste ovat numeroituvia.
• Luonnollisten lukujen joukko, jonka desimaaliluku esiintyy osamerkkijonona luvun π desimaalimuodossa , on numeroituva, ja jos π on normaali , jopa triviaalisti ratkaistavissa (koko luonnollisten lukujen joukko).
• Joukko rationaalilukuja, jotka ovat pienempiä kuin Khaitinin vakio Ω , on luettavissa, mutta ei päätettävissä.
• Mutta rationaalilukujen joukko, joka on suurempi kuin Khaitinin vakio Ω, ei ole numeroitavissa (vaikka se on aritmeettisesti ja corekursiivisesti numeroituva).
• Ensimmäisen asteen aritmetiikassa todistettavissa olevien lauseiden joukko on luettavissa.
• Mutta tosilauseiden joukko ensimmäisen asteen aritmetiikassa ei ole numeroitavissa eikä korkursiivisesti numeroitavissa (eikä ole edes aritmeettinen, mikä muodostaa Tarskin lauseen väitteen totuuden sanoittamattomuudesta aritmetiikassa).

Diophantine

Millä tahansa numeroitavalla kokonaislukujoukolla (tai kokonaislukujen monikoilla ) on diofantiiniesitys , eli se on projektio jonkin algebrallisen diofantiiniyhtälön kaikkien ratkaisujen joukosta.

Tämä tarkoittaa erityisesti sitä, että mikä tahansa numeroitava joukko osuu yhteen kokonaislukuparametreille jonkin polynomin kokonaislukukertoimilla ottaman positiivisten arvojen joukon kanssa. Tämän tuloksen loi Juri Matiyasevitš .

Katso myös

• Immuunijärjestelmä

Muistiinpanot

1. ↑ A. E. Pentus, M. R. Pentus, Formaalisten kielten matemaattinen teoria, Luento 14: Algoritmiset ongelmat // Intuit.ru, 07/09/2007
2. ↑ Barwise, Kenneth John. Matemaattisen logiikan hakuteos. Osa 3: Rekursioteoria. - M .: Nauka, 1982.

Kirjallisuus

• Rogers H. Rekursiivisten funktioiden teoria  ja tehokas laskettavuus : [käännös. englannista  . ] / toim. V. A. Uspensky: per. englannista. V. A. Dushsky, M. I. Kanovich, E. Yu. Nogina. - M  .: Mir, 1972.