Kurt Gödel is famous for his proof that any formal system which is complicated enough to include elementary arithmetic (or something isomorphic, that is, essentially equivalent, to elementary arithmetic) as part of it, can express statements which, although in fact true within the rules of the system, cannot be proven by it.
The technique of Gödel-numbering figured importantly in the proof. A formal system is, essentially, a branch of mathematics, like geometry or set theory, but one that is strictly limited by a fixed set of rules. One set of rules governs the statements we make about the subject matter of the system, and how a valid proof can be constructed. These are the rules of logic, which generally are the same for all branches of mathematics. Another set concerns the subject matter itself, such as the definition of multiplication, or the postulates of Euclidean geometry.
Gödel-numbering converted mathematical proofs into numbers, so that statements about proofs were also statements about numbers.
Today, with computers storing mathematical documents as sequences of ASCII characters, it is obvious that anything written can be represented as a number. However, Gödel used a special technique for representing a series of characters as a number, which made it more convenient to convert the rules of mathematical deduction into arithmetical operations.
A code was used to convert mathematical symbols into numbers, starting from 1. However, instead of just concatenating those numbers into a long string of digits, instead the number representing a string of symbols was the product of consecutive prime numbers, each one raised to the power representing one fo the symbols in the string.
Later, Alan Mathison Turing proved that it is impossible to write a computer program that can read another computer program, and, if that program will run forever without stopping, tell us, after some finite (but unbounded) time this fact.
This proof is based on the fact that every computer program is a finite string of symbols (although of unbounded length: for any program, one can find a larger, but still finite, one), and from a finite alphabet (or an alphabet of cardinality aleph-null, but finiteness can be assumed without loss of generality, since delimited strings of unbounded length composed of characters from a finite alphabet can represent the elements of an alphabet with aleph-null symbols). Hence, any program can be coded so that it can be represented by some positive integer.
What we desire is a program that states, in some finite time, when given a program that will not halt that, in fact, this is a program that never halts. If such a program exists, it could have a pre-processing step added to it so that it accepted programs as input for consideration in the form of the positive integer which represents it.
Also, note that such a program could be incorporated into a program that spent part of its time running the program that was submitted to it, so that it would halt and report whether or not the program given to it as input halted or was proved never to halt. Or, it could be designed so that if it finished looking for a proof that a program would never halt, and found none, it would go into an infinite loop and never halt itself. It is this latter form of the program we are concerned with.
(As this is a classic proof, if you happen to have read a bit about modern mathematics, you may well already know what comes next...)
Now, then, we submit to this form of the program the integer that represents itself.
Actually, this step involves cheating a bit. Here, we have distinguished between a "program" and its "input", and noted that a program might halt or not halt, depending on properties of its input. If so, there won't be a single answer for a great many programs. Obviously, then, to talk about determining for a number n whether or not it represents a program that halts, we need to disallow any additional input.
This is simple enough to do: programs requiring input would then be represented by many different programs: for each possible input, there would be a version which began with a program to write that sequence of input in an area of memory, and then runs a version of the original program that reads its input from that area of memory.
A program that takes its entire text as input is possible, since the storage containing the program itself can be read and copied somewhere.
But what you now have is a program that will halt if and only if it does not halt. Given n as input, it halts if program n does not halt, and goes into an infinite loop if n does not halt. But it _is_ program n. Since having a program that tells us when programs don't halt allows us, through trivial transformations we know are possible, to create this impossible program, we can't possibly have such a program.
At the time Turing composed this proof, computers did not even exist. For the purpose of the proof, he designed a computer architecture that was as simple as possible, although very inefficient, to make it simple to carry out the detailed steps of the proof that I have not dealt with here. This design is, of course, the famous Turing machine.
A Turing machine is a computer with two kinds of memory: an infinite tape, containing cells which can contain a mark, or be blank, and an internal state which can have one of several values.
The program of a Turing machine consists of a list of things to do for each of the internal states for two cases: when the one cell of the tape currently being examined contains a mark, and when it is blank. For each of those combinations, it is specified whether the machine halts, or:
Turing was also able to prove that a Turing machine with a certain minimum number of states could be given a program that would let it operate on a tape with a different kind of program, written on the tape, that described a Turing machine with a larger number of states, and carry out any calculation that that larger Turing machine could do, although perhaps by using part of the tape (such as only the even cells) to simulate the tape of the other machine. Thus, it couldn't necessarily write the same specific patterns on the tape as the other machine, but it could write an equivalent pattern which was the same except for a trivial transformation. Thus, it could solve the same problems, which was what was important. A Turing machine with enough states, and the internal program that allowed this to be done was called a Universal Turing Machine.
But the Turing machine was really only needed for the preliminary part of the proof, to establish that such things as computers could exist, and it made sense to talk about what they could do. The rest of the proof, what I recounted above, works for any kind of computer that has the same basic properties as a Turing machine, even if it is much more efficient, because it is organized like a conventional computer.
One could think of an ordinary PC, with the addition of an infinitely long rack of floppy disks, and a mechanism to move that rack, perhaps by distances indicated by 32-bit integers at any one time, and load and unload disks from it into the computer's floppy disk drive. This is still halfway like the Turing machine, in that a finite machine is manipulating an infinite external memory, although now long stretches of computation could take place between proceeding to another floppy disk.
An even simpler abstract computer would simply be one which directly performs arithmetic to arbitrarily high precision, and which has an infinite amount of RAM. Such a computer could also be simulated by a computer operating along more Turing-like principles.
For simplicity in representing any program for that computer as an integer, we will have its memory composed of single decimal digits, individually addressable.
Let it represent numbers in two forms: in the normal fashion, as strings of digits, which will require auxilliary information about where the number ends as well as begins, and in a coded fashion allowing numbers to indicate themselves where they terminate:
01 = 0 02 = 00 03 = 000 04 = 0000 05 = 00000 06 = 000000 07 = 0000000 08 = 00000000 09 = 000000000 00 = END OF NUMBER
Strings of more than nine zeroes would just be represented by one or more 09 codes, followed, if necessary, by a code for any odd zeroes.
The opcodes for the computer would be:
1 Jump to location (op1)
2 Add number at (op1) to number at (op2), storing result in (op3)
3 Subtract number at (op2) from number at (op1), storing result in (op3)
4 Multiply number at (op1) by number at (op2), storing result in (op3)
5 Divide number at (op1) by number at (op2), storing result in (op3)
6 Compare number at (op2) to number at (op1), jumping to location
(op3) if it is smaller, (op4) if they are the same, and (op5) if it
is bigger
Each operand would start with a single digit, giving its form:
0 The operand is a coded number, used as an immediate value.
1 The operand consists of a coded number, giving a number of digits,
followed by that many digits, used as an immediate value.
2 The operand is a single digit, followed by a
coded number, referring to memory containing the value to use.
3 The operand is a single digit, followed by a
coded number giving a number of digits, followed by that many
digits, used as an address referring to memory containing the value to use.
The single digit following a 2 or 3 can itself be 0, 1, 2, or 3. If it is a 1 or a 3, the length of the next part of the operand is included in the instruction as a coded number. If it is a 2 or a 3, indirect addressing is being used, and the 2 or 3 is again followed by 0, 1, 2, or 3, and so on.
For example, the instruction (with spaces present only for clarity):
2 20 10100 0 01500 231 301200 400 1500
does the following:
2 add to
20 the number found in memory location
10100 ten (10)
0 the constant
01500 five (5)
231 and store the result
301200
400
1500 as a fifteen (15) digit number
in the memory location pointed to by the four (4) digit number (from 400)
found at memory location three hundred and two (302) (from 301200)
The only thing not yet described is how negative numbers are represented. The rule will be that if a number begins with a digit from 5 to 9, it represents a negative number in ten's complement notation. Therefore, a positive number starting with a digit from 5 to 9 must be preceded by at least one leading zero, which is why 01500 was used to represent 5 above instead of 500, which represents -5.