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

Exercise 8.7
Design a register machine program which computes the
function f (x)

 2x
2
– 1 (The solution to this one is up to you.)
82
  

---

Before we move on, there are a few points of interest to draw from the
material we have covered so far in this chapter.
We have now looked at register machine programs which can copy
the contents of registers, compute addition and multiplication, and
compute squaring in two di
fferent ways. The latter way of computing
the squaring function involved generating, and accumulating, terms
of a series.
All this has been built up from a very sparse set of basic resources –
increment instructions and decrement instructions. We can see how
these could be built up further into rather more complex computa-
tions – programs which implement highly complex algorithms. This
is a notion we will revisit in Chapter 10.
Another point of interest is the demonstration that there can
be more than one way of computing a function. In fact, very
complicated functions are likely to be computable by a large
number of algorithms. This is another notion we will revisit in
Chapter 10.
In the following chapter, we are going to see how to use Gödel
coding to facilitate reference to programs within programs. Using this
method, we will see precisely how much can be achieved using only
increment instructions and decrement instructions.
First, however, here is a final challenge exercise for those whose
interest has been piqued.
Exercise 8.8 (Challenge)
We have seen how to accumulate the terms of a simple series.
Rather than accumulating the terms, we could easily modify
the program so as to return the nth term (where n is the input
of the function), in other words to terminate with the nth
odd number in R
1
rather than the sum of the first n odd
numbers.

83