IB107 Vyčíslitelnost a složitost rekurzivní a r.e. množiny, standardní numerace r.e. množin Jan Strejček Fakulta informatiky Masarykova univerzita rekurzivní množiny Definice (rekurzivní množina) Množina A c je rekurzivní, pokud existuje totálně vyčíslitelná funkce f: Nk -> N taková, že A = f-\{1}) = {(xu...,xk)eNk | ř(x1,...,x/f) = 1}. Funkce f se nazývá rozhodovací funkce pro A. ■ rekurzivní množině se také říká rozhodnutelná či řešitelná ■ příklady rekurzivních množin: IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 2/27 rekurzivní množiny Tvrzení A c Nk je rekurzivní, právě když je její charakteristická funkce Xa '■ ^k -> N definovaná vztahem 1 pokud (x1,..., xk) e A 0 jinak totálne vyčíslitelná. Důkaz: IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin vlastnosti rekurzivních množin Tvrzení Jestliže A c je konečná množina nebo Nk \ A je konečná, pak A je rekurzivní. Důkaz: IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 4/27 vlastnosti rekurzivních množin Lemma Nechí A, B c jsou rekurzivní množiny. Pak i množiny A, Au B a A n B jsou rekurzivní. Důkaz: IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 5/27 rekurzivně spočetné množiny Definice (rekurzivně spočetná množina) Množina B c N y e rekurzivně spočetná, právě když 6 = 0 nebo existuje totálně vyčíslitelná funkce f: N N taková, že B = range(f). Funkce f se nazývá numeru jícífunkce pro B. ■ rekurzivně spočetné množině se také říká částečně rozhodnutelná, rekurzivně vyčíslitelná nebo jen r.e. (z anglického recursively enumerable). ■ definici lze rozšířit na množiny Sc^ IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 6/27 vztahy rekurzivních a r.e. množin ^^^^^^^^^^^^^^^^ Každá rekurzivní množina AcNje také rekurzivně spočetná. Důkaz: IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin vztahy rekurzivních a r.e. množin Existuje množina Acn, která není rekurzivní. Existuje množina 6cn, která není r.e. Důkaz: (pomocí mohutnosti) Rekurzivních i r.e. množin je spočetně mnoho, ale N má nespočetně mnoho podmnožin. (diagonalizací) A = {/ e N | Lp,{i) ^ 1} B = {/ g N | / 0 range((fi)} IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin vztahy rekurzivních a r.e. množin Věta Množina A c N je rekurzivní, právě když A i A jsou r.e. Důkaz: =4> je-li A rekurzivní, pak je rekurzivní i A a každá rekurzivní množina je také r.e. <^= ■ je-li A = 0 nebo A = 0, pak A je rekurzivní ■ nechí A^Q) ^ A jsou r.e., pak A = range(f) aA = range(g) pro nějaké totálně vyčíslitelné funkce f, g : N N ■ platí range(f) n range(g) = 0 a range(f) u range(g) = N ■ charakteristickou funkci xa(x) počítáme takto: 1. počítáme /(O), gr(0), /(1), g(1),... dokud nedostaneme x 2. pokud x = /(a?) pro nějaké a?, pak vrátíme 1 3. pokud x = g{rí) pro nějaké a?, pak vrátíme 0 ■ xa je vyčíslitelná, tedy A je rekurzivní IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 9/27 funkce Step counter Lemma Funkce Sc(x, y,z) = < ' 1 jestliže program Px zastaví pro vstup y během z kroků jinak je totálně vyčíslitelná. Důkaz: interpreter z důkazu věty o numeraci rozšíříme o počítání instrukcí IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 10/27 programy jako generátory ■ rozšíříme jazyk while-programů o příkaz output(Xj) Tvrzení Množina A je r.e., právě když existuje program P (bez vstupních proměnných), který pomocí instrukce output během svého (potenciálně nekonečného) běhu dá na výstup právě všechny prvky A. Důkaz: <^= ■ pokud program P na výstup nic nedá, pak A = 0 je r.e. ■ nechí program generuje množinu výstupů A ^ 0 ■ nechí a e A, pak A = range(f) pro y pokud P dá v x-tém kroku na výstup y a jinak ■ f je totálně vyčíslitelná IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 11/27 programy jako generátory ■ pro A = 0 zřejmé ■ nechí A = range(f) pro tot. vyčíslitelnou funkci f : N N ■ nechi f je počítána programem Pe ■ pak A je generována tímto programem begin n := 0; while true do begin x := 7Ti(/7); / := 7T2(a7); If Sc(e, x, y) = 1 then begin Pe(x); output^) end a? := a7+ 1; end end IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin množiny a problémy Problém rozhodnout, zda dané x má vlastnost V ztotožníme s množinou {x \ x má vlastnost V}. Příklad: problém, zda n je prvočíslo, ztotožníme s množinou {n e N | n je prvočíslo} Terminologie Nechí M je množina odpovídající danému problému. Tento problém je ■ rozhodnutelný, právě když M je rekurzivní, ■ částečně rozhodnutelný (semirozhodnutelný), právě když M je r.e. Problém, který není rozhodnutelný, se nazývá nerozhodnutelný. IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 13/27 problém zastavení Problém zastavení, tedy problém, zda program P, zastaví na vstupu /, ztotožníme s množinou K = {/ e N | P, zastaví nad vstupu /} = {/ e N j (fj(i) je definováno}. Dříve jsme dokázali, že charakteristická funkce í 1 jestliže (fj(i) je definováno I 0 jestliže (pj(i) není definováno není vyčíslitelná. Proto K není rekurzivní a tedy problém zastavení je nerozhodnutelný. IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 14/27 problém zastavení Věta Množina K = {/1 cpj(i) je definováno} je rekurzivně spočetná. Důkaz: Množina K je generována programem begin n := 0; while true do begin X := 7í-| (r?)j / := tt2(/7); jf Sc(x,x,y) = 1 then output(x); n := n+ 1; end end Proto problém zastavení je částečně rozhodnutelný. IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 15/27 problém zastavení Věta Množina K = {i \ cpj(i) = _L} není rekurzivně spočetná. Důkaz: ■ množina K je rekurzivně spočetná ■ pokud by K byla také rekurzivně spočetná, tak by K bylo rekurzivní, což není Shrnutí: IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin rekurzivně spočetné množiny v rostoucím pořádku Definice Množina Ac.Nje rekurzivně spočetná v rostoucím pořádku, právě když má rostoucí numerující funkci. Lemma Nekonečná množina Ac.Nje rekurzivní, právě když je rekurzivně spočetná v rostoucím pořádku. Důkaz: <^= ■ nechi A = range(f) pro rostoucí tot. vyčíslitelnou funkci f ■ xa je počítána programem begin n = 0; while f{rí) < do n •= n + 1; lf f{rí) = x^ then x\ := 1 else x\ := 0 end IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 17/27 rekurzivně spočetné množiny v rostoucím pořádku ■ A je nekonečná a rekurzivní, tedy xa je vyčíslitelná ■ A je generována v rostoucím pořádku programem begin n := 0; while true do begin If xa(n) = 1 then output(n)\ n := a7+ 1; end end ■ funkce /(/) vracející /-tý prvek z generovaného seznamu je totálně vyčíslitelná ■ přitom f je rostoucí a >A = range(f) ■ tedy >4 je rekurzivně spočetná v rostoucím pořádku IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin rekurzivně spočetné množiny v rostoucím pořádku Důsledek Každá nekonečná r.e. množina A má nekonečnou rekurzivní podmnožinu B. Důkaz: ■ nechí f je numerující funkce pro A ■ uvažme podmnožinu B c A, kterou generuje program beg i n n := 0; m : = 0; while tme do beg i n jf f (n) > m then beg i n m ■= f(n)\ output(m) end; n := a7+ 1; end end ■ B je nekonečná a generovaná v rostoucím pořádku ■ tedy B je r.e. v rostoucím pořádku a tudíž rekurzivní IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin alternativní charakterizace r.e. množin Věta Množina Ac.Nje rekurzivně spočetná, právě když A = dom(g) pro nějakou vyčíslitelnou funkci g : N -> N. Množina AQNje rekurzivně spočetná, právě když A = range(g) pro nějakou vyčíslitelnou funkci g : N —^ N. IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 20/27 alternativní charakterizace r.e. množin Důkaz: A je r.e. <=^> 3 vyčíslitelná funkce g tak, že A = dom(g) A = Q A 7^ 0 je r.e., pak A = range(f) pro tot. vyčíslitelnou funkci f IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 21/27 alternativní charakterizace r.e. množin A je r.e. <=^> 3 vyčíslitelná funkce g tak, že A = dom(g) <== ■ >4 = dom(g) = 0 ■ >4 = dom(g) ^ 0, pak nechí a0 e A IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 22/27 alternativní charakterizace r.e. množin A je r.e. 3 vyčíslitelná funkce g tak, že A = range(g) ■A=$ m A^$\e r.e., pak A = range(f) pro tot. vyčíslitelnou funkci f ■ položíme g = f 4= ■ A = range(g) = 0 ■ A = range(g) ± 0, pak nechf a0 e A IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin možné numerace r.e. množin dom(ipo), dom(ipi), dom(ip2),... range{(f0), range(^), range{^2), ■ ■ ■ Věta Existují totálně vyčíslitelné funkce f, g : n -»• n řa/cové, že pro všechna i e n p/ař/ vzřafry; Q dom{^i) = range{ {A c N I A je r.e.} definovanou vztahem W(i) = dom(ipi). Index r.e. množiny A c N je číslo i splňující A = !/!/(/) ■ místo 1/1/(0), 1/1/(1),... píšeme W0lWi,... ■ množinu W, lze chápat jako akceptovanou programem P,: program P, akceptuje hgN, jestliže P, zastaví pro vstup n IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 26/27 r.e. relace a standardní numerace r.e. relací Definice (rekurzivně spočetná relace) Relace A c Ny je rekurzivně spočetná (r.e.), právě když existuje vyčíslitelná funkce f: Ny N taková, že A = dom(f). Definice (standardní numerace r.e. relací) Standardní numeracíj-árních r.e. relací nazveme funkci WV) ■ N {A c N/1 A je r.e.} definovanou vztahem Index r.e. relace A c nW je číslo i splňující A = W^\i). Místo l/l/W(0), ),... píšeme l%(y), l/l/f,.... IB107 Vyčíslitelnost a složitost: rekurzivní a r.e. množiny, standardní numerace r.e. množin 27/27