Basic Concepts 4  – Gödel Numbers

File:Kurt gödel.jpg

It is possible to define a mapping from arbitrary data into natural numbers and vice versa. There are many ways in which this could be done and I am going to explain just one here.

You might ask what this is good for. That is a good question. At the present moment I can only say that we are going to use this in our argumentation at a later time. Let me only hint at the motivation now, the details will be explained in later articles. What we are going to do is to prove some mathematical statements about total functions that have natural numbers as their inputs and outputs and that are computable. I am going to define in a later article what is meant by “computable”. Roughly speaking it means that one can write a program that computes the function. By mapping any kind of data to natural numbers, it will be possible to apply our mathematical results to arbitrary programs processing arbitrary types of data. So such a mapping will enable us to bring the abstract mathematical results back into the familiar world of programs processing things like texts and pictures.

In the previous article we have seen that, on a technical level of description, we can represent all kinds of data as sequences of ones and zeros. Now we can define a mapping from any kind of data into natural numbers in the following way:

We look at the coding of the data in binary form, as it is used by the computer. We could try to interpret these sequences of ones and zeros directly as (binary) numbers. However, there might be sequences with leading zeros for which such a mapping would not be unique. For example, the sequences 01 and 001, interpreted as numbers, would both have the value 1. So we have to find a way to get rid of leading zeros without losing any information (we want to be able to distinguish between sequences of binary digits that are distinguished only by leading zeros, and these sequences should map onto different numbers). One simple way of doing this is the following:

We replace each 1 by 2 and then each 0 by 1. Then we interpret the resulting sequence of ones and twos as a ternary number (i.e. a number in the number system with base three).

This way, we can map the binary data to a natural number in a unique way. No two binary sequences that are different would map onto the same number. Every ternary number that does not contain the digit 0 can be mapped back onto the corresponding binary sequence and thus onto the original data. In both directions, the mapping can be done by a computer program that is simple and fast. The test if a number is the number assigned to some binary sequence, and hence to some piece of data, can also be implemented as a fast computer program: the program just has to produce the ternary representation of the number and then check if the digit 0 occurs in it or not. If there is no zero, we can map the number back to a binary digit sequence by replacing 1s with 0s and then 2s with 1s.

We could define many other ways of mapping arbitrary data onto natural numbers in a unique way. What is important for our purpose here is to show that in principle, data can be mapped onto natural numbers. The resulting numbers might become very large, but that does not matter.

We call such numbers Gödel Numbers (you might pronounce this as “Godel”, although the actual vowel in German is a little bit different). They are named after the mathematician Kurt Gödel who first used this trick of mapping data (in his case: mathematical formulas) onto numbers in some mathematical proof, in a famous article published in 1931. A mapping from data onto Gödel numbers is sometimes called a “Gödelization” (sorry, I did not invent that word). The particular method Gödel used to create such numbers is not the one described above. It is a bit more complex and the calculation, especially the way back from numbers to data, is not as easy as the method shown above, but for his purpose (using the idea in a mathematical proof), this did not matter.

In mathematics, such mappings are often only used for mathematical formulas or for programs, but they can be used for arbitrary kinds of discrete, i.e. non-continuous data. This is always the case for data stored in ordinary computers (this discreteness is basically what we mean with the word “digital”.

A Gödelization must have the following features:

  • It must be unique in both directions, i.e. the same input always leads to the same output (i.e. Gödel number) and if two inputs are different, they must have different Gödel numbers. So for a Gödel number, there is only one piece of data that maps to it.
  • It must be computable in both directions, i.e. it must be possible to write a computer program that will calculate the Gödel number for a piece of data and another one that will calculate the data for a given Gödel number.
  • It is not required that every natural number is the Gödel number of something. However, it must be possible to check if a given natural number is a Gödel number or not. It must be possible to check this using a computer program that will yield the result (yes or no) for each natural number (i.e. the Gödel-numbers must be “decidable”).

The method of assigning numbers to data by translating their binary representations into ternary numbers clearly satisfies these conditions. Replacing the digits in one or the other direction is unique in both directions and even without defining the concept of computability in a rigorous way, it is intuitively clear that this simple operation can be done by a computer program.

In this scheme, natural numbers containing the digit 0 in their ternary representation are not Gödel numbers and this can easily be checked. Any programmer could easily write a program that checks this.

From a program that translates the Gödel numbers back into data, we could easily construct another program that would map any natural number into a piece of data, not just the Gödel numbers. One possible way of doing so is to replace all instances of 0 in a number by the digit 1. This way, we could map every number that is not a Gödel number onto a corresponding Gödel number (in many cases, several numbers would be mapped onto the same target number) and then map that Gödel number back to data. So it is possible to write programs mapping data to natural numbers and natural numbers to data.

We have now been talking about programs for some time already, so we have reached the point where we should take a closer look into what programs are – in the next article.

(The picture, showing the mathematician Kurt Gödel, is from https://en.wikipedia.org/wiki/File:Kurt_g%C3%B6del.jpg)

Advertisements

One comment

  1. […] whose inputs and outputs are natural numbers. We have seen in a previous article how the concept of Gödel numbers can be used to map arbitrary data into natural numbers and vice versa, so we do not actually lose […]

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: