Basic Concepts 9 – Productive Sets and Productive Functions

File:Emil Leon Post.jpg

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



  1. It was Kurt Ammon who directed my attention to the notion of productive sets and productive functions by letting me proof-read successive versions of an as yet unpublished paper. Some of the ideas I am presenting in this series of articles are my own, but a lot of them come from Kurt. I hope that he is going to publish that paper soon.

  2. […] may be part of the solution, but something is missing here. The existence, in mathematics, of productive functions provides a hint on what that missing thing might […]

  3. […] we perceive, to think or to do something, defines a closed “space”. We can leave that space and take a vantage point outside that bit of knowledge. From this meta-level or point of reflection, we can critically think about […]

  4. In a previous version of this article, I had written that the concept of productive functions was developed by Post. It looks like this was a mistake, so I have removed it. Some research into the literature is necessary to find out who actually came up whith this concept (I think, during the 1950s).

  5. […] the new knowledge can actually be constructed from the old formal system (by means of a productive function), there is a process that brings us from one formal description of a cognitive system (think of the […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: