Postin lause

Postin lause on laskettavuusteorian lause rekursiivisesti numeroitavista joukoista.

Lauseen lause

Jos joukko ja sen komplementti luonnollisten lukujen joukossa ℕ ovat rekursiivisesti numeroituvia , niin joukot ja ovat päätettävissä . $M$ $\overline{M}$ $M$ $\overline{M}$

Todiste

välttämättömyys . Voidaan olettaa, että . On siis myös . Koska se on ratkaistavissa, sen ominaisfunktio on laskettavissa. Harkitse toimintoa : $M\neq \varnothing$ $a\in M$ $b\not \in M$ $M$ ${\näyttötyyli \chi _{M}(x)}$ $f(x)$

f(x)={\begin{cases}x,{\text{ if }}\chi _{M}(x)=1\\a,{\text{ if }}\chi _{M }(x)=0\end{cases}}

Sitten - on joukko arvoja , joten se on rekursiivisesti luettavissa. Harkitse samalla toimintoa : ${\displaystyle M=\{f(0),f(1),....\))$ $f(x)$ $M$ $g(x)$

g(x)={\begin{cases}x,{\text{ if }}\chi _{M}(x)=0\\b,{\text{ if }}\chi _{M }(x)=1\loppu{tapaukset}}

Sitten - on joukko arvoja , joten se on rekursiivisesti luettavissa. ${\overline {M}}=\{g(0),g(1),....\}$ $g(x)$ $\overline{M}$

Riittävyys . Olkoon ja rekursiivisesti numeroituva. Tämä tarkoittaa, että on olemassa rekursiivisia arvojoukkofunktioita . Harkitse seuraavaa algoritmia. Laskemme peräkkäin . Koska mikä tahansa luonnollinen , tai , niin laskuprosessissa jossain vaiheessa ensimmäisessä tapauksessa havaitaan sellainen , että ja toisessa tapauksessa - . Ensimmäisessä tapauksessa ja toisessa - . Se on siis laskettavissa, joten se on päätettävissä. $M$ $\overline{M}$ $f(x),g(x)$ $M,{\overline {M}}$ ${\näyttötyyli f(0),g(0),f(1),g(1),....}$ $x\in M$ $x\not \in M$ $k$ $f(k)=x$ $g(k)=x$ $\chi _{M}(x)=1$ $\chi _{M}(x)=0$ ${\näyttötyyli \chi _{M}(x)}$ $M$

Seuraus

Jos rekursiivisesti numeroitava, mutta ei päätettävissä oleva joukko, niin ei-rekursiivisesti numeroitava joukko. $M$ $\overline{M}$

Kirjallisuus

Vereshchagin, Shen. Luentoja matemaattisesta logiikasta ja algoritmien teoriasta. – MTsNMO, 2002.
Igoshin V.I. Matemaattinen logiikka ja algoritmien teoria. – Akatemia, 2008.
Maltsev A.I. Algoritmit ja rekursiiviset funktiot. - M.: Nauka, Fizmatlit, 1986.

Postin lause

Lauseen lause

Todiste

Seuraus

Kirjallisuus

Katso myös