4.4 Church-Turing Thesis 191
4.4 Church-Turing Thesis
From the equivalence results of the last section, it is plausible to conjecture
that any other reasonable modifications of the Turing machine model will not
change the computational power of Turing machines. In fact, it is commonly
believed that almost all reasonable computational models can be simulated by
multi-tape DTM’s. For instance, consider Rundom Access Muchines (RAM’s)
which are close to our real-world digital computers.
A RAM contains a read-only input tape, a write-only output tape and an
infinite number of registers, named Ro, 81,.... Each cell of the tapes and
each register can store a nonnegative integer of an arbitrary size. The control
unit of the RAM can perform the following operations on integers stored in
its registers: read, write, add, subtract, multiply, divide, copy, and compare.
In addition, it can access a constant integer or to perform these operations by
the indirect addressing scheme. For instance, in a program of an RAM, one
may use an instruction like ADD@, R3, Ral), in which integer 5 means using
the constant 5 as the first operand, R3 means using the content of register R3
as the second operand, and Ral means to store the sum of constant 5 and the
value 213 in register R3 in the register R,,, where ~121 is the current content
of R21 (thus, an indirect addressing is used here). It is not too hard to show
how a multi-tape DTM can simulate a RAM. We now give a sketch.
First, we require that when a RAM begins the computation, all registers
cant ain value zero. Thus, at any time during computation, a RAM has at
most a finite number of nonzero registers. A multi-tape DTM can reserve
one of its tapes, say tape 2, to simulate the contents of all nonzero registers.
For instance, the following tape configuration represents the configuration of
the RAM in which registers Ri has the values vi, for i = 0, 1,... , m., and all
registers Rj, with j > m, have value 0:
... BB$BlwoBlv1Blw2B l l .Bl’“BBB l l l
From this tape information, it is easy to find the content of register Ri: it is
equal to the number of l’s between the (i+l)st and the (i+2)nd blank symbols
B to the right of the special marker $. Thus, to simulate an instruction of the
RAM, for instance, ADD@, R3, Ral), a multi-tape DTM first writes 5 and the
contents of R3 on tapes 3 and 4, respectively, and then adds them and puts
the sum on tape 5. Next, it searches for the 22nd B in tape 2 to get 2121 and
puts it in tape 6. Then, it searches for the (112r+ 1)st B in tape 2 and replaces
the following block of l’s by the block of l’s in tape 5. Note that if the sum
is different from the original value in R,,, , we need to move the rest of the
contents of R,,,+l,... , Rm to the right or to the left. This is similar to the
function insert’ of Exercise 4(c) of Section 4.2.
Historically, a number of different types of computational models have been
proposed and studied. It turns out that almost all of them have been found
to have the same computational power as Turing machines, in the sense that
the class of computable functions defined by each proposed model is exactly