[34] (a) Show that it is possible to effectively enumerate the partial computable functions without repetition. (b) Let A = {x : x is a

[34]

(a) Show that it is possible to effectively enumerate the partial computable functions without repetition.

(b) Let A = {x : φx is a total function}. Prove that A is not computably enumerable.

Comments. Items

(a) and

(b) are not contradictory. Hint: In Item (a), dovetail the computations of all partial computable functions on all arguments. Attributed to R.A. Friedberg, 1958. Source: [H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967; P. Odifreddi, Classical Recursion Theory, North-Holland, 1989, pp. 230–232].