Turing Machines
Table of Contents
-
- The fundamental issue we will focus on for the remainder of
this course are problems and problem solving methods or algorithms.
- The purpose of this unit is to discuss the following
ideas.
- The Turing machine model :
A formal model for representing
algorithms.
- Church's Thesis:
This thesis states that any algorithm can be represented as
a Turing machine.
- Universal Turing machines:
A Turing machine which acts like
a modern general purpose computer in that it can "run"
other Turing machines and thus solve any problem which can
be solved by Turing machines.
- Undecidability:
A formal proof that natural, important
problems such as the halting problem are "undecidable"
or unsolvable.
-
- M = (Q,
,
,
q0,
,
h)
- Note I have added the halt state h as an extra element
of the definition of a Turing machine.
- I'm not going to cover here all the definitions as they are
covered in the book, but please make sure you understand the
following list of concepts related to a Turing machine.
- What a configuration of a Turing machine is.
- What the initial configuration of a Turing machine on an input
string x is.
- The fact that Turing machines can compute functions as well
as decide/recognize languages.
- The language accepted by a Turing
machine (page 284).
- The language decided by a Turing
machine (page 294).
- The difference between the two
previous concepts of accepting a language and deciding a language.
-
- Church's Thesis states that any algorithm can be realized
as a Turing machine.
- That is, any algorithm which you implement using the C++ or Java
programming languages can also be implemented using Turing
machines.
- The importance of this thesis is as follows:
- First, we will prove that certain problems
cannot be solved using Turing machines.
- If Church's Thesis is true, this implies these same problems
cannot be solved using any computer or any programming
language we might ever develop.
- Thus, in studying the fundamental capabilities and limitations
of Turing machines, we are indeed studying the fundamental
capabilities and limitations of any computational device
we might ever construct.
- Can Church's Thesis ever be proven correct?
- Not really. To prove it correct,
we would need to prove that for all
possible models M of algorithms, any algorithm that
can be represented in model M can also be represented as
a Turing machine.
- Instead, we will provide evidence that Church's Thesis is
correct as described in the following section.
-
- In this section, we give evidence that Church's Thesis
is correct by considering several alternate formal models of algorithms
and show that they are equivalent
to the Turing machine model.
- The Basic Technique
- We will formally define an alternative model AM
- Possible example models include Turing machines with multiple tapes and
C++ programs.
- We will show that model AM is equivalent to our basic
Turing machine model as follows:
- For every machine or program M1 in
model AM, there exists a Turing machine M
such that L(M1) = L(M).
- For every Turing machine M,
there exists a machine or program M1
in model AM
such that L(M1) = L(M).
- We achieve the above two steps by employing constructive
proofs very similar to examples we've seen before
- Theorem 12.1 where we showed that any PDA which accepts by
final state can be converted into a PDA which accepts by
empty stack and accepts the same language.
- Theorem 5.2 which shows that any NFA can be converted into
an FA which accepts the same language.
- Key point
- Note in each case we are not creating
a new machine from scratch.
- Rather, we are modifying an existing
machine in a different model to do essentially the same thing
in our current model.
- Example Summaries
- Turing machines with 2-tracks on their input tape
- The basic idea is that to simulate a 2-track TM with an ordinary
TM, we need a bigger tape alphabet.
- Turing machines with a 2-way infinite tape
- Section 17.1.
- The basic idea is to simulate a 2-way infinite tape TM with
a 2-track TM by wrapping the "left end" of the tape onto
the second track.
- Turing machines with multiple tapes (some fixed number n)
- Section 17.2.
- The basic idea is to simulate an n-tape TM with
an n-track TM where track i holds the contents
of tape i.
- The cells for track i also need to mark where the tape
head for tape i is located.
- To simulate one move an n-tape TM, the n-track
TM needs to
- Collect the tape head information from each track.
- Given this information and the current state, decide on
how each track needs to be updated.
- Implement the update on each track.
- Note each single transition of an n-tape TM requires
many transitions from the normal TM.
- There exists a specific Turing machine U which we call
a universal Turing machine.
- We say that U is universal because it can "execute"
or "simulate" any other Turing machine.
- That is, if we use the notation that M(x) is the
result of executing Turing machine M on input x,
then there exists a Turing machine U such that
U(M,x) = M(x).
- Comments
- Note, U is a specific Turing
machine, not a new computational model such as multi-tape
Turing machines.
- U is a fairly simple Turing machine:
- It does exactly what you do when I ask you to simulate
a Turing machine on an input; nothing more, nothing less.
- It simply follows instructions.
- The specific Turing machine in the book is actually a
3-tape Turing machine, and it can simulate any normal
1-tape Turing machine on any input x.