Postens sats

Posts sats är en sats om beräkningsbarhetsteori om rekursivt uppräknade mängder.

Uttalande av satsen

Om en mängd och dess komplement i mängden naturliga tal ℕ är rekursivt uppräknade , är mängderna och avgörbara . $M$ $\overline{M}$ $M$ $\overline{M}$

Bevis

Nödvändighet . Det kan antas att . Så det finns också . Eftersom det är lösbart är dess karakteristiska funktion beräkningsbar. Tänk på funktionen : $M\neq \varnothing$ $a\in M$ $b\not \in M$ $M$ $\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}}

Då - är en uppsättning värden , därför rekursivt uppräknad. På samma sätt, överväg funktionen : ${\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\end{cases}}

Då - är en uppsättning värden , därför rekursivt uppräknad. ${\overline {M}}=\{g(0),g(1),...\}$ $g(x)$ $\overline{M}$

Tillräcklighet . Låt och var rekursivt uppräknad. Det betyder att det finns rekursiva värdeuppsättningsfunktioner . Tänk på följande algoritm. Vi kommer att beräkna sekventiellt . Eftersom alla naturliga , eller , sedan i processen för beräkning i något steg i det första fallet kommer det att hittas så att , och i det andra fallet - . I det första fallet och i det andra - . Så det är beräkningsbart, så det är avgörbart. $M$ $\overline{M}$ $f(x),g(x)$ $M,{\overline {M}}$ $f(0),g(0),f(1),g(1),....$ $x\i M$ $x\not \in M$ $k$ $f(k)=x$ $g(k)=x$ $\chi _{M}(x)=1$ $\chi _{M}(x)=0$ $\chi _{M}(x)$ $M$

Konsekvens

Om en rekursivt uppräknbar men inte avgörbar uppsättning, då en icke-rekursivt uppräknbar uppsättning. $M$ $\overline{M}$

Litteratur

Vereshchagin, Shen. Föreläsningar om matematisk logik och teori om algoritmer. — MTsNMO, 2002.
Igoshin V.I. Matematisk logik och teori för algoritmer. — Akademin, 2008.
Maltsev A.I. Algoritmer och rekursiva funktioner. — M.: Nauka, Fizmatlit, 1986.

Postens sats

Uttalande av satsen

Bevis

Konsekvens

Litteratur

Se även