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/11
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 cpi = e} c A
■ nechí 9 je nějaká vyč. funkce splňující {/ | <p/ = 9} c A
■ nechí ř(/) je tot. vyčíslitelná funkce vracející kód programu
begin x2 := <t>(/, /); x1 := 0(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/11
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/11
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/11
1. Riceova věta pro relace
Definice (respektovaní funkcí relacemi)
Množina R c Nk respektuje funkce, jestliže (ai,..., a^) e R a ¥>a! =<Pk> ■■■> <Pak = y>bk implikuje(bi,...,bk) e R.
■ {UJ) I ¥>/ = <Pj]
m WJ,k)\<pi{3) + <pj{4) = <pk{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/11
2. Riceova věta
Necht A c N respektuje funkce a nechí existují vyčíslitelné funkce 6,6': N -> N řa/cové, ze 6> < 0' a dáte;
■ {/1 w = #} c ,4
■ {/1 <pi = 9'}cA Pak A není r.e.
■ £ je vyčíslitelná (příklad 2.10 ze cvičení)
■ existuje TVF f splňující £(/,/) = <Pf(i)(j) (translační lemma)
■ pak f {i) e A        i e 7Č, tedy 7Č = ř"1 (/i)
■ vzor r.e. množiny při TVF f je r.e. množina
Důkaz:
je-li ipj(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/11
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 {/1 ^,(x) = 1 pro všechna x}.
IB107 Vyčíslitelnost a složitost: Riceovy věty
8/11
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í:
■ {/ \ cpj = 0} Q A
■ {/1 <fi < 0 a dom((pj) je konečná množina} c /A Pa/c/A není r.e.
Důkaz:
JL
jestliže Pj zastaví na / během j kroků
9{j) jinak
■ ii je vyčíslitelná
■ existuje TVF f splňující //(/,/) = ^f(/)(y) (translační lemma) m i e K = 0 ==> /(/) e >A
m i e K =4> dom(<pf(j)) a ^^/) < (9 ==>      e ^
■ celkem / e ~K ^> f(i) e A, tedy K = ř_1 (/A) ...
IB107 Vyčíslitelnost a složitost: Riceovy věty
9/11
použití 3. Riceovy věty
C = {/ | 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/11