We learned about the concept of enumerations of functions. In practice, they cor

Question

We learned about the concept of enumerations of functions. In practice, they correspond to programming languages.

In a passing remark, the professor mentioned that the class of all total functions (i.e. the functions that always terminate for every input) is not enumerable. That would mean that we can not devise a programming language that allows us to write all total functions but no others---which would be nice to have!

So how is it that we (apparently) have to accept the potential for non-termination if we want decent computational power?

Explanation / Answer

Because of diagonalization. If (fe:e?N) was a computable enumeration of all total computable functions from N to N, such that every fe was total, then g(i)=fi(i)+1 would also be a total computable function, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no computable enumeration of functions can consist of exactly the total computable functions.

Suppose we think of a universal computable function h(e,i), where "universal" means h is a computable binary function and that for every total computable unary function f(n) there is some e such that f(i)=h(e,i) for all i. Then there must also be some e such that g(n)=h(e,n) is not a total function, because of the previous paragraph. Otherwise h would give a computable enumeration of total computable unary functions that includes all the total computable unary functions.

Thus the requirement that every function is a system of functions is total is incompatible with the existence of a universal function in that system. For some weak systems, such as the primitive recursive functions, every function is total but there are not universal functions. Stronger systems that have universal functions, such as Turing computability, simply must have partial functions in order to allow the universal function to exist.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.