{{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.

*def: $W_x$ (x-tá rekurzivně spočetná množina) =

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 39: …, \varphi_x(y) \̲m̲b̲o̲x̲{je definována}…

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

*def: $K = \{x, x \in W_x\}$ **Jinými slovy

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 19: …, \varphi_x(x) \̲m̲b̲o̲x̲{je definovana}…

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 18: …x, \psi_1(x,x) \̲m̲b̲o̲x̲{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.