Sketch of a Proof: Computable Total Functions are not Enumerable

Diagonal

After getting an intuitive understanding of some basic concepts, we have now reached a point where it is possible to sketch the proof for a crucial result: the programs computing total functions on natural numbers are not enumerable. Before I sketch the proof, I want to give a little bit of motivation on why this is important.

We may think of cognitive processes as processes of information processing, i.e. processes of calculation. The justification of such an approach might be disputed, but for the time being, let’s assume it is valid. In such a model of cognition, we would think of the brain as something comparable to a computer. Data is entering the mind through the senses or is the result of previous computations or recall from memory. The data is transformed by applying some knowledge to it. We can think of the knowledge as consisting of small programs that are applied to data. So we may conceptually divide the process of thinking into two steps (although they might be interwoven into a single unit in reality) that are occurring repeatedly: we select or construct a program, depending on the data or some part of it, and then we apply the program to the data or some part of it.

We can think of the first step as the result of a program that enumerates programs. We enter some data and out pops a program. In the mathematical model, the data is represented by its Gödel number, so the input consists of natural numbers. The programs that are generated are also taking natural numbers (Gödel numbers of input data) as their inputs and produce natural numbers (Gödel numbers of output data) as their output. We can imagine this as a table. Each column corresponds to a function (a piece of knowledge) or the program calculating this function. We may think of the program that produces these functions (or the programs calculating them) as a knowledge base or as a learning program producing new programs, or a combination of these.

We assume that the functions are total, i.e. no matter what data we put into such a function, some data will come out after some time (even if that is just an error message or a copy of the input or the the like). Our knowledge base does not contain functions that would run forever for some inputs, so that the computer would “hang”.

Think of a spreadsheet with infinitely many rows and columns. Each columns represents something we can do with data, i.e. a piece of knowledge we can apply to the data in some way. You may think of the numbers in each column as following some pattern described by the program calculating that column.

We are now going to prove that the set of programs calculating computable total functions (on natural numbers) is not enumerable. What this means is that every program we could write that produces such programs (i.e. every knowledge base or learning algorithm) is incomplete.

In order to prove this, we assume the opposite and derive a contradiction. The opposite (negation) of the statement we want to prove is that the set of all programs calculating total functions on natural numbers is enumerable. So we assume that a program is possible that takes the natural numbers as its input and produces as its output all programs calculating total functions. So we could have something like a universal knowledge base. The input would be any data (represented by Gödel numbers). The program would be able to produce any possible program (piece of knowledge) for some input.

Let us call this program K. For inputs 1, 2, 3, etc. it produces programs k1, k2, k3 etc. calculating total functions. For every program producing a total functions, there is some natural number n so that kn is that program.

You may imagine this as a table, something like an infinitely large spreadsheet. Each column in the spreadsheet corresponds to one function kx. The fields in each row of that column contain the values of the function. So in column x, row y, you will find the value that program kx calculates for input y.

Now we use K to produce a new program calculating a total function. This program works the following way:

  • For an input number n, the program kn is produced by applying K to n. This program kis applied to n. To the result, we add 1.

If K is a program, one can write a program that acts like this, so this rule describes a program calculating a computable function. It will yield a result for every input since there is a kn which in turn is computable.

You may have noted that this program will take the diagonal of our table. For 1, it gets the value in column 1, row 1. For 2, the value in column 2, row 2 etc.

It then adds 1 to whatever it finds in that square.

Now we have assumed that K is complete. Since the newly defined function is total, there must be some column in our table that contains exactly that function already. Let us say this column has the number m.

The diagonal function goes through every column, so it also goes through column m. So what is contained in the field at column m, row m? What is contained there is the value of km(m), i.e. the value of applying km to m. And according to the definition of the function, it contains that value, plus 1. So we get km(m) = km(m) + 1. That, however, is impossible. There is no natural number that is equal to itself + 1 (If we subtract km(m) on both sides of this equation, we get 0 = 1, which is clearly false). So our assumption that K is complete is leading to a contradiction. This means that no program can exist that can enumerate all programs calculating total functions.

Note that this proof works because we are looking at total functions, so there must be some number in the m-m-square of the table.

Actually this proof, employing the proof method known as (Cantor’s) “diagonal method” is not only proving that every program enumerating programs calculating total functions is incomplete, it it also provides us with a method to construct a new program calculating a total function that could not be produced by K.

Note that instead of adding 1, we could have used any operation that guarantees that the result is not equal to the input. We know that for all numbers x, the result of calculating x+1 is not equal to x. We could have used any other function that, applied to any number, yields an output number different from the input number. For example, we could also add 2 instead of 1, and the proof would work just as well.

Of course, we can add this new program to our enumeration, e.g. by shifting all the columns by one place and adding it as a new column in front (or inserting it in any other position inside the table – we could write some program that chooses a position). This way, we can replace K by a new program K’ that produces one function more than K.

Of course, K’ is incomplete again: we can apply the same “take the diagonal and modify (e.g. add 1) the result”-method again (and again and again).

We can try to build this diagonalization trick into the program K, so that, for example, every second column will be generated this way. This is possible, but whatever we try, we will not make it to get a complete enumeration, no matter how sophisticated our scheme will become: we can always apply the same diagonal + modify operation “from the outside” and get another program and function not previously covered.

We have now reached the point where we can actually turn from mathematics and computer science to philosophy. I am going to start doing so in further articles.

(For a related article, see here.)

Advertisements

7 comments

  1. […] For a related article, see here. […]

  2. […] computable total function having natural numbers as inputs and outputs. The proof sketched here that the set of total computable functions of natural numbers is not enumerable can therefore be […]

  3. […] a previous article, I have sketched a proof that shows that the set of computable total functions (as well as the […]

  4. […] which a complete description in terms of a formal theory is impossible in principle. For example, the set of computable total functions is non-formalizable in this […]

  5. […] the article SKETCH OF A PROOF: COMPUTABLE TOTAL FUNCTIONS ARE NOT ENUMERABLE I have used the notion of “total functions”. What is so special about “total […]

  6. […] a previous article on this blog a proof was sketched showing the following about programs that compute total […]

  7. […] see why there always must be such a limit, let us now look back at the proof, sketched in a previous article, that total computable functions are not enumerable by an algorithm. What we have shown there is […]

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: