Gödel Numbering

Our main goal in this course is to show that some problems are hard, for example, not recursively decidable. To do that, we'll find one hard problem and do all the others by showing that if they were easy the hard problem would be easy, that is, by showing how to solve the hard problem using a solution to the new problem.

To get started then, we need one hard problem. (Actuallly, we'll use two closely related ones for convenience.)

The problem is the Halting Problem: given a register machine, determining whether it halts. To show that that problem is hard (that is, not decidable) we must turn it into a problem of our favored type: one involving strings of symbols. Register machines process strings of symbols, but now we want to recode register machines so that they are themselves strings of symbols. That will allow us to apply register machines to register machines.

The first proof that a problem is hard, due to Gödel, showed that the theorems of an axiomatization of arithmetic are not decidable. To do that, he needed to talk about theorems of arithmetic in arithmetic, apply arithmetic to arithmetic just as we will apply register machines to register machines. He did it by associated each symbol in the language of arithmetic with a number and sequences of them with other numbers: %$0=0$%, for example, became %$2^{n(0)}3^{n(=)}5^{n(0)}}$%, where %$n$% is the function that takes a symbol to its number. These are called Gödel numbers. By extension, any technique for using a system of procedures to talk about that very system is called a Gödel numbering.

So, how do we Gödel number register machines?

In an obvious alphabet, the Gödel number of the machine
0 PRINT
1 GOTO 0
2 HALT
could be
0PRINT%$\S$%1GOTO0%$\S$%2HALT%$\S$%

The above string is a perfectly adequate Gödel number for the machine, except for one minor detail: it is not in the original alphabet. It will be convenient not to have to shift back and forth between alphabets, and so we adopt the following minor bit of trickery: Every useful alphabet has at least one symbol, say %$a_0$%. We arrange the strings in the alphabet used above to Gödel number machines in lexicographical order. That way, each such string is associated with a number--its position in the order. Given any machine, we code it as above, find out what position (number) in the order just given that code occupies, say, %$n$%, and we then use a string of %$n$% %$a_0$%s as the official Gödel number for the machine. That is, of course, terribly inefficient, but when all we are interested in is the existence of any procedure at all, efficiency is not an issue. From now on I shall only refer to the string of %$a_0$%s as the Gödel number.

End of story.

Now any set of machines corresponds to a set of codes (Gödel numbers) for those machines.

The halting problem is the set of codes that code machines that halt.

To show that the problem (the set) is undecidable, we will, assuming we have a machine that solves the problem, build a machine out of it that halts if the machine says it does not ... . This is like a machine that says "I halt if the test says I don't." The "self-reference" is critical to the construction.

Quine says that Gödel's sentence, which is usually rendered "I am not provable" is actually more like this:

"Yields when appended to the quotation of itself an unprovable sentence" yields when appended to the quotation of itself an unprovable sentence.

---

We adopt the following notation: Given an alphabet %$\mathcal{A}$%, we use the variable %$\zeta$% to range over strings from %$\mathcal{A}$%, that is, members of %$\mathcal{A}^*$%. We fix a member %$a_0$% of %$\mathcal{A}^*$% to use to code machines. Given that, we write %$ \xi_P$% for the Gödel number of the register machine, or program, %$P$%. Thus, %$\zeta =\xi_P$% if and only if %$\zeta$% is the Gödel number of the program %$P$%. We reserve the letter %$\mathcal{P}$% for procedures, in the intuitive sense of the term. Thus, Church's thesis is that for every procedure %$\mathcal{P}$% there is a program %$P$% that implements it. I am intentionally leaving the idea of implementation vague, since there are many possible variants, but all agree that, at a minimum, %$P$% must produce the same results (outputs, halting or not) as %$\mathcal{P}$%, and that that can be informally demonstrated.

Homework 3:Problems 2.9--2.12, p. 162. Due 11 February.

-- ProfessorShaughanLavine - 02 Feb 2005