IB107 úkol 2, příklad 1 Odevzdání: 10. 11. 2023 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 F ⊆ N definovanou vztahem
F = {i | existuje k > 1 takové, že pro všechna x ∈ N platí ϕi(k · x) = k}.
(a) Rozhodněte a dokažte, zda je množina F rekurzivně spočetná.
(b) Rozhodněte a dokažte, zda je množina F rekurzivně spočetná.
(a) Množina F není rekurzivně spočetná, což dokážeme pomocí 3. Riceovy věty.
F respektuje funkce: Uvažme libovolné i, j ∈ N splňující i ∈ F a ϕi = ϕj. Jelikož i ∈ F, tak
existuje k > 1 takové, že pro všechna x ∈ N platí ϕi(k · x) = k. Z rovnosti ϕi = ϕj pak
plyne, že pro stejné k > 1 a všechna x ∈ N také platí ϕj(k · x) = k, a proto j ∈ F.
Jako funkci θ zvolíme například konstantní funkci θ(x) = 2. Tato funkce je zjevně vyčíslitelná.
{i | ϕi = θ} ⊆ F: Pokud ϕi = θ, pak pro všechna x ∈ N platí ϕi(2x) = θ(2x) = 2. Pro k = 2 je
tedy splněna podmínka v definici F, a proto i ∈ F.
{i | ϕi ≤ θ a dom(ϕi) je konečná množina} ⊆ F: Uvažme libovolnou vyčíslitelnou funkci ϕi
s konečným definičním oborem, která splňuje ϕi ≤ θ. Sporem dokážeme, že i ∈ F. Předpokládejme,
že i ∈ F. Pak ovšem existuje k > 1 takové, že ϕi(k · x) = k pro všechna x ∈ N.
Zejména tedy platí, že ϕi je definovaná pro všechny násobky k a množina dom(ϕi) je tudíž
nekonečná. To je spor, a proto i ∈ F.
Z 3. Riceovy věty plyne, že množina F není rekurzivně spočetná.
(b) Množina F také není rekurzivně spočetná, což dokážeme pomocí 2. Riceovy věty. Nechť θ(x) = ⊥
je funkce s prázdným definičním oborem a θ (x) = 2. Obě funkce jsou zjevně vyčíslitelné a θ ≤ θ .
F respektuje funkce: Víme, že libovolná množina respektuje funkce právě tehdy, když respektuje
funkce její doplněk. Dokázali jsme, že F respektuje funkce, a proto také F repsektuje
funkce.
{i | ϕi = θ} ⊆ F: Jelikož θ není definovaná pro žádný argument, nemůže existovat ani jedno k
a x takové, že θ(k · x) = k a proto všechny indexy θ leží v F.
{i | ϕi = θ } ⊆ F = F: Skutečnost, že indexy konstantní funkce 2 leží v F, byla dokázaná v bodě
(a), kde byla tato funkce nazvaná θ.
Z 2. Riceovy věty plyne, že množina F není rekurzivně spočetná.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.