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í 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
Funkce code : P -» N je injektivní a totálni. Důkaz:
Tvrzení
Funkce code : P -> N není surjektivnf.
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 (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 (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(O), (fU)0),... obvykle píšeme ....
Pro j = 1 píšeme jen <p0,   > • • •■
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
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
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 počítaná programem halt. Pak program confuse
begin
while halt(x^) = 1 do begin end;
x-| := 1
end
počítá funkci
' JL jestliže f{i) = 1
1 jestliže f(i) = 0
Nechí e je index programu confuse. Pak
_L
1
IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci ff/26
diagonalizační metoda
	0	1	2	...  n ...
Po	t	l	i	t • • •      i      • • •
P^	t		t	• • •     ->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 <t>: 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í
■ 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 <t>
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 <t> 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
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
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 ^ begin
x2 := 0; x3 := 0;
while t(x2,0) < x1 do x2 \= x2 + 1;
while r(x2, x3) ^ X| do begin x2 .= x2 - 1; x3 ■= x3 + 1 end,
*\ := *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 \-> N následně:
ti(/i) = /'1
r/f (/!,..., //c) = rfa.-! (/'1,...,      ), /*) prok>\
Tyto funkce nazýváme standardní kódovací funkce. Odpovídající projekce ^ : N ^ N jsou pro všechna 1 < / < k definovány takto:
>1
Kkk(jk(h , • • • , ik))
'k
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í A77 je počet proměnných potřebný k výpočtu r
■ programy počítající 71-1 , tt2 vystačí s m + 3 proměnnými
■ 7Tki lze počítat pomocí 7í-i , 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 i-» N taková, že m m(J) _ JJ)
m a program Pshort{e) používá nejvýše j + r proměnných
Důkaz: Nechi program Pe používá proměnné x^,..., xk. Program
Pshort(é)
■ 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 <t>
■ 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
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
begin
E := Short(xi);       := x2;  x2 : = x3;   ... Xy := Xy+1;  Xy+1 := 0; L/ST := quad{E); LBL := 1;
M/4X := max{LIST); while LfíL ^ M/AX do begin
/A/S7 := fetch{LIST, LBL);
BLN := 0;
if /A/S7" = coc/eí^ := 0) then ^ := 0;
N^'+1 -> N:
if INST if /A/ST if /A/ST if INST if /A/S7"
code(xk code(x-\ code(x-\ code(x-\ code(x-\
0) then xk ■= 0; xi + 1) then xi := xi — 1) then xi := x2 + 1) then xi := x2 — 1) then xi :=
X! + 1; x-i - 1; x2 + 1; x2 - 1;
if INST = code(xk := xk + 1) then x^ := x^ + 1; if INST = code(xk := x^ — 1) then x^ := x^ — 1; if /A/S7" = code(xi ^ x2) A x-\ ^ x2 then BZ.A/ := 1; if INST = code(xi ^ x3) A ^ ^x3 then ß/_A/ := 1;
end
if /A/ST = code{xk_i ^ xk) A x/c_1 ^ xk then ßLA/ Z_ß/_ := next{LIST, LBL, BLN);
:= 1
end
IB107 Vyčíslitelnost a složitost: standardní numerace, problém zastavení, věta o numeraci
26/26