IB107 úkol 2, příklad 2 Odevzdání: 8. 11. 2022 23:59
Jméno: Ferdo Mravec UČO: 1234567
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2. [3 body] Pro každé j ∈ N definujeme množinu Aj ⊆ N následujícím způsobem:
Aj =
l ∈ range(ϕj)
range(ϕl)
(a) Dokažte, že existují indexy j, k ∈ N takové, že Aj je rekurzivní a Ak není rekurzivní.
(b) Rozhodněte a dokažte, zda jsou všechny množiny Aj rekurzivně spočetná.
(a) Nechť j je index prázdné funkce, tedy ϕj(x) = ⊥. Jelikož range(ϕj) = ∅ a sjednocení přes
prázdnou množinu je prázdná množina, dostáváme Aj = ∅, což je rekurzivní množina.
Zbývá najít k takové, že Ak není rekurzivní. Jelikož problém zastavení K je rekurzivně spočetná
množina, existuje vyčíslitelná funkce ϕm splňující range(ϕm) = K. Nechť k je index konstantní
funkce m, tedy ϕk(x) = m. Platí range(ϕk) = {m} a celkově dostáváme
Ak =
l ∈ range(ϕk)
range(ϕl) =
l ∈ {m}
range(ϕl) = range(ϕm) = K
Množina Ak = K není rekurzivní.
(b) Ukážeme, že každá množina Aj je rekurzivně spočetná. Pro libovolné pevné j ∈ N zkonstruujeme
program, který generuje množinu Aj pomocí příkazu output(x). Nejprve přepíšeme definici Aj
do ekvivalentního tvaru
Aj = {i | ∃k . k ∈ dom(ϕj) a i ∈ range(ϕϕj(k))}
= {ϕϕj(k)(y) | ∃k, y . k ∈ dom(ϕj) a y ∈ dom(ϕϕj(k))}.
Nyní snadno napíšeme program, který prochází všechny trojice (k, y, z) ∈ N3 a funkcí Sc zjišťuje,
zda výpočty ϕj(k) a ϕϕj(k)(y) pomocí příslušných programů zastaví během z kroků. Pokud tomu
tak je, program dá na výstup hodnotu ϕϕj(k)(y). Připomínáme, že j reprezentuje v programu
fixní hodnotu a nikoliv promněnnou.
begin
n := 0;
while true do begin
k := π1(n);
y := π1(π2(n));
z := π2(π2(n));
if Sc(j, k, z) = 1 then begin
l := Φ(j, k);
if Sc(l, y, z) = 1 then output(Φ(l, y))
end;
n := n + 1
end
end
Dodejme, že pokud k ∈ dom(ϕj) a y ∈ dom(ϕϕj(k)), tak musí existovat z splňující Sc(j, k, z) = 1
a Sc(l, y, z) = 1, kde l = ϕj(k). Tedy program generuje právě množinu Aj a ta je tudíž rekurzivně
spočetná.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.