IB107 úkol 2, příklad 2 Odevzdání: 2. 11. 2021 23:59
Jméno: Brouk Pytlík 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 libovolnou funkci f : N → N definujeme binární relaci Rf ⊆ N2 vztahem
Rf = {(x, f(x)) | x ∈ dom(f)}.
Dokažte nebo vyvraťte každé z následujících tvrzení.
(a) f je vyčíslitelná funkce =⇒ relace Rf je rekurzivní
(b) f je vyčíslitelná funkce =⇒ relace Rf je r.e.
(c) f je vyčíslitelná funkce ⇐= relace Rf je r.e.
V důkazu můžete využít fakt, že následující funkce je totálně vyčíslitelná.
Sc (x, y1, y2, z) =
1 pokud program Px na vstupu (y1, y2) zastaví během z kroků
0 jinak
(a) Tvrzení neplatí. Uvažme například funkci f definovanou takto:
f(x) =
0 ak ϕx(x) = ⊥,
⊥ inak.
Tato funkce je zjevně vyčíslitelná (program simuluje pomocí univerzální funkcie výpočet ϕx(x)
a pokud výpočet skončí, vrací hodnotu 0). Pro funkci f platí
Rf = {(x, 0) | ϕx(x) = ⊥}.
Vidíme, že druhým řezem relace Rf pro hodnotu 0 je problém zastavení K = {x | ϕx(x) = ⊥}.
Jelikož libovolný řez rekurzivní množiny je opět rekurzivní množina, relace Rf není rekurzivní,
protože pak by musela být rekurzivní také množina K, což není.
(b) Tvrzení platí. Nechť f je libovolná vyčíslitelná funkce a if je nějaký její index. Zkonstruujeme
vyčíslitelnou funkci g : N2 → N splňující dom(g) = Rf , čímž dokážeme, že Rf je rekurzivně
spočetná. Funkce g je počítaná nasledujícím programem.
begin
x3 := Φ(if , x1);
while x3 = x2 do begin end
end
Pokud vstup (x1, x2) patří do Rf , tak výpočet Φ(if , x1) skončí a zároveň bude platiť x3 = x2,
tedy i náš program skončí a g(x1, x2) je definováno. Pokud vstup (x1, x2) do Rf nepatří, mohou
nastat dvě možnosti. Jestliže f(x1) není definováno, tak výpočet Φ(if , x1) cyklí a g(x1, x2)
není definováno. Jestliže f(x1) je definováno, ale x2 = f(x1), tak výpočet Φ(if , x1) skončí, ale
náš program cyklí, protože nikdy neopustí while-cyklus. Tedy opět g(x1, x2) není definováno.
Celkem dostáváme dom(g) = Rf .
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.
IB107 úkol 2, příklad 2 Odevzdání: 2. 11. 2021 23:59
Jméno: Brouk Pytlík 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.
(c) Tvrzení platí. Nechť Rf je relace definovaná pro nějakou funkci f : N → N dle zadání. Pokud
je Rf rekurzivně spočetná, pak existuje vyčíslitelná funkce g : N2 → N splňující dom(g) = Rf .
Nechť ig je nějaký index této funkce g. Následující program počítá funkci f.
begin
counter := 0;
done := 0;
while done = 0 do
begin
result := π1(counter);
steps := π2(counter);
done := Sc (ig, x1, result, steps);
counter := counter + 1
end
x1 := result
end
Program využívá makra implementující totálně vyčíslitelnou funkci Sc ze zadání a totálně
vyčíslitelné projekční funkce π1, π2 z přednášky.
Uvažme libovolné pevné x1. Není-li f(x1) definováno, v relaci Rf není žádná dvojice (x1, result),
a proto g(x1, result) = ⊥ a Sc (ig, x1, result, steps) = 0 pro libovolné hodnoty result a steps.
Program tedy cyklí, což odpovídá předpokladu f(x1) = ⊥. Je-li naopak f(x1) definováno,
existuje právě jedna hodnota result = f(x1) splňující (x1, result) ∈ Rf . Pro tuto hodnotu result
musí být g(x1, result) definováno, a tedy Sc (ig, x1, result, steps) = 1 pro dostatečně velkou
hodnotu steps. Postupným zvyšováním hodnoty counter prohledáváme všechny dvojice hodnot
result a steps a v konečném čase nějakou dvojici splňující Sc (ig, x1, result, steps) = 1 objevíme.
Náš program v tom případě skončí s hodnotou result na výstupu. Program tedy implementuje
funkci f a ta je proto vyčíslitelná.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.