IB107 Vyčíslitelnost a složitost
r.e. množiny a jejch standardní numerace
Jan Strejček
Fakulta informatiky Masarykova univerzita
rekurzivně spočetné množiny
Definice 7.1 (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á numeru jí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 Sc^
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
2/22
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: r.e. množiny a jejch standardní numerace
vztahy rekurzivních a r.e. množin
Věta 7.7
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 | Lp,{i) ^ 1}
B = {/ g N | / 0 range(ipj)}
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
vztahy rekurzivních a r.e. množin
Věta 7.8
Množina A c N je rekurzivní, právě když A i A jsou r.e. Důkaz:
=4> 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í
■ nechí 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 x/\M počítáme takto:
1. počítáme /(O), gr(0), /(1), g(1),... dokud nedostaneme x
2. pokud x = f(ri) 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: r.e. množiny a jejch standardní numerace
5/22
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 6/22
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
7/22
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
8/22
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
9/22
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
10/22
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
11/22
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
12/22
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 tme 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
15/22
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
16/22
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
17/22
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
19/22
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
21/22
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í numeracf j-árních r.e. relací nazveme funkci WW : n -> {A c n/ I A je r.e.} definovanou vztahem
Index r.e. relace A c W je číslo i splňující A = wV)(i). Místo IV(/)(o), 1/1/^(1),... píšeme WJj\ W®,....
IB107 Vyčíslitelnost a složitost: r.e. množiny a jejch standardní numerace
22/22