IB107 Vyčíslitelnost a složitost standardní numerace, problém zastavení, věta o numeraci Jan Strejček Fakulta informatiky Masarykova univerzita numerace množiny Definice (numerace množiny) Numerace množiny M je surjektivní funkce v : N -> M. Je-li v navíc totální, mluvíme o totální numeraci množiny. příklady ■ numerace množiny M = {a, b, c} ■ totální numerace množiny M = {a, b, c} IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 2/26 numerace množiny ■ numerace množiny {0,2,4,6,8,...} ■ numerace množin Z a Q ■ numerovat lze libovolnou nejvýše spočetnou množinu ■ chceme definovat totální numeraci y-árních vyčíslitelných funkcí (pro každé j > 1) IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 3/26 index programu ■ každému programu priradíme číslo z N ■ zvolíme techniku, kterou použil Kurt Godel ■ předpokládáme, že programy používají pouze proměnné X-| , X2,... ■ definujeme funkci code : P -> N pro všechna /,/, m > 1 a libovolné příkazy 8,8^, 52,... cocře(x/ := 0) = 2' code(Xj := xy- - 1) = 3'íy code(Xj := xy + 1) = 7'11y cocfeíwhile x,- ^ xy do 5) = 13'17h 9code^ codeíbeam 8Vl82\ ...8m end) = 23code^)29code(^). . . (pQ+myode(ôm) coďe( beg i n end) = 1 kde p, je Mé prvočíslo, přičemž první prvočíslo je 2 ■ code(P) nazýváme index programu P IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 4/26 příklad code(Xj := 0 code(Xj := Xj: - 1 code(Xj := xy + 1 cootefwhile x, ^ xy do S cootefbegin ; <52; ... 5m end codei beg in end 2' 3y5/ 7''1V 13M7^19coafe^ 1 ^empty- COdo(Pempty) — begin x^ := 0; x2 := x1 + 1; while x1 7^ x2 do begin end end IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 5/26 vlastnosti funkce code Lemma Funkce code : P N ye injektivní a totální. Důkaz: Tvrzení Funkce code : P -> N není surjektivní Důkaz: např. číslo 12 není indexem žádného programu. IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci standardní numerace programů Pempty- begin x^ := 0; x2 := x1 + 1; while x1 ^ x2 do begin end end Definice (standardní numerace programů) Standardní (kanonická) numerace programů je funkce num :N^P definovaná takto: code 1 (n) jestliže n e range(code) num(ri) = empty jinak Namísto num(0), num^),... obvykle píšeme P0, Pí, IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 7/26 standardní numerace vyčíslitelných funkcí Definice (standardní numerace vyčíslitelných funkcí) Nechí j > 1. Standardní (kanonická) numerace j-árních vyčíslitelných funkcí je funkce cpW : N ^ definovaná takto. v vy r'num(i) Index vyčíslitelné funkce f e je číslo i splňující f = ^\i). Místo ^(0), (fU)0),... obvykle píšeme j^ • • • Pz ■ ■ i ■ ■ • • • ->j^ • • • ■ ■ ■ Pn ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ t ■ ■ ■ ■ ■ t • • • i • • • ■ ■ ■ confuse 1 t t IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 12/26 věta o numeraci Věta (věta o numeraci) Pro každé j > 1 existuje vyčíslitelná funkce : Ny+1 -> N taková, že pro všechna e, a-i,..., ay- e N platí 0(e, a1,...,ay) = ^y)(a1,...,ay). ■ 0 nazýváme univerzální funkce pro standardní numeraci y-árních vyčíslitelných funkcí ■ větě se také říká utm-věta (universal Turing machine) IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 13/26 poznámky k důkazu věty o numeraci intuitivní implementace univerzální funkce □ ze vstupu (e, a-i,..., ay) dekóduj program Pe H simuluj program Pe na vstupu (a-i,..., ay) B pokud simulovaný program Pe skončí, dej na výstup jeho výslednou hodnotu úskalí intuitivní implementace ■ simulovný program může obsahovat libovolně velký (konečný) počet proměnných ■ implementace má ale fixní počet proměnných -> kódování více proměnných do jedné IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 14/26 párující funkce Definice (párující funkce) Totálně vyčíslitelné bijekci f: N2 ^ N říkáme párující funkce. (0,0) (0,1) (0,2) (0,3) 0,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 15/26 párující funkce (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) Lemma Funkce r : N2 ^ N definovaná vztahem (- m\ (/+y)(/+y + 1) • t('>7) = ---- + i je párující funkce. Důkaz: r je bijekce (viz konstrukce) a totálně vyčíslitelná. ■ IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 16/26 projekce Lemma Funkce 7r-| :N^Na7í2:N^N definované jako ^(r{ij)) = i a 7r2{r{ij))=j jsou totálně vyčíslitelné funkce. Funkce nazýváme projekce. Důkaz: program pro 7r-| begin x2 := 0; x3 := 0; while t(x2, 0) < *1 do x2 \= x2 + 1; while t(x^xz) ^ x^ do begin x? = x2 - 1; x3 = x3 + 1 end; x! := x2 end IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 17/26 standardní kódovací funkce Pro všechna k > 1 definujeme funkce rk : Nk \-> N následně: ri(/i) = /i r/cí/i,..., /*) = rír/f.i (/'1,..., //c_i), /*) prok>\ Tyto funkce nazýváme standardní kódovací funkce. Odpovídající projekce tt^ : N h* N ysou pro všechna 1 < / < /c definovány takto: (r/c('l, • • • Á)) /1 ^kk(jk{h j • • • Á)) IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 18/26 počítání projekcí Lemma Existuje pevné číslo n takové, že pro každé kj eN splňující 1 < I < k je funkce 7rkí vyčíslitelná programem, který používá nejvýše n proměnných. Důkaz: ■ nechí m je počet proměnných potřebný k výpočtu r ■ programy počítající ^, tt2 vystačí s m + 3 proměnnými ■ 7Tki lze počítat pomocí ^, 7r2 7^(0 = Trf"1 (#) 7r/c/(0 = 7r2(7rf '(/')) pro / > 1 IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 19/26 počítání funkcí s omezeným počtem proměnných Lemma Ke každému j > 1 existuje číslo r a totálně vyčíslitelná funkce short :N^N taková, že ■ $ = víL(e) ■ a program PShort(e) používá nejvýše j + r proměnných Důkaz: Nechí program Pe používá proměnné x1,..., xk. Program Pshort{e) ■ zakóduje tyto proměně do proměnné U ■ simuluje program Pe s využitím projekcí ■ používá pouze ■ y vstupních proměnných ■ m proměnných pro výpočet r ■ n proměnných pro výpočet projekcí (viz předchozí lemma) ■ pomocné proměnné U, V, W IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 20/26 počítání funkcí s omezeným počtem proměnných program Ps/70rř(e) begin U := U := t(*i,x2); r(U,x3); U:=t(U,Xj); U:=t(U,0); ) } {k - y)-krát U:=t(U,0); J modifikace programu Pe XA :=7Tki(U) end IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 21/26 počítání funkcí s omezeným počtem proměnných modifikace programu Pe: begin V:=7rki(Uy, V:=V + V, W:=^{U); W:=r{W^k2{U)); W:=T(W,nk3(U)); x, := x, + 1 : W := t(W} V); II V místo 7rki{U) W:=T(W,nkk(U)); U:=W end IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 22/26 počítání funkcí s omezeným počtem proměnných modifikace programu Pe\ begin V:=7Tki(U)-W:=7rkl(Uy, while V ^ W do begin while Xj y^x/doS modifikovaná verze S; V:=7rki(Uyt W:=7Tk,(U) end end ■ program PShort(e) počítá tutéž y-arní funkci jako Pe ■ funkce short spočítá z indexu programu Pe index programu PShort(e)> tj- provede zde uvedenou konstrukci ■ IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 23/26 překlad programu na čtveřice další úskalí implementace univerzální funkce ■ není snadno patrné, v jakém pořadí instrukce vykonávat (Pokračovat další instrukcí nebo se vrátit k testu? Ke kterému testu?) ■ program proto převedeme na čtveřice (návěští, instrukce, návěští pro falše, návěští pro true) ■ konečné posloupnosti čtveřic lze kódovat přirozenými čísly beg i n while x1 ^ x? do (1, xi ^x2, 4, 2) (2, X! ^x4, 1, 3) while x1 ^ xd do Xi 1=^+1; x2 := x4 end (3, xi +1, 2, 2 (4, x2 := x4j 5, 5) IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 24/26 funkce pro práci se čveřicemi Lemma Existuje totálně vyčíslitelná funkce quad :N^N taková, že quad(e) je kód posloupnosti čtveřic reprezentující program Pe. Nechi LIST je kód posloupnosti čtveřic. Důkaz věty o numeraci používá i tyto totálně vyčíslitelné funkce: max(LIST) vrací nejvyšší návěští v LIST (tj. konec programu) fetch(LIST, LBL) najde v LIST čtveřici s návěštím LBL a vrátí kód odpovídající instrukce next{LIST, LBL, BLN) najde v LIST čtveřici s návěštím LBL a vrátí návěští pro falše pokud BLN = 0 nebo návěští pro true pokud BLN = 1 IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 25/26 důkaz věty o numeraci Důkaz: program počítající univerzální funkci O : Ny+1 -> N: begin E := short(Xj); := x2; X2 := x3; . . . > LIST := quad(E); LBL := 1; MAX := max{LIST); while LBL ^ MAX do begin INST := fetch{LIST, LBL); BLN := 0; if //VS7~ = code(xi := 0) then ^ := 0; 7 := 0; if//VS7~ if//VS7~ it INST tflNST if //VS7" code(xk code(Xj code(x<\ code(x^ code(x^ 0)\henxk ■= 0; x-| + 1) then x-| := x-i — 1) then x-i -x2 + 1) then x-| := x2 — 1) then x-| :: X-, + 1; *1 — 1; x2 + 1; x2 - 1; if /A/S7~ = code(xk ■= xk + 1) then x^ := + 1; jf //VS7~ = code(xk ■= xk — 1) then x^ := x/< — 1; if //VS7~ = coate^ ^ x2) AX! ^ x2 then BLN := 1; if INST = code(xi ^ x3) A x-\ ^ x3 then SLA/ := 1; if INST = code(xk_i ^ xk) A x/(_1 ^ x^ then ß/./V := 1; LBL := next{LIST, LBL, BLN); end end IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 26/26