IB107 úkol 1, příklad 2 Odevzdání: 12. 10. 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.
2. [3 body] Uvažme funkci g: N3 → N definovanou následovně:
g(i, j, k) =



ϕj(ϕi(k)) pokud ϕi(k) = ⊥,
ϕj(k + 1) jinak.
a) (2 body) Rozhodněte a dokažte, zda je funce g vyčíslitelná.
b) (1 bod) Rozhoděte a dokažte, zda existuje totálně vyčíslitelná funkce
h: N2 → N taková, že pro všechna i, j, k ∈ N platí
ϕh(i,j)(k) = g(i, j, k).
a) Funkce g(i, j, k) není je vyčíslitelná.
Pro důkaz sporem předpokládejme, že g(i, j, k) je vyčíslitelná. Definujeme funkci
f(x) =
0 pokud ϕx(x) = ⊥,
⊥ jinak.
Funkce f(x) je počítaná následujícím programem a tedy vyčíslitelná. Označme její index e.
begin
Φ(x1, x1);
x1 := 0
end
Pokud je funkce g vyčíslitelná, je jistě vyčíslitelná i funkce halt(x) = 1−g(e, e , x), kde e je index
identity (tedy ϕe (x) = x) a odečítání funguje jako v jazyce while-programů (nejde do záporu).
Pro funkci halt platí
halt(x) = 1 − g(e, e , x) =



1 − ϕe (ϕe(x)) = 1 − f(x) pokud ϕe(x) = f(x) = ⊥,
1 − ϕe (x + 1) = 1 − (x + 1) jinak.
Uvedený zápis lze dále zjednodušit, jelikož
• f(x) = ⊥ platí právě tehdy, když ϕx(x) = ⊥. Pokud tato situace nastane, pak f(x) = 0.
• 1 − (x + 1) = 0, neboť x + 1 ≥ 1 a odečítání v jazyce while-programů nejde do záporu.
Celkem tedy dostáváme
halt(x) =



1 − 0 = 1 pokud ϕx(x) = ⊥,
0 jinak.
Funkce halt tedy rozhoduje problém zastavení a z přednášky víme, že nemůže být vyčíslitelná.
Tím jsme dostali spor, přičemž jediným předpokladem bylo, že funkce g je vyčíslitelná.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.
IB107 úkol 1, příklad 2 Odevzdání: 12. 10. 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.
b) Sporem dokážeme, že funkce h(i, j) s požadovanými vlastnostmi neexistuje.
Předpokladejme, že existuje totálně vyčíslitelná funkce h(i, j) splňující g(i, j, k) = ϕh(i,j)(k). Pak
je ovšem funkce g(i, j, k) vyčíslitelná, protože ji můžeme implementovat následujícím programem,
kde Φ je univerzální funkce pro unární vyčíslitelné funkce.
begin
x1 := h(x1, x2);
x1 := Φ1(x1, x3);
end
O funkci g jsme ovšem dokázali, že není vyčíslitelná. Dostáváme tedy spor.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.