Graph theorem for partial recursive functions

[4/100%]
Show
LaTeX
Problem III.3.23 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that the graph of a general recursive function is recursive.

?
Problem III.3.24 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that if the graph Γf\Gamma_{f} of a function ff is recursively enumerable, then the function ff is partial recursive.

?
Problem III.3.30 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that:

?
(a)

a function obtained by means of superposition from functions with recursively enumerable graph has recursively enumerable graph;

(b)

a function obtained by means of the primitive recursion scheme from functions with recursively enumerable graph has recursively enumerable graph;

(c)

a function obtained by means of the μ\mu-operator from a function with recursively enumerable graph has recursively enumerable graph;

(d)

the graph of any partial recursive function is recursively enumerable.

Problem III.3.31 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that a function is partial recursive if and only if its graph is recursively enumerable (the graph theorem).

?

References

[LaMa02] Lavrov I.A., Maksimova L.L. Задачи по теории множеств, математической логике и теории алгоритмов. 5-е изд., Физматлит, 2002.