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 5.1 (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í V® (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é definujeme funkci code : P -> N pro všechna /,/, m > 1 a libovolné příkazy S, 8^, 52, • • • code{x, := 0 code(Xj := xy - 1 code(Xj := xy + 1 coc/e(while x, ^ XjdoS codei beg i n ^; 52; ... 5m end coder beg i n end _ o/ 2j 7''1V 13/17^19C0*W 23C0de(5i)29C0de((52)! # # (p8+A7?)coafe^m) 1 kde P, je Me 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; • • • ^ end codei beg in end 2' 3y5/ 7''1V 13M7^'l9coafeW 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 5.3 Funkce code : P N je 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; *2 := *1 + 1; while x1 ^ x2 do begin end end Definice 5.4 (standardní numerace programů) Standardní (kanonická) numerace programů je funkce nu m :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 5.5 (standardní numerace vyčíslitelných funkcí) Necht 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 = ^(/). Místo ¥>W(0),^(/)(1)?... obvykle píšeme v^,^,.... Pro j = 1 píšeme jen • • •■ Vyčíslitelných y-árních funkcí je pouze spočetně mnoho. Všech vyčíslitelných funkcí je pouze spočetně mnoho. IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 8/26 počet indexů funkce Lemma 5.6 Každá vyčíslitelná funkce má nekonečně mnoho různých indexů. Důkaz: IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci problém zastavení ■ existují funkce, které nejsou vyčíslitelné ■ neexistuje algoritmus rozhodující, zda daný program na svém indexu zastaví Věta 5.7 Funkce ř:N^N definovaná vztahem ( 1 jestliže (fj(i) je definováno f {i) = { { 0 jestliže cpj(i) není definováno není vyčíslitelná. IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 10/26 důkaz nerozhodnutelnosti problému zastavení '(0 = 1 jestliže (fj(i) je definováno 0 jestliže (fi(i) není definováno Důkaz: (sporem) Nechí f je vyčíslitelná funkce. Pak program confuse begin while ř(xi) = 1 do begin end; x-| := 1 end počítá funkci ' _L jestliže f{i) = 1 1 jestliže f(i) = 0 Nechí e je index programu confuse. Pak ^(e) = 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 5.10 (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). ■ O nazýváme univerzální funkce pro standardní numeraci y-árních vyčíslitelných funkcí ■ numerace s vyčíslitelnou univerzální funkcí někdy nazýváme efektivní numerace ■ 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 D ze vstupu (e, a-i,..., ay) dekóduj program Pe B 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 5.12 (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 5.13 Funkce r : N2 ^ N definovaná vztahem c m\ (/+y)(/+y + 1) • ^(>j) = -—-^y1—- + / 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 projekce Lemma 5.14 Funkce 7ri \N \-+N \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 7ri begin x2 := 0; x3 := 0; while t(x2, 0) < x1 do x2 \= x2 + 1; while r(x2, *3) ^1 do begin x2 \= x2 - 1; x3 = x3 + 1 end; *1 := *2 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 h> N následně: t\ (h) = h Tk{h ,•••,//() = r(Tk_i ,..., k_i), ik) prok>\ Tyto funkce nazýváme standardní kódovací funkce. Odpovídající projekce nki: N i-> N ysou pro všechna 1 < / < /< definovány takto: Kk-\{Tk(h, •■■Jk)) Ik IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 18/26 počítání projekcí Lemma 5.16 Existuje pevné číslo n takové, že pro každé k,l 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í A77 je počet proměnných potřebný k výpočtu r ■ programy počítající 71-1 , tt2 vystačí s m + 5 proměnnými ■ 7Tki lze počítat pomocí 7í-i , 7r2 7Tfc1(0 = Trf-1 (#) ^ki(i) = '(')) 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 5.18 Ke každému j > 1 existuje číslo r a totálně vyčíslitelná funkce short :N^N taková, ž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:= r(x1,x2); U:=r(U,Xj); U:=t(U,0); ) } (fr-y)-krát U:=t(U,0); J modifikace programu Pe xA :=ttm{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 := irkl(U); V := V + W:=7rk^U); W:=r(W,7rk2(U)); W:=r(W,nk3(U)); Xj := x, + 1 : ■ W:=t(W,V); II V místo irki(U) ■ ■ ■ W := t(W,7tkk(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 1/:=7ta/(10; while V ^ W do begin while Xj j^xidoS modifikovaná verze 5; 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 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 X| ^ xd do := Xi + 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 5.19 Existuje totálně vyčíslitelná funkce quad :N^N taková, že quad(e) je kód posloupnosti čtveřic reprezentující program Pe. Nechí 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 0 : Ny+1 -> N: begin E := short(x-\)\ x-i := x2; x2 := x3; . LIST := quad{E); LBL := 1; MAX := max{LIST); while LBL ^ MAX do begin INST := fetch{LIST, LBL); BLN := 0; if INST = code'(x^ ■= 0) then x<\ := 0; X; 7+1 - Ay'+1 := 0; if /A/ST if /A/sr if INST 11 /A/sr if /A/sr code' (xk code' code7 code' (xi code' 0) then xk := 0; *1 + 1) then x-| := x-| — 1) then xi := x2 + 1) then x-| := x2 — 1) then xi := X-, + 1; x-i - 1; x2 + 1; x2 - 1; if /A/sr if /A/sr if /A/sr if /A/sr = code7 (x/f := x^ + 1) then x^ := x^ + 1; = code' (xk := xk — 1) then x^ := x^ — 1; = code'(x-\ ^ x2) A x-| ^ x2 then SLA/ := 1; = code^x-i ^ x3) A x-| ^ x3 then BLN := 1; end end if /A/sr = cocfe/(x/(_1 ^ xk) A x/(_1 ^ xk then ßZ_A7 : LßZ. := next{LIST, LBL, BLN); : 1 IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci 26