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í.
Množina není rekurzivní, což dokážeme pomocí redukce. Ukážeme, že platí K ≤m B.
Chceme tedy ukázat, že existuje TVF f taková, že x ∈ K ⇐⇒ f(x) ∈ B.
Nechť máme nejprve funkci g(i), která pro konkrétní i vrátí index následujícího programu:
begin
y := Φ(i, i);
x1 := 0;
end
Pro funkci s indexem g(i) pak tedy platí:
ϕg(i)(a) =
0 pokud ϕi(i) je def - tedy i ∈ K
⊥ jinak.
Funkce g(i) jen dosazuje konkrétní číslo do kostry programu a vrací jeho index, tedy je TVF.
U funkce ϕg(i)(a) nezáleží její chování na vstupu a, pracujme tedy např. s nulou.
Naše redukční funkce f, se pak bude chovat takto: f(x) =< g(x), 0 >.
(pak tedy π1(f(x)) = g(x), π2(f(x)) = 0)
Jelikož párující funkce i funkce g jsou TVF, je i f TVF.
Nyní dokažme ekvivalenci x ∈ K ⇐⇒ f(x) ∈ B:
x ∈ K =⇒ ϕx(x) je def =⇒ ϕg(x)(0) = 0 =⇒ pro k=1 platí ϕ1
g(x)(0) = 0 =⇒ < g(x), 0 >∈ B
x /∈ K =⇒ ϕx(x) = ⊥ =⇒ ϕg(x)(0) = ⊥ =⇒ ∀k ≥ 1 platí ϕk
g(x)(0) = ⊥ =⇒ < g(x), 0 >/∈ B
Tedy jsme ukázali, že platí K ≤m B. A jelikož K není rekursivní, tak ani B nemůže být rekursivní.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.