Teorema lui Post

Teorema lui Post este o teoremă a teoriei computabilității despre mulțimile enumerabile recursiv.

Enunțul teoremei

Dacă o mulțime și complementul ei din mulțimea numerelor naturale ℕ sunt enumerabile recursiv , atunci mulțimile și sunt decidabile . $M$ $\overline{M}$ $M$ $\overline{M}$

Dovada

Necesitatea . Se poate presupune că . Deci există și . Deoarece este rezolvabil, funcția sa caracteristică este calculabilă. Luați în considerare funcția : $M\neq \varnothing$ $a\in M$ $b\nu \în 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{cazuri}}

Atunci - este un set de valori , deci enumerabile recursiv. În mod similar, luați în considerare funcția : $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{cazuri}}

Atunci - este un set de valori , deci enumerabile recursiv. ${\overline {M}}=\{g(0),g(1),....\}$ $g(x)$ $\overline{M}$

Suficiență . Fie și să fie enumerabile recursiv. Aceasta înseamnă că există funcții recursive de set de valori , respectiv. Luați în considerare următorul algoritm. Vom calcula secvenţial . Deoarece orice natural , sau , atunci în procesul de calcul la un pas în primul caz se va găsi astfel încât , iar în al doilea caz - . În primul caz , iar în al doilea - . Deci este calculabil, deci este decidebil. $M$ $\overline{M}$ $f(x),g(x)$ $M,{\overline {M}}$ $f(0),g(0),f(1),g(1),....$ $x\în M$ $x\nu \în M$ $k$ $f(k)=x$ $g(k)=x$ $\chi _{M}(x)=1$ $\chi _{M}(x)=0$ $\chi _{M}(x)$ $M$

Consecință

Dacă o mulțime enumerabilă recursiv, dar nu decidabilă, atunci o mulțime enumerabilă nerecursiv. $M$ $\overline{M}$

Literatură

Vereșchagin, Shen. Prelegeri despre logica matematica si teoria algoritmilor. — MTsNMO, 2002.
Igoshin V.I. Logica matematică și teoria algoritmilor. — Academia, 2008.
Maltsev A.I. Algoritmi și funcții recursive. — M.: Nauka, Fizmatlit, 1986.

Teorema lui Post

Enunțul teoremei

Dovada

Consecință

Literatură

Vezi și