IB107 úkol 2, příklad 2 Odevzdání: 2. 11. 2021 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.
2. [3 body] Pro libovolnou funkci f : N → N definujeme binární relaci Rf ⊆ N2 vztahem
Rf = {(x, f(x)) | x ∈ dom(f)}.
Dokažte nebo vyvraťte každé z následujících tvrzení.
(a) f je vyčíslitelná funkce =⇒ relace Rf je rekurzivní
(b) f je vyčíslitelná funkce =⇒ relace Rf je r.e.
(c) f je vyčíslitelná funkce ⇐= relace Rf je r.e.
V důkazu můžete využít fakt, že následující funkce je totálně vyčíslitelná.
Sc (x, y1, y2, z) =
1 pokud program Px na vstupu (y1, y2) zastaví během z kroků
0 jinak
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.