Vyčísliteľnosť, Ľuboš Brim

Vyčísliteľnosť

Ľuboš Brim

numerácia programov

vlastnosti množín

riceova veta

relativizácia

• 1 Úvod
  1.1 Náš programovací jazyk . .
  1.2 Základní pojmy.......
  2 Efektivní numerace programů
  2.1 Standardní numerace ....
  2.2 Halting problém ......
  2.3 Věta o numeraci......
  2.4 Veta o parametrizaci ....
  2.5 Totální numerace......
  3 Nerozhodnutelné problémy
  3.1 Problém totálnosti.....
  3.2 Problém verifikace.....
  3.3 Problém ekvivalence ....
  4 Vyčislistelné vlastnosti množin
  4.1 Rekurzivní množinv ...............
  4.2 Rekurzivně vvčislitclnc množinv.........
  4.3 Další vlastnosti rekurzivně vvčislitclnvch množin
  5 Uzáverové vlastnosti RE-množin
  5.1 Uzávěry RE-množin..............
  5.2 Projekce a sekce ................
  6 Riceova věta
  6.1 Množiny respektující funkce..........
  6.2 Rcdukovatclnc množinv............
  6.3 Produktivní a kreativní množinv.......
  6.4 Imunní a jednoduché množiny.........
  6.5 Klasifikace problémů..............
  7 Relativizovaná teorie vyčíslitelnosti