IB107 Vyčíslitelnost a složitost věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny Jan Strejček Fakulta informatiky Masarykova univerzita věta o parametrizaci ■ funkci lze definovat parametrizací, tj. zafixováním vybraných argumentů jiné funkce Věta (věta o parametrizaci, věta (Kleene)) Pro každá m^n^l existuje totálně vyčíslitelná funkce sm . ^A7?+i _^ tak0Vá} že pro všechna e, ,..., ym+n e N platí IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 2/31 důkaz věty o parametrizaci ^s-(e,yi,...,ym)(^+1 > ' ' ->ym+n) = Ve , • • • , Ym+n) Důkaz: funkce s™(e, yi,..., y™) vrací index programu begin *A77+1 := *1 i Pe end IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny využití věty o parametrizaci Existuje totálně vyčíslitelná funkce h : N2 N taková, že pro všechna /,/, x g N p/aŕŕ ;)(*)■ Důkaz: ■ definujme funkci ŕ: N3 -> N jako f (i j, x) = o (/, 4>(/\ x)) ■ ŕ je vyčíslitelná a nechí e je její index ■ věta o parametrizaci říká, že existuje tot. vyčíslitelná funkce s2 splňující ^s2(e?/-y)(x) = N existuje tot. vyčíslitelná funkce r : N ^ N taková, že pro všechna x, y e N p/aŕ/' ŕ(x,y) = v9r(x)(y). ■ nazývá se také neefektivní podoba věty o parametrizaci ■ lze zobecnit na vyšší počty argumentů Důkaz: ■ nechí e je index f ■ věta o parametrizaci říká, že existuje tot. vyčíslitelná funkce s] splňující y>si(e>x)(y) = y>e(x,y) = ř(x,y) ■ klademe r(x) = s] (e, x) a tudíž r je tot. vyčíslitelná ■ IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 5/31 využití translačního lemmatu ■ nechí i\): N -> S je (ne nutně totální) numerace podmnožiny unárních vyčíslitelných funkcí S c v, která splňuje větu o numeraci, tj. existuje vyčíslitelná funkce ^ : N2 N taková, že pro všechna x, y e N platí ■ dle translačního lemmatu pak existuje tot. vyčíslitelná funkce r splňující ii>(x,y) = 1 jsou ^\^>'^ totální numerace množiny . Pokud ý splňuje větu o n u m e raci a ípf větu o parametrizaci, pak ^ < ^/(y) pro každé j > 1. Důkaz: pro j = 1 ■ ý má vyčíslitelnou univerzální funkci d>^(/,x) = ^/(x) ■ translační lemma pro 1 jeipW totální numeraci množiny a (pW její standardní numeraci. Pak ý splňuje věty o numeraci a parametrizaci, právě když pro každé j > 1 platí ^(y) = ^\ Důkaz: =4> plyne z předchozí věty <== ukážeme, že íp splňuje větu o numeraci ■ pro každé j > 1 je univerzální funkce ^ : Ny+1 N pro ý definovaná jako vztahem ■ z ^ < cpW plyne existence tot. vyčíslitelné funkce r : N -» N splňující ^}y) = <^ ■ tedy je vyčíslitelná IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 10/31 vztahy ke standardní numeraci <== ukážeme, že í/j splňuje větu o parametrizaci ■ nechí m, n > 1 ■ z ^m+n) < (p(m+n) plyne existence tot. vyčíslitelné funkce r : N N splňující ^m+n) = ■ z ^ : N2 -> N definovaná jako není vyčíslitelná. Důkaz: diagonalizací ■ Důsledek Neexistuje přípustná totální numerace všech totálních vyčíslitelných funkcí. IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 13/31 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 = r\m) = {(xi,...,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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 14/31 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) g A 0 jinak totálne vyčíslitelná. Důkaz: IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 15/31 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 16/31 vlastnosti rekurzivních množin Lemma Nechí A, B c jsou rekurzivní množiny. Pak i množiny A, A u B a A n B jsou rekurzivní. Důkaz: IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 17/31 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á numerují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 B c Nk IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 18/31 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny vztahy rekurzivních a r.e. množin Existuje množina A c N, 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 |

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í ■ nechi 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 21/31 funkce Step counter Lemma Funkce 1 jestliže program Px zastaví pro vstup y Sc(x, y,z)=< během z kroků 0 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny programy jako generátory ■ rozšíříme jazyk while-programů o prí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. ■ nechi program generuje množinu výstupů A ^ 0 ■ nechi a e A, pak A = range(f) pro f(x) 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 23/31 programy jako generátory ■ pro A = 0 zřejmé ■ nechi 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 24/31 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řiklad: 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 25/31 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 26/31 problém zastavení ^^^^^^^^^ Množina K = {/ | 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 := 7r-| (r?); y :=tt2(a7); if 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 27/31 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 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í numeru jí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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 29/31 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(h) = 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 / je rekurzivně spočetná v rostoucím pořádku ■ IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 30/31 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 begin n := 0; m : = 0; while true do begin If f{n) > at? then begin 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: věta o parametrizaci, programovací systémy, rekurzivní a r.e. množiny 31/31