TIN064 Vlastnosti RSM

Wiki-skripta pro Vyčíslitelnost I
Obsah
Úvod (náhled do problematiky) Prerekvizity (co je dobré vědět předem) ČRF, ORF, PRF Rekurzivní spočetnost Převeditelnost RSM Generování RSM Imunní a simple množiny Věty o rekurzi Produktivní a kreativní množiny Neoddělitelné množiny Gödelova věta Seznam zkratek

Tato část je neúplná a potřebuje rozšířit. 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) = $ 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.