192 TURING MACHINES
the same as the class of Turing-computable functions. In general, we
a computational model reasonable if it has the following properties:
may call- The computation of a machine is given by a finite set of instructions.
- Each instruction can be carried out in this model in a finite number of
steps, or in a finite amount of time. - Each instruction can be carried out in this model in a deterministic
manner so that the effect of the instruction is predictable.
Suppose a computational model is reasonable. Then, intuitively, we could
simulate such a model by a Turing machine. This is called the Church-Turing
Thesis.
Church-Turing Thesis. A function computable
tional model is computable by a Turing machine.in any reasonable compu ta-Note that we cannot prove the Church-Turing Thesis as a theorem, as
we cannot predict what types of computational devices people may invent
and whether these new devices may be more powerful than Turing machines.
So, we have to accept (or reject) the Church-Turing Thesis from the empir-
ical studies. Once it is accepted on the empirical ground, however, we find
it extremely useful in the theoretical study. Specifically, it provides a fixed
computational environment to study the notion of computable functions. For
instance, when we want to argue that a given function is computable, we do
not need to prove this by constructing a Turing machine that computes it.
We may simply use an algorithm in a more convenient model to describe how
to compute it and rely on the Church-Turing Thesis to convince ourselves
that this algorithm can be converted to an equivalent Turing machine. Con-
versely, if we want to prove that a function is not computable, we prove this
in any reasonable model and argue, using the Church-Turing Thesis, that it
is actually not computable at all, no matter which computational model is
used.
In the above, we have seen that Turing machines can simulate multi-tape
Turing machines and RAM’s, These simulations provide some evidence for
the Church-Turing Thesis. To further demonstrate the plausibility of the
Church-Turing Thesis, we will consider, in the rest of this chapter, two other
notions of computability based on machineries of very different natures and
show that they are equivalent to the notion of Turing-computability.
Exercises 4.4
- We present RAM’s in more detail. A RAM is defined by a list of in-
structions, numbered from 1 to n. An instruction is of one of the types
shown in Figure 4.17. (Note: We only list the instructions in the form of
using direct addressing. As discussed in the text, they can also use con-
stants or indirect addressing.) Initially, all registers of a RAM contain