IB107 Vyčíslitelnost a složitost
věta o parametrizaci, programovací systémy*,
rekurzivní a r.e. množiny
Jan Strejček
Fakulta informatiky Masarykova univerzita
věta o parametrizaci
■ funkci lze definovat parametrizací, tj. zafixováním vybraných argumentů jiné funkce
Věta 5.20 (věta o parametrizaci,    věta (Kleene))
Pro každá m^n^l existuje totálně vyčíslitelná funkce
sm . ^A7?+i _^   tak0Vá} že pro všechna e,   ,..., ym+n e N platí
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
2/22
důkaz věty o parametrizaci
^(e,y1r..,ym)(^+1' ' ' ^Ym+n) - <Pe      (/1, ■ ■ • > Ym+n)
Důkaz: funkce s™(e, yi,..., y™) vrací index programu begin
■
■
■
■
■
■
end
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
využití věty o parametrizaci
Lemma 5.21	
Existuje totálně vyčíslitelná funkce h :	N2    N taková, že pro
všechna /,/, x e N platí	
<Ph{ij){*) = (¥>/	
Důkaz:
■ definujme funkci ř: N3    N jako
f{ij, x) =     o <pj)(x) = <pí{<pj{x)) = 4>(/, 4>(/\ x))
■ ř je vyčíslitelná a nechí e je její index
■ věta o parametrizaci říká, že TVF sf splňující
^s?(e,/j)(x) = ^e(/J» =
■ klademe /)(/,/) = s2(e, /,/) a tudíž Ai je totálně vyčíslitelná
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
translační lemma
Důsledek 5.23 (translační lemma)
Ke každé vyčíslitené funkci f: N2 -> N existuje totálně vyčíslitelná funkce r:N^N taková, že pro všechna x, y e N platí
f{x,y) = <pr{x){y).
■ nazývá se také neefektivní podoba věty o parametrizaci
■ lze zobecnit na vyšší počty argumentů
Důkaz:
■ nechí e je index f
■ věta o parametrizaci říká, že existuje TVF s] splňující
Vst(e,x)(y) = (Pe(x,y) = f(x,y)
■ klademe r(x) = s] (e, x) a tudíž r je totálně vyčíslitelná
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
využití translačního lemmatu
■ nechí i\): N -> S je (ne nutně totální) numerace podmnožiny unárních vyčíslitelných funkcí S c v, která splňuje větu o numeraci, tj. existuje vyčíslitelná funkce <t>^ : N2 —^ N taková, že pro všechna x, y e N platí
■ dle translačního lemmatu pak existuje totálně vyčíslitelná funkce r splňující
<t>ii>(x,y) = <pr{x){y) = My)
■ tedy r převádí numeraci íp na standardní numeraci <p
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny 6/22
programovací systém/jazyk
■ while-programy nejsou jediným modelem algoritmů
■ ukážeme nezávislost teorie na volbě formalismu
Definice (programovací systém/jazyk)
Programovací systém (či jazyk) pro je dvojice C! = (T, Lp'), kde T je množina programů (syntaxe) acp* \ je sémantika
přiřazující každému programu j-ární vyčíslitelnou funkci.
■ jazyk while-programů:
■ můžeme předpokládat, že T = N
■ programovací jazyk by měl být
■ univerzální - existuje univerzální program
■ efektivní - programy lze jednoduše skládat
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
7/22
redukce a ekvivalence numerací
Definice 6.1 (redukce a ekvivalence numerací)
Numerace ty množiny M se redukuje na numerací ty' množiny M' (píšeme ty < ty'), právě když existuje totálně vyčíslitelná funkce r : N    N taková, že pro všechna i e dom(ty) platí
Numerace ty, ty' jsou ekvivalentní (píšeme ty = ty'), právě když ty < ty'a ty' < ty.
■ jsou-li ty, ty' dvě totální numerace množiny      pak ty < ty' znamená, že jazyk (N, ty) lze efektivně přeložit do jazyka (N, ty')
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
8/22
vztahy numerací
Věta 6.2
Necht pro každé j > 1 jsou ^\ ípf^ totální numerace množiny V^. Pokud íp splňuje větu o numeraci a ípř větu o parametrizaci, pak ýU) < ý'U) pro každé j > 1.
Důkaz: pro j = 1
■ íp má vyčíslitelnou univerzální funkci
0^(/,x) = ipj(x)
■ translační lemma pro <// říká, že existuje totální vyčíslitelná funkce r taková, že
= ^(/)(x)
tedy ^ <
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny 9/22
vztahy ke standardní numeraci
Věta 6.2 (pokračování)
Necht pro každé j > 1 je ýU) totální numeraci množiny V® a cpU) její standardní numeraci Pak ý splňuje věty o numeraci a parametrizaci, právě když pro každé j > 1 platí ^(y) = <pV\
Důkaz:
=4> plyne z předchozí věty
<== ukážeme, že íp splňuje větu o numeraci
■ pro každé j > 1 je univerzální funkce <t>^ : Ny+1    N pro ý definovaná vztahem
■ z     < cpW plyne existence totálně vyčíslitelné funkce r : N N splňující ^}y) = <^
■ tedy    je vyčíslitelná
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny 10/22
vztahy ke standardní numeraci
<== ukážeme, že íp splňuje vetu o parametrizaci
■ nechí m, n > 1
■ z ^m+n) < (p(m+n) plyne existence totálně vyčíslitelné funkce r : N    N splňující ^m+n) =
■ z      <      plyne existence totálně vyčíslitelné funkce
S : N    N splňující (f^ = ^
ém+n){yu...iym+„) =
jelikož g(/, y,..., y™) = s(s^(r(/), yi,..., y™)) je totálně vyčíslitelná funkce, i/; splňuje větu o parametrizaci
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
11/22
přípustná numerace
Definice 6.3 (přípustná numerace)
Totální numerace vyčíslitelných funkcí je přípustná (efektivní), pokud pro ni platí věty o numeraci a parametrizaci.
věty o numeraci a parametrizaci jsou nezávislé, tedy
■ existuje numerace, pro kterou platí věta o numeraci, ale neplatí věta o parametrizaci
■ existuje numerace, pro kterou neplatí věta o numeraci, ale platí věta o parametrizaci
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
12/22
numerace totálně vyčíslitelných funkcí
Věta 6.5
Necht ý je totální numerace všech unárních totálně vyčíslitelných funkcí Pak univerzální funkce <t>^ : N2 -> N definovaná jako
není vyčíslitelná.
Důkaz: diagonalizací ■
Důsledek 6.6
Neexistuje přípustná totální numerace všech totálních vyčíslitelných funkcí
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
13/22
rekurzivní množiny
Definice 7.1 (rekurzivní množina)
Množina AcNk je rekurzivní, pokud existuje totálně vyčíslitelná funkce f : Nk -> N taková, že
A = f-\V}) = {(xi,...,xk)eNk | f(x,,...,xk) = 1}.
Funkce f se nazývá rozhodovací funkce pro A.
■ rekurzivní množině se také říká rozhodnutelná či řešitelná
■ příklady rekurzivních množin:
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
14/22
rekurzivní množiny
Tvrzení
A c Nk je rekurzivní, právě když je její charakteristická funkce Xa ■ ^k -> N definovaná vztahem
1 pokud (x1,..., xk) g A 0 jinak
totálne vyčíslitelná.
Důkaz:
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
vlastnosti rekurzivních množin
Věta 7.4
Jestliže A c je konečná množina nebo Nk \ A je konečná, pak A je rekurzivní.
Důkaz:
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
16/22
vlastnosti rekurzivních množin
Lemma 7.5
Necht A, B c jsou rekurzivní množiny. Pak i množiny A, Au B a A n B jsou rekurzivní.
Důkaz:
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
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: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
18/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: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
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: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
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{rí) 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: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny
21/22
funkce Step counter
Lemma 7.9		
Funkce		
Sc(x, y,z) = <	' 1	jestliže program Px zastaví pro vstup y během z kroků
		jinak
je totálně vyčíslitelná.		
Důkaz: interpreter z důkazu věty o numeraci rozšíříme o počítán instrukcí
IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*, rekurzivní a r.e. množiny