IB107 úkol 1, příklad 2 Odevzdání: 18. 10. 2022 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) =



ϕi(ϕj(j) + ϕi(j)) pokud pro všechna k ≥ min(i, j) platí ϕk(j) = ⊥,
ϕi(5) 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(j)(i) = g(i, j).
a) Funkce g je vyčíslitelná.
Uvažme funkci m(x) = ⊥ s prázdným definičním oborem. Tato funkce je vyčíslitelná (počítá ji
například program Pempty) a jako každá vyčíslitelná funkce má nekonečně mnoho indexů. Pro
libovolé i, j tedy existuje index k této funkce takový, že k ≥ min(i, j). Jelikož ϕk(j) = m(j) = ⊥
pro každé j, podmínka v první větvi definice funkce g nikdy neplatí. Můžeme tedy usoudit, že
g(i, j) = ϕi(5).
Funkce g je vyčíslitelná, neboť ji lze počítat například následujícím programem, který využívá
vyčíslitelnou univerzální funkci Φ pro standardní numeraci unárních vyčíslitelných funkcí.
begin
x1 := Φ(x1, 5)
end
b) Ano, funkce h s požadovanými vlastnostmi existuje. Z odrážky a) víme, že funkce g je vyčíslitelná,
a tedy g = ϕ
(2)
e pro nějaké e ∈ N. Nechť g : N2 → N je funkce definovaná vztahem g (j, i) = g(i, j).
Funkce g je zřejmě vyčíslitelná, ale pro úplnost uvádíme program, který ji počítá (tentokrát je
Φ univerzální funkce pro standardní numeraci binárních vyčíslitelných funkcí).
begin
x1 := Φ(e, x2, x1)
end
Dle translačního lemmatu pro binární funkce existuje totálně vyčíslitelná unární funkce h taková,
že ϕh(j)(i) = g (j, i) = g(i, j), což jsme měli dokázat.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.