IB107 úkol 2, příklad 3 Odevzdání: 3. 12. 2020 23:59
Jméno: Chuck Norris 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.
3. [2 body] Bonusový úkol, bude opraven jen tehdy, pokud z ostatních dvou příkladů
získáte alespoň 4 body.
Připomeňme definici iterovaného skládání funkcí: pro libovolnou funkci f : N → N a libovolné
x ∈ N klademe f0(x) = x; pro k > 0 klademe fk(x) = f(fk−1(x)) (pokud fk−1(x) = ⊥, pak
i fk(x) = ⊥). Pozor, nepleťte toto značení se značením arity z přednášky (ϕ
(m)
i jakožto sémantická
funkce programu Pi arity m).
Uvažme množinu
B = {i | ∃k ≥ 1.ϕk
π1(i)(π2(i)) = 0}.
(Zde π1 a π2 jsou projekce párovací funkce, viz 2. přednáška). Rozhodněte a dokažte, zda je
množina B rekurzivní.
B nie je rekurzívna.
Dôkaz. Tvrdenie dokážeme redukciou K ≤m B, kde K = {i | ϕi(i) je definované}. Nech y je index
programu:
begin
Φ(x1, x1) ;
x1 := 0;
end
Program počítajúci funkciu f definujeme nasledovne:
begin
x1 := τ(y, x1) ;
end
f teda vráti spárovanu dvojicu y (index vyššie uvedeného programu) a x1. Táto funkcia je zrejme
totálne vyčísliteľná, nakoľko vieme vytvoriť index y a párujúca funkcia τ je TV.
Dokážeme x ∈ K ⇐⇒ f(x) ∈ B.
x ∈ K ⇒ f(x) ∈ B:
x ∈ K ⇒ f(x) = τ(y, x). Máme ϕx(x) je def., teda ϕ1
y(x) = 0, takže τ(y, x) ∈ B ⇒ f(x) ∈ B.
x /∈ K ⇒ f(x) /∈ B:
x /∈ K ⇒ f(x) = τ(y, x). Vieme, že ϕx(x) nie je def., teda ani ϕ1
y(x) nie je def., tým pádom
(∀k ≥ 1)(ϕk
y(x) = ⊥), takže τ(y, x) /∈ B ⇒ f(x) /∈ B.
Ukázali sme, že K ≤m B a keďže K nie je rekurzívna, tak ani B nie je rekurzívna.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.