IB107 úkol 1, příklad 1 Odevzdání: 18. 10. 2022 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 funkci f : N2 → N definovanou následovně:
f(i, j) =



ϕi(ϕj(j) + ϕi(j)) pokud ϕj(j) = ⊥ a ϕi(j) = ⊥,
ϕi(5) jinak.
a) (2.5 bodu) Rozhodněte a dokažte, zda je funkce f vyčíslitelná.
b) (0.5 bodu) Rozhodněte a dokažte, zda existuje totálně vyčíslitelná funkce h: N → N taková, že
pro všechna i, j ∈ N platí
ϕh(j)(i) = f(i, j).
a) Funkce f(i, j) není vyčíslitelná, což dokážeme sporem. Předpokládejme, že f(i, j) je vyčíslitelná.
Definujeme funkci
p(x) =
99 pokud x = 5,
100 jinak.
Funkce p(x) je počítaná následujícím programem a tedy vyčíslitelná. Označme její index e.
begin
if x1 = 5 then x1 := 99 else x1 := 100
end
Pokud je funkce f vyčíslitelná, je vyčíslitelná i funkce h(x) = f(e, x) − 99, pro kterou platí
h(x) = f(e, x) − 99 =



ϕe(ϕx(x) + ϕe(x)) − 99 pokud ϕx(x) = ⊥ a ϕe(x) = ⊥,
ϕe(5) − 99 jinak.
Tento zápis dále zjednodušíme díky pozorování, že funkce ϕe je totální a ϕe(x) > 5 pro všechna x.
V prvním případě tedy platí ϕx(x) + ϕe(x) > 5 a proto ϕe(ϕx(x) + ϕe(x)) = 100. Dostáváme
h(x) =



100 − 99 = 1 pokud ϕx(x) = ⊥,
99 − 99 = 0 jinak.
Funkce h je tedy totožná s funkcí halt, která rozhoduje problém zastavení. Z přednášky víme, že
funkce h = halt není vyčíslitelná. Tím jsme dostali spor, přičemž jediným předpokladem bylo, že
funkce f je vyčíslitelná.
b) Sporem dokážeme, že funkce h(j) s požadovanými vlastnostmi neexistuje.
Předpokladejme, že existuje totálně vyčíslitelná funkce h(j) splňující f(i, j) = ϕh(j)(i). Pak je
ovšem funkce f(i, j) vyčíslitelná, protože ji můžeme implementovat následujícím programem, kde
Φ je vyčíslitelná univerzální funkce pro standardní numeraci unárních vyčíslitelných funkcí.
begin
x3 := h(x2);
x1 := Φ(x3, x1);
end
O funkci f jsme ovšem dokázali, že není vyčíslitelná. Dostáváme tedy spor.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.