Why are the total functions not enumerable?

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?

Answer 1

Because of diagonalization. If $(f_e: e \in \mathbb{N})$ was a computable enumeration of all total computable functions from $\mathbb{N}$ to $\mathbb{N}$, such that every $f_e$ was total, then $g(i) = f_i(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.

Answer 2

Just to be clear, we need to distinguish mathematical functions (I will call them functions and there is often uncountably many of them so they are not at all enumerable) and functions you can write: I will call them programs or also computable functions.

A subset $S$ of a countable set $E$ is called computable if there is a program that, given an element $x$ of $E$ responds "yes" if $x∈S$ and "no" if $x\not∈S$. (And he always has to respond something) A set is called recursively enumerable if the program is authorized not to respond instead of saying "no". (it's equivalent to require that the program has to print all elements of $S$ in any order)

The set of all programs that are total on a finite set is enumerable because you can write an interpreter that just run the program on all the elements of the finite set and return "yes" if they all terminates. (But can't see if any of them does not)

Your professor said that the set of all programs that are total on a infinite set is not enumerable because you can't just run your program on an infinite number of elements.

But this does not mean this is bad:

1. For example the set if all programs that are provably total is enumerable because you can enumerate all the proofs and mechanically check if they prove your program is total.

2. Even an enumerable set would not be practical, because you may have to wait forever without being sure if the procedure would terminate one day. I don't see how to use a programs that enumerate all total functions...

There are some programming languages where everything you write is guaranteed to terminate just with static typing! There are even some that guarantees you polynomial bound. They are mostly academic for now, writing in those will probably make you feel the constraints more that writing in Python, but there are a lot of researchers working on this.

So to answer your question: in a sense, yes. Potential non-termination is necessary to be Turing-complete (highest computational power for now). But I don't find this directly relevant to the fact that total functions are enumerable or not. You can still write all total programs!