Posts sætning

Posts sætning er en sætning om beregningsteori om rekursivt talløse mængder.

Udtalelse af sætningen

Hvis en mængde og dets komplement i mængden af naturlige tal ℕ er rekursivt tællelige , så er mængderne og afgørelige . $M$ $\overline{M}$ $M$ $\overline{M}$

Bevis

Nødvendighed . Det kan antages at . Så der er også . Da det er løseligt, kan dets karakteristiske funktion beregnes. Overvej 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}}

Derefter - er et sæt af værdier , og derfor rekursivt optælling. Overvej på samme måde 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}}

Derefter - er et sæt af værdier , og derfor rekursivt optælling. ${\overline {M}}=\{g(0),g(1),...\}$ $g(x)$ $\overline{M}$

Tilstrækkelighed . Lad og vær rekursivt optælling. Det betyder, at der er henholdsvis rekursive værdisætfunktioner . Overvej følgende algoritme. Vi vil beregne sekventielt . Da enhver naturlig , eller , så i processen med beregning på et eller andet trin i det første tilfælde vil det blive fundet sådan , og i det andet tilfælde - . I det første tilfælde og i det andet - . Så det er beregneligt, så det kan bestemmes. $M$ $\overline{M}$ $f(x),g(x)$ $M,{\overline {M}}$ $f(0),g(0),f(1),g(1),....$ $x\i M$ $x\ikke \in M$ $k$ $f(k)=x$ $g(k)=x$ $\chi _{M}(x)=1$ $\chi _{M}(x)=0$ $\chi _{M}(x)$ $M$

Konsekvens

Hvis et rekursivt optalbart, men ikke afgørligt sæt, så et ikke-rekursivt optalbart sæt. $M$ $\overline{M}$

Litteratur

Vereshchagin, Shen. Forelæsninger om matematisk logik og teori om algoritmer. — MTsNMO, 2002.
Igoshin V.I. Matematisk logik og teori for algoritmer. - Akademiet, 2008.
Maltsev A.I. Algoritmer og rekursive funktioner. — M.: Nauka, Fizmatlit, 1986.

Posts sætning

Udtalelse af sætningen

Bevis

Konsekvens

Litteratur

Se også