In a previous article, I have sketched a proof that shows that the set of computable total functions (as well as the sets of programs calculating them, and of the Gödel numbers of such programs) is not enumerable. I want to look into this matter in more detail here.
All of these sets are not enumerable, i.e. there cannot be any program that has the natural numbers as inputs and produces all elements of these sets as an output, and only these elements. This is what the proof sketched in that article is demonstrating.
It is, however, possible to enumerate larger sets that contain all these elements, plus some more that do not belong to these sets. For example, it is possible to enumerate all natural numbers: you just have to count to do so. All the Gödel numbers of total functions must appear in this enumeration somewhere, i.e. the set of Gödel numbers of programs calculating total functions is a subset of the set of all natural numbers.
Likewise, it is also possible to enumerate all programs that can be written in a given programming language. I am not going to demonstrate that here, but it can be done – programming languages have a strict syntax and by applying the rules of that syntax in a systematic way, one could generate all the programs, one by one. All the programs calculating total functions will appear somewhere in this sequence.
However, it is not possible to enumerate just the “right ones” and only those, the programs calculating total functions or the Gödel numbers of these programs, as was demonstrated in the proof sketch.
It is also possible to enumerate subsets of these non-enumerable sets (e.g. just the programs (or their Gödel numbers) producing constant total functions, where every input of one of these programs is mapped to the same number).
So you have a set (let’s call it “A”) that is not enumerable and there are subsets of A (let’s call such a subset “S”) that are enumerable. The operation used in the proof sketch (“take the diagonal and modify (e.g. by adding 1)” can then be used to produce a new element (let’s call it “s”) of A that is not contained in S. This operation is even computable: We can write a program that takes the program enumerating S (or its Gödel-number) as an input and produces a new program s that is an element of A but not of S. We can then produce a new enumeration that produces all elements of S, and s on top. So any enumeration of a subset S of A can be extended and this extension process is computable.
However, although the extension process is computable, it cannot be used to construct an enumeration of A. The proof sketched in this article has demonstrated that this cannot be possible.
In mathematics, such a set A is called a productive set. The function that allows us to find a new element of A given an enumerable subset of S is called a productive function (H. Rogers. Theory of Recursive Functions and E_ective Computability. The MIT Press, Cambridge, 1987.).
What does all of this mean?
Mathematics contains “objects” or “entities” for which a complete formal description is not possible (I leave the discussion what a mathematical object is and in which sense it exists to the philosophers of mathematics). There cannot be any single formal theory in which all true statements of the form “f is a computable total function” are derivable, and only those statements. There cannot be any program producing all of them, and only those. In this sense, the concept of “total functions” cannot be completely formalized.
However, for each formal theory or program describing a subset of the set of total computable functions, we can generate a new element of that set. It is always possible to extend the programs or formal theories we have at any given time.
It is, however, impossible to integrate this extension mechanism into the formal system in such a way that we get a complete formal system. We can of course integrate it and produce formal systems that are much more powerful than the original one, producing sets of additional elements, but each such formal system will in turn be incomplete.
We have reached here the border of what can be formalized. The concepts sketched here have profound philosophical consequences. In a paper published in 1944 (“Recursively enumerable sets of positive integers and their decision problems”, Bulletin of the American Mathematical Society 50 (5): 284–316)), the mathematician and logician Emil Post (see picture above) wrote (p. 295):
The conclusion is unescapable that even for such a fixed, well defined body of mathematical propositions, mathematical thinking is, and must remain, essentially creative.
However, his insights into the limits of what can be formalized and the need for a notion of creativity where not picked up by the mainstream of philosophy, even of analytical philosophy and where totally ignored in the field of “artificial intelligence” that was created about ten years later. I am planning to explore the philosophical consequences of these insights in further articles.
(The picture, showing the mathematician Emil Leon Post, is from https://commons.wikimedia.org/wiki/File:Emil_Leon_Post.jpg.)