I was looking at Gödelization in Theory of Computation course. I could understand the Gödel numbering concepts, but couldn't understand its importance in Theory of Computation. Could anyone please point to some good materials or point out its importance.


Gödel numbering in computer science means more or less "source code" and "data in binary format", so I hope the significance of this should be obvious if I can convince you that this really is so.

Before modern computers came into existence, people made single-purpose computing devices (I am telling you a story, not a history), for example someone made a machine for calculating $arctan$, and someone else made a machine for calculating the Bessel function. Turing's original insight was that we only had to build one machine (the universal one), which took as input the description of any machine and simulated it. But what is a "description of a machine"? An engineer might think of circuit designs and assembly instructions. But that is very complicated and not easily presented to a machine. And perhaps ever more complicated machines require ever more complicated descriptions?

We need a way of describing machines that is as simple as possible. Here Gödel's idea was important: he showed some years before Turing that all sorts of things in logic (formulas, proofs) could be encoded with numbers, and then manipulated within arithmetic. We can do a similar trick with Turing machines: encode the program, the current state, and the contents of the tape used so far, with a string of symbols on a tape (for examples $0$'s and $1$'s), and then manipulate the string with a Turing machine.

In practice we do not write down sequences of $0$'s and $1$'s when we program. We use another layer of encoding and write "source code" which is translated to $0$'s and $1$'s (the "machine code") by compilers. But in fact early computer scientists did write down $0$'s and $1$'s directly by flipping switches. That was Gödelization in its pure form.

In practice we represent programs and data in a variety of formats known as .java, .py, .mp3, .jpg, etc. In logic and theory of computing people prefer to stick with the good old numbers because they are more easily manipulated within mathematics.

Nowadays everybody knows that "computers do everything in terms of $0$'s and $1$'s". This fact has become so familiar that it is hard to appreciate its originality. Many years ago, when no modern computers existed, it was far from obvious that machines, text, music, pictures and movies could all be encoded with numbers, or sequences of $0$'s and $1$'s.

  • $\begingroup$ This is super clear. Where could I get some technical materials on these? $\endgroup$ – user5507 Nov 25 '12 at 16:02
  • $\begingroup$ What does "on these" refer to? $\endgroup$ – Andrej Bauer Nov 25 '12 at 19:13
  • $\begingroup$ Sorry for my vague english. I was looking for some materials containing proof on Godelization in Turing machine. Can you also please tell me about the significance of godel numbering here. (Generating a sequence from a number ) $\endgroup$ – user5507 Nov 26 '12 at 1:47
  • $\begingroup$ Martin Davis's book "Computability and Unsolvability" has a very detailed treatment of Turing Machines, perhaps that is what you are looking for. I am not sure what it is that you are asking for. $\endgroup$ – Andrej Bauer Nov 26 '12 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.