IB107 úkol 2, příklad 1 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.
1. [3 body] Uvažme množinu
B = {i | ϕi(x) = 7 pro nekonečně mnoho různých x ∈ N}.
(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í.
Množina B je netriviální vlastní podmnožina N: Indexy prázdné funkce f(x) = ⊥, která
je vyčíslitelná, do množiny B zjevně nepatří, tedy B = N. Naopak indexy konstantní funkce
g(x) = 7, která je také vyčíslitelná, do množiny B patří, tedy B = ∅.
Množina B respektuje funkce: Uvažme libovolné i, j ∈ N splňující i ∈ B a ϕi = ϕj. Tedy
ϕi(x) = 7 pro nekonečně mnoho různých x ∈ N a pro všechna tato x platí ϕj(x) = ϕi(x) = 7.
Dostáváme, že ϕj(x) = 7 pro nekonečně mnoho různých x ∈ N a proto j ∈ B.
Z 1. Riceovy věty plyne, že množina B není rekurzivní.
(b) Množina B není je rekurzivne spočetná.
V předchozím bodě jsme již dokázali, že B respektuje funkce.
Zvolme θ jako konstantní funkci θ(x) = 7. Tato funkce je vyčíslitená a všechny její indexy leží
v B, tedy {i | ϕi = θ} ⊆ B.
Nyní uvažme libovolnou vyčíslitelnou funkci ϕj s konečným definičním oborem, která splňuje
ϕj ≤ θ. Jelikož ϕj je definovaná jen pro konečně mnoho různých argumentů, nemůže existovat
nekonečne mnoho různých vstupů x splňujících ϕj(x) = 7 a proto j ∈ B. Tím jsme dokázali
{j | ϕj ≤ θ a dom(ϕj) je konečná množina} ⊆ B.
Z třetí Riceovy věty plyne, že množina B není je rekurzivně spočetná.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.