{{Template:TIN064 Skripta}}
{{TODO|Jestli nekdo chce mit dve stranky zabyvajici se RSM tak at sem prehodi vlastnosti RSM ze strany Rekurzivni spocetnost}}

**Tato stránka je obsolete, obsah žije v [Převeditelnosti](TIN064%20Převeditelnost).**

*def: $W_x$ (x-tá rekurzivně spočetná množina) = $ dom( \varphi_x) = \{ y, \varphi_x(y) \mbox{je definována} \} $

* $\varphi_x $ je x-tá ČRF

*def: $K = \{x, x \in W_x\}$
**Jinými slovy $\{x, \varphi_x(x) \mbox{je definovana} \}$, tedy $\{x, \psi_1(x,x) \mbox{je definovana}\}$

**$\psi_1$ je univerzální funkce z Kleeneho věty
**množina $K$ souvisí s Halting problémem (viz definice rekurzivně spočetné množiny) – kdyby $K$ byla rek => by bylo možné díky tomu, že $K$ je 1-převeditelná na $K_0$ rozhodnout halting problém

*def: $K_0 = \{<y, x> |\ y \in W_x\}$

* $K_0$ je 1-úplná (důkaz převodem $K$ na $K_0$)

*věta: Množina $K$ je rekurzivně spočetná, ale není rekurzivní a její doplněk není rekurzivně spočetný
**důkaz: $K$ je rek. spočetná, jelikož je def. oborem $\psi_1(x)$, která je ČRF, doplněk není rekurzivně spočetný, důkaz sporem pomocí Cantorovy diagonální metody.