IB107 Vyčíslitelnost a složitost
r.e. množiny a jejch standardní numerace
Jan Strejček
Fakulta informatiky Masarykova univerzita
programy jako generátory
■ rozšíříme jazyk while-programů o příkaz output(Xj)
Tvrzení
Množina A c. N 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 množiny 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
■ / je totálně vyčíslitelná
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace 2/18
programy jako generátory
■ pro A = 0 zřejmé
■ nechí A = range(f) pro totálně 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 •= f(x)\ output^) end; n := a?+ 1;
end end
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
3/18
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 rozhodnout, zda n je prvočíslo, ztotožníme s množinou
{n e N | n je prvočíslo}
Definice ((částečně) rozhodnutelný a nerozhodnutelný problém)
Problém ztotožněný s množinou M je
■ rozhodnutelný, právě když M je rekurzivní,
■ nerozhodnutelný, právě když M není rekurzivní,
■ částečně rozhodnutelný neboli semirozhodnutelný, právě když M je re.
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
4/18
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 cp i (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á. Tedy K není rekurzivní a problém zastavení je nerozhodnutelný.
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
5/18
problém zastavení
Věta 7.10
Množina K = {i \ cpi(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?);
/ := tt2(/7);
|f 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: r.e. množiny a jejch standardní numerace
6/18
problém zastavení
Věta 7.11
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: r.e. množiny a jejch standardní numerace
rekurzivně spočetné množiny v rostoucím pořádku
Definice 7.12
Množina Ac.Nje rekurzivně spočetná v rostoucím pořádku, právě když má rostoucí numerující funkci.
Lemma 7.13
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álně vyčíslitelnou funkci f ■ xa je počítána programem
begin n = 0;
while f{rí) <    do n •= n + 1;
lf f{rí) =    then x\ := 1 else x\ := 0 end
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
8/18
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: r.e. množiny a jejch standardní numerace
rekurzivně spočetné množiny v rostoucím pořádku
Důsledek 7.14
Každá nekonečná r.e. množina A má nekonečnou rekurzivní podmnožinu B.
Důkaz:
■ nechi 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 true 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: r.e. množiny a jejch standardní numerace
alternativní charakterizace r.e. množin
Věta 7.15
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: r.e. množiny a jejch standardní numerace
11/18
alternativní charakterizace r.e. množin
Důkaz:
A je r.e. <=^> 3 vyčíslitelná funkce g tak, že A = dom(g)
A = (b
A 7^ 0 je r.e., pak A = range(f) pro totálně vyčíslitelnou funkci f
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
12/18
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: r.e. množiny a jejch standardní numerace
13/18
alternativní charakterizace r.e. množin
A je r.e.        3 vyčíslitelná funkce g tak, že A = range(g)
A = $
A ^ 0 je r.e., pak A = range{f) pro totálně vyčíslitelnou funkci f položíme g = f
A = range(g) = 0
A = range(g) ^ 0, pak nechf a0 e A
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
možné numerace r.e. množin
dom(ipo), dom(ipi), dom(ip2),... range{(f0), range(^), range{^2), ■ ■ ■
Věta 7.16
Existují totálně vyčíslitelné funkce f, g : N -»• N takové, že pro všechna i e N platí vztahy:
Q dom{^i) = range{<pf(i))
H range{ípi) = dom{(fg{i))
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
15/18
vr r
možne numerace r.e. množín
Důkaz:
dom(ipj) = range{ipm)
rangem,) = dom(<pg{i))
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
standardní numerace r.e. množin
Definice 7.17 (standardní numerace r.e. množin)
Standardní nu merací r.e. množin nazveme funkci W : N -> {A c N | 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 l/l/(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: r.e. množiny a jejch standardní numerace
17/18
r.e. relace a standardní numerace r.e. relací
Definice 7.19 (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-árnich r.e. relací nazveme funkci l/l/(y) : n    {i4 c ny" |   je r.e.} definovanou vztahem
|/|/0')(/) = dom((p]i]).
Index r.e. relace A c     je číslo i splňující A = W^{i).
Místo l/l/W(0), ... píšeme       w\j\ ....
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
18/18