Gödelization in Turing Machine

Problem Detail: 

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.

Asked By : user5507

Answered By : Andrej Bauer

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6883