IB107 úkol 1, příklad 2 Odevzdání: 20. 10. 2023 23:59
Jméno: Ferda Mravenec 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: N2 → N definovanou následovně:
g(i, j) =



j je-li definováno alespoň j z hodnot ϕ0(0), ϕ1(1), . . . , ϕi(i)
0 jinak
a) (2.5 bodu) Rozhodněte a dokažte, zda je funkce g 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(i)(j) = g(i, j).
a) Funkce g(i, j) není vyčíslitelná, což dokážeme sporem. Předpokládejme, že g(i, j) je vyčíslitelná.
Pak je vyčíslitelná i funkce
g (i) = j, kde j je počet definovaných hodnot z ϕ0(0), ϕ1(1), . . . , ϕi(i),
neboť ji počítá následující program, který pro daný vstup x1 = i vrací nejvyšší j splňující
g(i, j) > 0 a pokud takové j neexistuje, vrací 0.
begin
j := 1;
while g(x1, j) > 0 do j := j + 1;
x1 := j − 1
end
Pak je ovšem vyčíslitelná i funkce
f(i) =



1 jestliže ϕi(i) je definováno,
0 jestliže ϕi(i) není definováno,
kterou počítá následující program.
begin
if x1 = 0 then x1 := g (x1) else x1 := g (x1) − g (x1 − 1)
end
O funkci f ovšem víme, že rozhoduje problém zastavení a není vyčíslitelná. Tím jsme dostali
spor, přičemž jediným předpokladem bylo, že funkce g je vyčíslitelná.
b) Sporem dokážeme, že funkce h(i) s požadovanými vlastnostmi neexistuje. Předpokladejme, že
existuje totálně vyčíslitelná funkce h(i) splňující ϕh(i)(j) = g(i, j). Pak je ovšem funkce g(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(x1);
x1 := Φ(x3, x2);
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.