Computability - Models of Computation: Exploring the Power of Computing - page 209

CHAPTER
Computability
The Turing machine (TM) is believed to be the most general computational model that can
be devised (the Church-Turing thesis ). Despite many attempts, no computational model has
yet been introduced that can perform computations impossible on a Turing machine. This
is not a statement about efficiency; other machines, notably the RAM of Section 3.4 ,cando
the same computations either more quickly or with less memory. Instead, it is a statement
about the feasibility of computational tasks. If a task can be done on a Turing machine, it is
considered feasible; if it cannot, it is considered infeasible. Thus, the TM is a litmus test for
computational feasibility. As we show later, however, there are some well-defined tasks that
cannotbedoneonaTM.
The chapter opens with a formal definition of the standard Turing machine and describes
how the Turing machine can be used to compute functions and accept languages. We then
examine multi-tape and nondeterministic TMs and show their equivalence to the standard
model. The nondeterministic TM plays an important role in Chapter 8 in the classification of
languages by their complexity. The equivalence of phrase-structure languages and the languages
accepted by TMs is then established. The universal Turing machine is defined and used to
explore limits on language acceptance by Turing machines. We show that some languages
cannot be accepted by any Turing machine, while others can be accepted but not by Turing
machines that halt on all inputs (the languages are unsolvable). This sets the stage for a proof
that some problems, such as the Halting Problem, are unsolvable; that is, there is no Turing
machine halting on all inputs that can decide for an arbitrary Turing machine M and input
string w whether or not M will halt on w . We close by defining the partial recursive functions ,
the most general functions computable by Turing machines.
209