IB107 úkol 1, příklad 1 Odevzdání: 10. 11. 2020 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) =
max(ϕi(k), ϕj(k)) pokud ϕi(k) = ⊥ = ϕj(k),
⊥ jinak.
a) (1,5 bodu) 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: N → 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á, neboť je počítaná následujícím programem (kde Φ je univerzální funkce
pro vyčíslitelné funkce arity 1):
begin
y := Φ(x1, x3);
z := Φ(x2, x3);
if y < z then x1 := z else x1 := y
end
Vskutku, program zastaví na vstupu i, j, k právě když zastaví výpočty hodnot Φ(i, k) = ϕi(k)
a Φ(j, k) = ϕj(k), tedy právě když jsou obě hodnoty definovány. V takovém případě pak díky
předposlednímu řádku vrátí maximum z těchto hodnot.
b) Dle věty o parametrizaci existuje totálně vyčíslitelná funkce s1
2 : N2 → N taková, že pro všechna
e, i, j, k ∈ N je ϕ
(2)
s1
2(e,i)
(j, k) = ϕ
(3)
e (i, j, k). Z odrážky a) víme, že f je vyčíslitelná ternární funkce,
existuje tedy index E ∈ N takový, že f = ϕ
(3)
E . Definujme nyní unární funkci h tak, že pro libovolné
i ∈ N položíme h(i) = s1
2(E, i) (pozn. autora: lze též psát h = s1
2(E, ·)). Funkce h je vyčíslitelná,
neboť ji počítá následující program:
begin
x1 := s1
2(E, x1)
end
(přičemž s1
2 je vyčíslitelná, viz výše). Protože s1
2 je totální, tento program vždy zastaví a tedy i h je
totální. Konečně pro všechna i, j, k ∈ N platí
ϕh(i)(j, k) = ϕs1
2(E,i)(j, k) = ϕ
(3)
E (i, j, k) = f(i, j, k),
kde první rovnost plyne z definice funkce h, druhá rovnost je vlastností funkce s1
2 a poslední rovnost
plyne z definice konstanty E.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.