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

Exercise 9.1
Code the instruction bodies of the solutions to the exercises in
chapter eight. (Disregard the line numbers for the moment –
just code the instructions.)
Now that we know how to code instructions, we are going to use
exactly the same procedure to code entire programs.
A program is some number n of lines consisting of a line number
and an instruction. To simplify things, we make the assumption that
lines are numbered in the sequence of natural numbers beginning
from 1. When we decode program codes into their constituent
instruction codes, we simply enumerate them in the same sequence.
This allows us to disregard line numbers in codes.
Given a sequence of n instructions, we can code this by simply mul-
tiplying the first n primes, each of which is raised to the exponent
which is the code of the relevant instruction. So the first prime is
raised to the exponent which is the code of the first instruction, the
second prime is raised to the exponent which is the code of the second
instruction, and so on.
To express this symbolically:
90
  

---

given a program 1 

1
, 2 

2
, 3 

3
, . . . , n 

n
it can be coded as 2
#
1
. 3
#
2
. 5
#
3
. . . p
#
n
(where p is the
nth prime).
This might seem rather complicated but some examples will serve to
show that it is actually very straightforward. We always simply leave
the expressions in their exponential form and we assign variables to
stand for instruction codes to make things easier to read, as the exam-
ples below illustrate.
The program:
1 D 3 1 2
2 D 1 3 5
3 D 2 4 5
4 I
3 2
is coded as:
2
a
. 3
b
. 5
c
. 7
d
where:
a

 3 . 5
3
. 7
1
. 11
2
b

 3 . 5
1
. 7
3
. 11
5
c

 3 . 5
2
. 7
4
. 11
5
d

 2 . 5
3
. 7
2
The program:
1 D 3 1 2
2 D 4 2 3
3 D 1 4 9
4 D 2 5 7
5 I 3 6
6 I
4 4
7 D 4 8 3
8 I 2 7
9 D 3 10 12
10 I 1 9
is coded as:
2
a
. 3
b
. 5
c
. 7
d
. 11
e
. 13
f
17
g
. 19
h
. 23
i
. 29
j
where:
a

 3 . 5
3
. 7
1
. 11
2
b

 3 . 5
4
. 7
2
. 11
3
c

 3 . 5
1
. 7
4
. 11
9
 
91

---

d

 3 . 5
2
. 7
5
. 11
7
e

 2 . 5
3
. 7
6
f

 2 . 5
4
. 7
4
g

 3 . 5
4
. 7
8
. 11
3
h

 2 . 5
2
. 7
7
i

 3 . 5
3
. 7
10
. 11
12
j

 2 . 5
1
. 7
9