IB107 úkol 1, příklad 1 Odevzdání: 20. 10. 2023 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 : N3 → N definovanou následovně:
f(i, j, k) =



1 +
j
n=i
ϕn(k) pokud i ≤ j a pro všechna i ≤ n ≤ j platí ϕn(k) = ⊥
0 pokud i > j
⊥ 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: N2 → N taková, že
pro všechna i, j, k ∈ N platí
ϕh(i,j)(k) = f(i, j, k).
a) Funkce f je vyčíslitelná, počítá ji například následující program.
begin
if x1 > x2 then x1 := 0 else begin
x4 := 1;
while x1 ≤ x2 do begin
x4 := x4 + Φ(x1, x3);
x1 := x1 + 1
end;
x1 := x4
end
end
Program pro argumenty i, j, k nejprve vyřeší případ i > j, pro který nastaví výstupní proměnnou
x1 na 0. Pokud i ≤ j, tak program v proměnné x4 přímočaře spočítá odpovídající hodnotu funkce
f a následně ji zkopíruje do výstupní proměnné x1. Pokud i ≤ j a výpočet makra Φ(x1, x3) pro
nějaké i ≤ x1 ≤ j a x3 = k zacyklí, pak je funkce počítaná programem pro uvažované hodnoty
nedefinovaná, což odpovídá definici funkce f.
b) Ano, funkce h s požadovanými vlastnostmi existuje. Věta o parametrizaci říká, že existuje totálně
vyčíslitelná funkce s2
1 : N3 → N taková, že pro všechna e, i, j, k ∈ N platí ϕs2
1(e,i,j)(k) = ϕ
(3)
e (i, j, k).
Funkci h: N2 → N získáme z funkce s2
1 zafixováním prvního argumentu na hodnotu libovolného
indexu e funkce f. Takový index existuje, neboť je funkce f vyčíslitelná. Funkce h je tedy totálně
vyčíslitelná a platí:
ϕh(i,j)(k) = ϕs2
1(e,i,j)(k) = ϕ(3)
e (i, j, k) = f(i, j, k).
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.