IB107 úkol 2, příklad 2 Odevzdání: 10. 11. 2023 23:59
Jméno: Ferdo Mravec 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.
2. [3 body] Uvažme množinovou operaci , která pro libovolné množiny A, B ⊆ N vrací množinu
A B = {x + y | x ∈ A, y ∈ B}.
Dokažte nebo vyvraťte následující implikace.
(a) A je rekurzivní =⇒ A A je rekurzivní
(b) A je rekurzivně spočetná =⇒ A A je rekurzivně spočetná
Bonus [2 body]: Za důkaz či vyvrácení každé z následujících implikací můžete získat další bod.
(c) A je rekurzivní ⇐= A A je rekurzivní
(d) A je rekurzivně spočetná ⇐= A A je rekurzivně spočetná
(a) Implikace platí. Pro dané z ∈ N rozhodujeme z
?
∈ A A intuitivně tak, že z postupně rozložíme
na všechny dvojice x, y splňující z = x + y a pokud pro nějakou takovou dvojici platí x, y ∈ A,
pak z ∈ A A. V opačném případě z ∈ A A.
Předpokládejme tedy, že A je rekurzivní a její charakteristická funkce χA je tudíž totálně vyčíslitelná.
Pak je i množina A A rekurzivní, protože její charakteristickou funkci χA A lze počítat
následujícím programem.
begin
x := 0;
y := x1 − x;
r := 0;
while x ≤ x1 do begin
if (χA(x) = 1 ∧ χA(y) = 1) then r := 1;
x := x + 1;
y := x1 − x
end;
x1 := r
end
(b) Implikace platí. Využijeme fakt, že množina je r.e., právě když je oborem hodnot nějaké vyčíslitelné
funkce. Nechť A je r.e. a f : N → N je vyčíslitelná funkce splňující range(f) = A. Pak
A A je taktéž r.e., neboť je oborem hodnot vyčíslitelné funkce g počítané tímto programem:
begin
x := f(π1(x1));
y := f(π2(x1));
x1 := x + y
end
Zjevně platí range(A) ⊆ A A, jelikož všechny výstupy programu jsou tvaru x + y, kde x, y ∈
range(f) = A. Zbývá dokázat range(A) ⊇ A A. Uvažme libovolný prvek z ∈ A A. Pak
z = x + y pro vhodné x, y ∈ A = range(f). Tedy z = f(a) + f(b) pro vhodné a, b ∈ N. S
využitím párující funkce τ snadno získáme τ(a, b), pro které platí g(τ(a, b)) = f(π1(τ(a, b))) +
f(π2(τ(a, b))) = f(a) + f(b) = z, a proto z ∈ range(g). Celkem dostáváme range(g) = A A.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.
IB107 úkol 2, příklad 2 Odevzdání: 10. 11. 2023 23:59
Jméno: Ferdo Mravec 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.
(c) Implikace neplatí. Protipříklad snadno zkonstruujeme s využitím operace ⊕ definované pro libovolné
A, B ⊆ N na cvičeních v příkladu 4.2:
A ⊕ B = {2a | a ∈ A} ∪ {2b + 1 | b ∈ B}.
Na cvičeních jsme dokázali, že A ⊕ B je rekurzivní právě tehdy, když A i B jsou rekurzivní.
Jelikož K není rekurzivní, tak ani množina N⊕K není rekurzivní. Dále víme, že přidání konečně
mnoha prvků do množiny nemá vliv její (ne)rekurzivitu. Proto ani množina A = (N ⊕ K) ∪ {1}
není rekurzivní. Tato množina přitom obsahuje všechna sudá čísla včetně 0 a také číslo 1. Tedy
A A = N, což je rekurzivní množina.
(d) Ani tato implikace neplatí. Na cvičeních jsme totiž také dokázali, že A ⊕ B je r.e. právě tehdy,
když A i B jsou r.e. Jelikož K není r.e., tak ani množina N ⊕ K není r.e. Dále víme, že přidání
konečně mnoha prvků do množiny nemá vliv na to, zda množina je či není rekurzivně spočetná.
Proto ani množina A = (N⊕K)∪{1} není r.e. Tato množina přitom obsahuje všechna sudá čísla
včetně 0 a také číslo 1. Tedy A A = N, což je r.e. množina. Dodejme, že zde zkonstruovaná
množina A by šla použít jako protipříklad i pro předchozí implikaci.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.