Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence

ffective procedures, regis-
ter machine programs, deterministic formal systems and computable
functions are all equivalent ways of speaking – they all specify the
same class of things.
9.2
GÖDEL CODING
We have seen that for any algorithm one can specify, we can design a
register machine program to compute it. The final aim for this chapter
is to specify a single register machine program which can itself
compute any algorithm. In other words, we want to specify a register
machine program which can emulate or instance any other register
machine program.
This means we are going to need some way of making register
machine programs suitable to be the input of another register
machine. Given that the inputs of register machines are natural
numbers, we are going to need some way to code register machine pro-
grams as natural numbers. Furthermore, this coding procedure needs
to be unique and e
ffective. In other words, as well as being algorith-
mic, the coding procedure must be such that any given register
machine program results in a unique code, and vice versa. The
procedure we are going to use is known as Gödel coding.
Kurt Gödel was a brilliant logician and mathematician who deliv-
ered some of the most important results in mathematical logic in the
twentieth century. Gödel’s incompleteness theorems, delivered in a
1931 paper, are arguably the theorems which are the most well known
by those who are not mathematicians or logicians, and simultan-
eously the least understood. There is, in fact, rather a lot of nonsense
written about the Gödel results in philosophy of mind.
88
  

---

Unfortunately, a proper understanding of the Gödel incomplete-
ness theorems, such that we might see how they are frequently misin-
terpreted in arguments against computationalism, would require
considerably more mathematical sophistication than one would expect
from the introductory reader to whom this volume is directed. Su
ffice
it to say, if you run across arguments against computationalism
employing these theorems, they should be taken with a grain of salt.
The method of Gödel coding is one of the very neat tricks Gödel
used to prove the Incompleteness Theorems. It facilitates reference to
elements of a formal system from within that system, which is pre-
cisely what we require. Fortunately for our purposes here, under-
standing the method of Gödel coding requires no more mathematical
sophistication than an understanding of the operations of multipli-
cation and exponentiation, and of the notion of a prime number.
The mathematical operations of squaring and cubing are examples
of exponentiation, which is the more general operation of raising one
number to the power or exponent of another. The expression a
b
is
evaluated by multiplying a with itself b times – a is the base and b is
the exponent.
A prime number is a number which has no factors other than itself
and 1. An interesting feature of primes – and a crucial one for our
purposes – is that every natural number can be uniquely expressed as
a product of primes. The proof of this is a little complicated so you’ll
have to simply take my word for it here. Furthermore, prime factor-
isation is algorithmic (there are a number of known algorithms).
Again the details are complicated so you’ll just have to take my
word here too.
So for any given natural number, we can e
ffectively and uniquely
determine its prime factors. The method of Gödel coding exploits this
by coding programs as exponents of primes.
Recall that a register machine program is a sequence of instruc-
tions of one of two forms – either the form I a b or the form D a b c.
For increment instructions we need to code three pieces of infor-
mation – that it is an increment instruction and the numbers a and b.
For decrement instructions we need to code four pieces of inform-
ation – that it is a decrement instruction and the numbers a, b and c.
So to code increment instructions, we use three prime numbers. We
begin with 2 which will indicate that the code is of an increment
instruction. We then multiply this by 5 raised to the power of a and 7
raised to the power of b.
To code decrement instructions, we use four prime numbers. We
begin with 3 which will indicate that the code is of a decrement
 
89

---

instruction. We then multiply this by 5 raised to the power of a, 7
raised to the power of b and 11 raised to the power of c.
To express this symbolically:
I a b is coded as 2 . 5
a
. 7
b
(where the . represents
multiplication) and
D a b c is coded as 3 . 5
a
. 7
b
. 11
c
(We will always leave these expressions in exponential form.)
Note that the code of an increment instruction will always be an
even number, the code of a decrement instruction will always be divis-
ible by 3, and any number which is not divisible by 2 or 3 is not the
code of any instruction.
If 
 stands for some instruction, then we will use #
 to refer to the
code of 
. So, to give a few examples:
if 


 I 2 3
then #


 2 . 5
2
. 7
3
if 


 I 7 4
then #


 2 . 5
7
. 7
4
if 


 D 3 8 5 then #
 
 3 . 5
3
. 7
8
. 11
5
if 


 D 2 6 3 then #
 
 3 . 5
2
. 7
6
. 11
3
and so on.