Ratkaistava setti

Ratkaistava joukko (myös rekursiivinen , laskettava ) on luonnollisten lukujen joukko , jolle on olemassa algoritmi , joka vastaanottaa minkä tahansa luonnollisen luvun syötteenä ja päättyy rajallisen määrän vaiheiden jälkeen määrittämällä kuuluuko se tähän joukkoon. Toisin sanoen joukko on päätettävissä, jos sen ominaisfunktio on laskettavissa . Joukkoa, joka ei ole liukeneva, kutsutaan ratkaisemattomaksi . Voidaan puhua myös ratkaistavasta joukosta, joka koostuu kaikista luonnollisilla luvuilla koodatuista konstruktivista objekteista . Mikä tahansa päätettävissä oleva joukko on numeroituva ja aritmeettinen . Ratkaisevat joukot vastaavat aritmeettisen hierarkian tasoa . ${\displaystyle \Delta _{1}^{0))$

Yleisessä tapauksessa konstruktiivisten elementtien joukon osajoukkoa kutsutaan määritettävissä olevaksi suhteessa , jos on olemassa algoritmi, jota voidaan soveltaa objekteihin, ja jos sitä sovelletaan johonkin objektiin , joka vastaa kysymykseen, kuuluuko tämä objekti [ 1] . ${\mathfrak {M}}_{1}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{2}$ ${\mathfrak {M}}_{1}$

On olemassa lukuisia joukkoja, jotka eivät ole päätettävissä. Lisäksi numeroitava joukko on päätettävissä, jos ja vain jos sen komplementti on myös numeroituva. Päätettävissä olevan joukon projektio on luettavissa, mutta ei välttämättä päätettävissä. Päätettävissä olevan joukon osajoukko ei välttämättä ole päätettävissä (eikä välttämättä edes aritmeettinen).

Kaikkien ratkaistavissa olevien osajoukkojen joukko on laskettava ja kaikkien ratkaisemattomien osajoukkojen joukko on laskematon , koska kaikkien positiivisten kokonaislukujen osajoukkojen joukko on laskematon. [2] $\mathbb {N}$ $\mathbb {N}$ $2^{P}$

Laskettavien osajoukkojen ja laskettavien reaalilukujen välillä on yksi yhteen vastaavuus [2] . $S\alajoukko P$ $x\in [0,1]$

Esimerkkejä

Tyhjä sarja on päätettävissä.
Mikä tahansa äärellinen joukko ja sen komplementti ovat ratkaistavissa olevia joukkoja.
On olemassa äärettömiä ratkaistavissa olevia joukkoja, joissa on ääretön komplementti. Esimerkiksi kaikkien parillisten lukujen joukko ja kaikkien alkulukujen joukko ovat ratkaistavissa.
Ratkaisevan joukon komplementti on päätettävissä.
Ratkaisevien joukkojen rajallisen määrän liitto ja leikkaus ovat myös ratkaistavissa.
Mikä tahansa numeroitava joukko, jonka komplementti on myös numeroituva, on ratkeava ( Postin lause ).
Joukko rationaalilukuja , jotka ovat pienempiä $\pi$ kuin , on ratkaistavissa.
Joukko, jonka ainoa alkio on yhtä suuri kuin yksi, jos Riemannin hypoteesi on tosi, ja muuten nolla, on päätettävissä (koska se on äärellinen).
ζ-funktion ei-triviaalien nollien lukujoukko , jonka osalta Riemmannin hypoteesi rikotaan , on päätettävissä (vaikkakaan ei tiedetä, onko se tyhjä, äärellinen vai ääretön).
Joukko merkkijonoja, jotka ovat kelvollisia todisteita ZFC :ssä, on päätettävissä. Sen projektio - ZFC:ssä todistettavissa olevien väitteiden joukko - on luettavissa, mutta sillä ehdolla, että ZFC on johdonmukainen , se on ratkaisematon.

Muistiinpanot

↑ Ebbinhouse, 1972 , s. 19.
↑ 1 2 Birkhoff G. , Barty T. Modern Applied Algebra. - M., Mir, 1976. - s. 375-376

Kirjallisuus

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turingin koneet ja rekursiiviset funktiot. - M .: Mir, 1972. - 262 s.