IB107 Vyčíslitelnost a složitost
Riceovy věty
Jan Strejček
Fakulta informatiky Masarykova univerzita
respektování funkcí
Definice (respektování funkcí)
Množina A c N respektuje funkce, jestliže platí
i e A a ifj = ifj   =4>  j g A.
■ A respektuje funkce, právě když A respektuje funkce
■ 0, N
■ konečná neprázdná množina A c N
■ {/1 (f i je prostá}
■ {/ | Wi = {42}}
IB107 Vyčíslitelnost a složitost: Riceovy věty
2/10
1. Riceova věta
Věta (1. Riceova věta)
Neprázdná vlastní podmnožina N (tedy A splňující® ^ A c N), která respektuje funkce, není rekurzivní.
Důkaz: (sporem)
■ předpokládejme, že A je rekurzivní
■ nechí e je prázdná funkce (dom(e) = 0) a {/1 ^, = e} c A
■ nechí 6 je nějaká vyč. funkce splňující {/ | <pj = 9} c A
■ nechí f{i) je tot. vyčíslitelná funkce vracející kód programu
begin x2 := <t>(i\ /); x1 := 6>(x1) end
■ tedy f{í) e A       i e K a tudíž /c je rekurzivní (spor) ■
IB107 Vyčíslitelnost a složitost: Riceovy věty 3/10
použití 1. Riceovy věty
A = {/ | Lpi je prostá} není rekurzivní
Existují nerekurzivní množiny, které nerespektují funkce. (Jejich nerekurzivita není důsledkem 1. Riceovy věty.)
IB107 Vyčíslitelnost a složitost: Riceovy věty
4/10
důsledky 1. Riceovy věty
Množina všech indexů programů s daným vstupně-výstupním chováním, která není rovna 0 nebo N, není rekurzivní.
Není rozhodnutelné, zda má funkce cpj danou netriviální vlastnost, která není závislá na jejím indexu.
IB107 Vyčíslitelnost a složitost: Riceovy věty
5/10
1. Riceova věta pro relace
Definice (respektovaní funkcí relacemi)
Množina R c Nk respektuje funkce, jestliže (a,-,..., a^) e R a Vai = <Pb, ■ ■ ■ > ^ak = Vbk implikuje(bi,...,bk) e R.
■ {(',/) I ¥>/ = ¥>;}
■ {(/,y,/c)|w(3) + ^(4) = ^(5)}
Věta (1. Riceova věta pro relace)
Necht R c Nk respektuje funkce. Pak R je rekurzivní, právě když R = 0 nebo R = Nk.
IB107 Vyčíslitelnost a složitost: Riceovy věty
6/10
2. Riceova věta
Nechí A c N respektuje funkce a nechí existují vyčíslitelné funkce 0,0': N —>► N takové, že 0 < 0' a dále:
■ {/1 w = 9ř} c A
Pak A není r.e.
■ £ je vyčíslitelná (příklad 2.10 ze cvičení)
■ existuje TVF f splňující £(/,/) = ^f(/)(y) (translační lemma)
■ pak f (i) e A ^ / e 7Č, tedy 7Č = f~A (A)
■ vzor r.e. množiny při TVF f je r.e. množina
Důkaz:
je-li cpj(i) definováno jinak
■ ovšem K není r.e. a proto ani A není r.e.
IB107 Vyčíslitelnost a složitost: Riceovy věty
7/10
použití 2. Riceovy věty
B = {/1 cpj není totální} není r.e.
Existují množiny, které nejsou r.e. a nelze to dokázat
2. Riceovou větou. Například {/ | ^,(x) = 1 pro všechna x}.
IB107 Vyčíslitelnost a složitost: Riceovy věty
8/10
3. Riceova věta
Věta (3. Riceova věta)
Necht A c N respektuje funkce a necht existuje vyčíslitelná funkce 9 : N -> N splňující:
■ {/1 w = #} c >A
■ {/1 <pí < 0 a dom((fj) je konečná množina} c /A Pa/c/A není r.e.
Důkaz:
_L    jestliže P/ zastaví na / během j kroků 0(/) jinak
■ ji je vyčíslitelná
■ existuje TVF f splňující /í(/j) = (translační lemma) m i e K => ^(/) = 0 ==>       e /A
m i e K =4> dom{iff(j)) a      < 0 =4>      e ^
■ celkem i eK ^ f{i) e A tedy 7Č = ř~1 (A) ... ■
IB107 Vyčíslitelnost a složitost: Riceovy věty 9/10
použití 3. Riceovy věty
C = {/1 cpi = f}, kde f je pevně zvolená totálně vyčíslitelná funkce, není r.e.
Množina všech indexů programů s daným nekonečným vstupně-výstupním chováním není rekurzivně spočetná.
Existují množiny, které nejsou r.e. a nelze to o nich dokázat Riceovými větami.
IB107 Vyčíslitelnost a složitost: Riceovy věty
10/10