IB107 úkol 1, příklad 1 Odevzdání: 12. 10. 2021 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.
Uvažme funkci f : N3 → N definovanou následovně:
f(i, j, k) =



ϕj(ϕi(k)) pokud ϕi(k) = ⊥,
ϕi(k) jinak.
a) (2 body) Rozhodněte a dokažte, zda je funkce f vyčíslitelná.
b) (1 bod) 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(j,k)(i) = f(i, j, k).
a) Funkce f je vyčíslitelná, neboť je počítaná následujícím programem (kde Φ je univerzální funkce
pro vyčíslitelné funkce arity 1):
begin
y := Φ(x1, x3);
x1 := Φ(x2, y)
end
Vskutku, pokud je ϕi(k) definováno, tak program spočítá ϕj(ϕi(k)), což je v souladu s prvním
řádkem definice funkce f. V opačném případě program cyklí, což je v souladu s druhým řádkem
definice f.
b) Ano, funkce h s požadovanými vlastnostmi existuje. Z odrážky a) víme, že funkce f je vyčíslitelná,
a tedy f = ϕ
(3)
e pro nějaké e ∈ N. Nechť f : N3 → N je funkce definovaná vztahem f (j, k, i) =
f(i, j, k). Funkce f je zřejmě vyčíslitelná, ale pro úplnost uvádíme program, který ji počítá (tentokrát
je Φ univerzální funkce pro vyčíslitelné funkce arity 3):
begin
x1 := Φ(e, x3, x1, x2)
end
Dle translačního lemmatu pro ternární funkce existuje totálně vyčíslitelná binární funkce h taková,
že ϕh(j,k)(i) = f (j, k, i) = f(i, j, k), což jsme měli dokázat.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.