Necht $ : N2 N je univerzální funkce pro množinu Kolik indexů má $? Vaši odpověď zdůvodněte!
všech unárních vyčíslitelných funkcí.
! l J
I i
O-V
2.2 Nechi Pe je program, který počítá univerzální funkci $ : N2 —> N. Ukažte, že výsledek výpočtu programu Pe pro vstupní vektor (e,a) je stejný jako výsledek výpočtu Pe pro vstupní vektor
2.4 Definujme obecněji pojem univerzální funkce následovně. Nechť .Fje třída j— árních funkcí, ne nutně vyčíslitelných. Univerzální funkce F : W+1 —> N pro F je funkce splňující následující dvě podmínky:
(a) Pro každé pevné e G N patří j-ární funkce F(e, xi,..., Xj) doT.
(b) Ke každé funkci f(xi,..., Xj) G T existuje e e N tak, že pro všechna xi,...,Xj G N:
F(e,x1,.. .,Xj) = f(xi, ...,Xj)
Pro jednoduchost předpokládejme j = 1.
(a) Definujte univerzální funkci pro třídu funkcí F = {1, x, x2, ar,... }.
(b) Definujte univerzální funkci pro třídu funkcí F = {x, x3, x5,... }.
(c) Ukažte, že každá konečná třída funkcí F má univerzální funkci F.
miro
2.5 Použijeme definici univerzální funkce z cvičení 2.4.
(a) Nechť T je třída totálních unárních funkcí nad N, která má univerzální funkci F : N2 -> N. Dokažte, že pak existuje totální unární funkce, která nepatří do T.
(b) Dokažte, že třída všech totálně vyčíslitelných unárních funkcí nad N, nemá vyčíslitelnou univerzální funkci.
r(č)) Definujte nekonečnou třídu totálně vyčíslitelných funkcí, která má vyčíslitelnou univer-zální funkci. ' ==ss'
A9 ^
Ve
VJK\M      ^Cmk ^
a— i. ^
1
^    - ^Vv, Ui,„ vyt- <^<^ ^ \
II
LAJ é 4
miro
Nechť* : N2  > N je univerzální funkce. Ukažte, žc funkce </<x) - nemůže být rozšířena
na totální vyčíslitelnou fvmkd.
Řekneme, 2e / je rozšířením g, píSeme g < f, jestliže kdykoliv je g{x) definováno, pak je definováno i /(ar) a /(x) = fl(.r). ^
	
	
	
	
	
	6