IB107 úkol 2, příklad 1 Odevzdání: 8. 11. 2022 23:59
Jméno: Chrobák Truhlí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.
1. [3 body] Uvažme množinu B ⊆ N definovanou vztahem
B = {i | dom(ϕi) {0, 1} = ∅ a ∀y ∈ N . ϕi(y) = ϕi(y2
) = . . . = ϕi(yy
)}.
(a) Rozhodněte a dokažte, zda je množina B rekurzivní.
(b) Rozhodněte a dokažte, zda je množina B rekurzivně spočetná.
(a) Množina B není rekurzivní, což dokážeme pomocí 1. Riceovy věty.
B = ∅: Konstantní funkce g(x) = 1 je vyčíslitelná a její indexy patří do B, protože dom(g)
{0, 1} = N {0, 1} = ∅ a ∀y, x ∈ N . g(y) = g(x) = 1. Tedy {i | ϕi = g} ⊆ B a proto B = ∅.
B N: Prázdná funkce ε(x) = ⊥ je vyčíslitelná a její indexy do B nepatří, protože dom(ε) = ∅.
Tedy {i | ϕi = ε} ⊆ B a proto B N.
B respektuje funkce: Uvažme libovolné i, j ∈ N splňující i ∈ B a ϕi = ϕj. Jelikož dom(ϕi) =
dom(ϕj) a pro každé y ∈ N platí ϕi(y) = ϕj(y) = ϕi(y2) = ϕj(y2) = ... = ϕi(yy) = ϕj(yy),
dostáváme j ∈ B.
Z 1. Riceovy věty plyne, že množina B není rekurzivní.
(b) Množina B není rekurzivne spočetná, což dokážeme pomocí 3. Riceovy věty. V předchozím bodě
jsme již dokázali, že B respektuje funkce. Nyní zvolme θ jako konstantní funkci θ(x) = 1, což je
vyčíslitelná funkce.
{i | ϕi = θ} ⊆ B: V předchozím bodě jsme zdůvodnili, že indexy konstantní funkce θ(x) =
g(x) = 1 leží v B, tedy {i | ϕi = θ} ⊆ B.
{i | ϕi ≤ θ a dom(ϕi) je konečná množina} ⊆ B: Uvažme libovolnou vyčíslitelnou funkci ϕi
s konečným definičním oborem, která splňuje ϕi ≤ θ. Sporem dokážeme, že i ∈ B. Předpokládejme
opak a označme m největší prvek v dom(ϕi). Z předpokladu dom(ϕi) {0, 1} = ∅
plyne, že m ≥ 2. Z podmínky ∀y ∈ N . ϕi(y) = ϕi(y2) = . . . = ϕi(yy) dále plyne, že
ϕi(m) = ϕi(m2) a tedy m2 ∈ dom(ϕi). Jelikož m2 > m, dostáváme spor s volbou m jako
největšího prvku v dom(ϕi). Tím jsme dokázali, že
{i | ϕi ≤ θ a dom(ϕi) je konečná množina} ⊆ B.
Z 3. Riceovy věty plyne, že množina B není rekurzivně spočetná.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.