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

rules are.
Register machines have only one rule. This rule takes a special form
and is called a program.
A register machine program is a finite number of lines, each of
which have two components: a line number and an instruction. Line
numbers are simply natural numbers, assigned to facilitate reference
to lines of the program. Each line must be assigned a unique line
number. These are conventionally consecutive for readability, but
need not be. Instructions take one of two forms: they are either incre-
ment instructions or decrement instructions.
An increment instruction is something of the form I a b, where the
I stands for ‘increment’ and the a and b are numerical variables – they
stand for natural numbers. A decrement instruction is something of
the form D a b c, where the D stands for ‘decrement’ and, as with
increment instructions, the lower case roman letters are numerical
variables.
Recall that there must be e
ffective procedures for both determining
whether a rule applies to a state of a formal system and for applying
rules to states of formal systems.

71

---

The e
ffective procedure for determining whether a register machine
program applies to a given register machine state is as follows:
1. Examine the contents of R
0
(this first register is always set aside for
this purpose and is referred to as the program counter or pc).
2. If there is no line of the program which begins with the number in
the pc then the program does not apply to the state.
3. If there is a line of the program which begins with the number in
the pc then the program applies to the state.
The e
ffective procedure for applying a register machine program is as
follows:
1. If the line of the program which begins with the number in the pc
contains an increment instruction (I a b), then increment (add one
to) R
a
and put b in the pc.
2. If the line of the program which begins with the number in the pc
contains a decrement instruction (D a b c), then decrement (take one
from) R
a
and put b in the pc. If R
a
is already empty (contains zero)
then do nothing except put c in the pc.
The instruction forms I a b and D a b c are precisely that: forms.
Register machine instructions are instantiations of these forms.
Instantiated forms assign values to variables – in this case natural
numbers to the numerical variables. So examples of actual lines of a
register machine program look like this:
1
I
1
2
2
D
3
4
3
Line 1 instructs us to increment R
1
then put 2 in the pc (R
0
). Line 2
instructs us to decrement R
3
if we can then put 4 in the pc, otherwise
(if R
3
is empty) just put 3 in the pc.
So, when looking down the lines of a register machine program, the
numbers in the first column after the instruction letters refer to regis-
ters – they tell us which register to increment or decrement. The
numbers in the next column tell us which number to place in the pc
after successfully executing the instruction. Numbers in the third
column (which only appear in decrement instructions) tell us which
number to place in the pc if we cannot execute the instruction.
Registers can always be incremented as there is no largest natural
number. They cannot, however, always be decremented. The contents
of registers are natural numbers not integers. The natural numbers
include zero and the positive integers. If a register contains 1 it can be
72
  

---

decremented once more then we say the register is empty. An empty
register cannot be decremented. One can’t take something away from
a pile of nothing.
We can amalgamate the e
ffective procedures for determining pro-
gram applicability and applying a program into a single algorithm for
running a program, as follows:
1. Look in the pc.
2. If there is no program line beginning with this number then halt.
3. If there is a program line beginning with this number, execute the
instruction on that line.
4. Repeat.
So running a program simply involves repeated applications of first
determining whether the program applies to the current state and
then executing the relevant instruction until the program is no longer
applicable (until there is a state with a number in the pc which has no
corresponding program line).
8.3 RUNNING A PROGRAM
Now that we know what register machine states are and what it is to
run a register machine program, let’s examine the operations of a
simple register machine. Consider the following program:
[ADD]
1
D
2
2 3
2
I
1
1
Let’s exemplify the operations of this simple program and try to
determine what it does. We know by looking at the first column after
the instruction letters that there are only two registers referred to in
this program – R
1
and R
2
. So let’s apply this program to an initial state
which has contents in these two registers, let’s say 3 in R
1
and 2 in R
2
.
Let us also suppose that our initial state contains 1 in R
0
(the pc) –
this is conventional as it ensures that the first thing to happen will be
the execution of line 1 of our program.
This initial state is represented on the first line of Figure 8.1. Each
line below the initial state represents the resultant state of one appli-
cation of the program.
When the program [ADD] is run with the initial state described, the
sequence of operations will be as shown in Figure 8.1.

73

---

If you have your pile of tokens handy, pull them out now and
arrange three piles to represent the initial state in the example above.
Now, let’s work stepwise through the example. We will simply be
applying the algorithm for running a program which I described at the
end of section 8.2.
The first thing we do is look at the contents of R
0
(the pc) in the
initial state. It contains 1 and there is a line of the program which
begins with 1 so we execute the instruction on line 1. Line 1 contains
a decrement instruction – it tells us to decrement R
2
(which leaves 1
in R
2
) then put 2 in the pc. The resultant state of this first application
is represented on the line below the initial state in Figure 8.1. To be
explicit, we now have 2 in the pc, 3 in R
1
and 1 in R
2
.
74
  