IB107 Vyčíslitelnost a složitost
Riceovy věty, redukce
Jan Strejček
Fakulta informatiky Masarykova univerzita
respektování funkcí
Definice 9.2 (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, redukce
2/20
1. Riceova věta
Věta 9.1 (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í 0 je nějaká vyčíslitelná funkce splňující {/ \ <pj = 0} q A
■ nechí f(i) je totálně vyčíslitelná funkce vracející kód programu
begin x2 := <t>(/, /); *i := 0(x1) end
■ tedy     e A       i e K a tudíž /C je rekurzivní (spor) ■
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce 3/20
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, redukce
4/20
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.
Není rozhodnutelné, zda jsou dvě vyčíslitelné funkce identické (nebo dva algoritmy/while-programy sémanticky ekvivalentní).
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
5/20
1. Riceova věta pro relace
Definice 9.6 (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 9.7 (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, redukce
6/20
2. Riceova věta
Necht A c N respektuje funkce a nechi existují vyčíslitelné funkce 0,0': N —>► N takové, že6<9f a dále:
■ {/1 <pj = 0} c A
■ {/1 ^ = 9'} CA
Pak A není r.e.
Důkaz:
je-li (pj(i) definováno jinak
■ £ je vyčíslitelná (příklad 2.10 ze cvičení)
■ existuje TVF / splňující £(/,/) = (translační lemma)
■ pak f (i) e A        / e 7Č, tedy 7Č = r1 (4)
■ vzor r.e. množiny při TVF ř je r.e. množina
■ ovšem /C není r.e. a proto ani /A není r.e.
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
7/20
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, redukce
8/20
3. Riceova věta
Věta 9.11 (3. Riceova věta)
Necht A c N respektuje funkce a necht existuje vyčíslitelná funkce 9 : N    N splňující:
■ {/1    = 9} c A
■ {/1 <fi < 0 a dom((fj) je konečná množina} c A Pak A není r.e.
Důkaz:
_L
jestliže Pj zastaví na / během j kroků
0{j) jinak
li je vyčíslitelná
existuje TVF f splňující //(/,/) = ^f(/)(y) (translační lemma)
i E~K   =4>   ^(/) = 0   =^ g /4
/ g /C =4> dom((pf(j)) je konečná a <^(/) < 0 =4> g >A celkem / g /C <=:
g A tedy /C = ŕ"1 (4)
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
9/20
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, redukce
10/20
intuice pro redukci
A = {ne N | nje dělitelné 13} B= {n e N | nje dělitelné 26}
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
11/20
intuice pro redukci
K = {/' e N | </?/(/) je definováno} B= {n e N | nje dělitelné 26}
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
12/20
redukce
Definice 10.1 (m-redukce, m-ekvivalence)
Necht A, B c N. Řekneme, že A se m-redukuje na B, píšeme A<m B, právě když existuje totálně vyčíslitelná funkce f: N -> N taková, že
x e A f(x) e 6.
Funkci f nazveme redukcí A na B.
AaB jsou m-ekvivalentní, psáno A =m B, pokud A <m B a B <m A.
Platí A <m B =>► >4 <m B.
Platí /l<m6a6<fflC        A <m C (tj. <„, je tranzitivní).
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce 13/20
příklad redukce
K = {/' | (f,(i) je definováno}
j={/1^(0 = 1}
K <m J:
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
14/20
příklad redukce
K = {/' | ipj(i) je definováno} J={i\ W(/) = 1}
J<m K:
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
15/20
redukce a rozhodnutelnost
Věta 10.3
NechíA <m B. O B je rekurzivní =4> A je rekurzivní B B je rekurzivně spočetná =4> A je rekurzivně spočetná
Důkaz: A <m B, tedy existuje totálně vyčíslitelná funkce f splňující
x e A       f(x) e B □ B je rekurzivní, tedy \b je totálně vyčíslitelná
B B je r.e., tedy B = dom(g) pro nějakou vyčíslitelnou funkci g
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
16/20
redukce a rozhodnutelnost
Důsledek 10.4
NechtA <m B. O A není rekurzivní =4> B není rekurzivní Q A není rekurzivně spočetná =4> B není rekurzivně spočetná
Důsledek
NechíA=m B. O /A ye rekurzivní <^> 6 ye rekurzivní B >A ye rekurzivně spočetná <=^> 6 ye rekurzivně spočetná
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
17/20
typické aplikace
■ důkaz (částečné) rozhodnutelnosti A
■ důkaz nerozhodnutelnosti B
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
18/20
r.e. množiny a K
Věta 10.5
Je-li A c N rekurzivně spočetná, pak A <m K.
Důkaz: Nechí g je vyčíslitelná funkce splňující A = dom(g)
begin
y := #(>);
x-| := 1
end
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
19/20
těžká a úplná množina
Definice 10.6 (těžká a úplná množina)
Necht C je třída podmnožin množiny N a A c N. Řekneme, že A je C-těžká, právě když pro každou množinu B e C platí B <m A. Je-li navíc AeC, pak A nazýváme C-úplná nebo úplná ve třídě C.
Věta 10.7
Množina K je úplná ve třídě všech rekurzivně spočetných množin.
IB107 Vyčíslitelnost a složitost: Riceovy věty, redukce
20/20