Outline of Turing Machines and Complexity
Outline of Turing Machines and Complexity
Outline of Turing Machines and Complexity
1
We prove there is no C program to solve that
problem by supposing that there were such a
program H , the \hello-world-tester."
✦ H takes as input a C program P and an
input le I for that program, and tells
whether P , with input I , \prints hello
world" (by which we mean it does so as
the rst 13 characters).
Modify H to a new program H1 that acts like
H , but when H prints no, H1 prints hello,
world.
✦ Requires some thought: we need to
nd where no is printed and change the
printf statement.
Modify H1 to H2. This program takes only
one input, P , and acts like H1 with both its
program and data inputs equal to P .
✦ I.e., H2(P ) = H1(P; P ).
✦ Requires more thought: H2 must buer
its input so it can be used as both the P
and I inputs to H1.
H2 cannot exist. If it did, what would H2(H2)
do?
✦ If H2(H2) = yes, then H2 given H2 as
input evidently does not print hello,
world. But H2(H2) = H1(H2; H2) =
H (H2; H2), and H1 prints yes if and only
if its rst input, given its second input as
data, prints hello, world. Thus, H2(H2 )
= yes implies H2(H2 ) = hello, world.
✦ But if H2(H2) = hello, world. then
H1(H2; H2) = hello, world. and
H (H2; H2) = no. Thus, H2 (H2) =
hello, world. implies H2(H2 ) 6= hello,
world.
The TM
Finite-state control, like PDA.
One read-write tape serves as both input and
unbounded storage device.
✦ Tape divided into cells.
✦ Each tape holds one symbol from the tape
alphabet.
✦ Tape is \semi-innite"; it ends only at the
left.
2
Tape head marks the \current" cell, which is
the only cell that can in
uence the move of
the TM.
Initially, tape holds a1a2 an BB where
a1 a2 an is the input, chosen from an input
alphabet (subset of the tape alphabet) and B
is the blank.
Formal TM
M = (Q; ; ,; ; q0; B; F ), where:
Q = nte set of states.
, = tape alphabet; , = input alphabet.
B in , , = blank.
q0 in Q = start symbol; F Q = accepting
states.
takes a state and tape symbol, returns a new
state, replacement symbol (either might not
change) and a direction L=R for head motion.
Example
Nontrivial examples are hard to come by. Here's a
TM that checks its third symbol is 0, accepts if so,
and runs forever, if not.
M = (fp; q; r; s; tg; f0; 1g; f0; 1; B g; p; B; fsg)
1. (p; X ) = (q; X; R) for X = 0; 1.
2. (q; X ) = (r; X; R) for X = 0; 1.
3. (r; 0) = (s; 0; L).
4. (r; 1) = (t; 1; R).
5. (t; X ) = (t; X; R) for X = 0; 1; B .
ID's of a Turing Machine
The ID (instantaneous description) captures what
is going on at any moment: the current state, the
contents of the tape, and the position of the tape
head.
Keep things nite by dropping all symbols to
the right of the head and to the right of the
rightmost nonblank.
✦ Subtle point: although there is no limit
on how far right the head may move and
write nonblanks, at any nite time, the
TM has visited only a nite prex of the
innite tape.
3
Notation: q says:
✦ is the tape contents to the left of the
head.
✦ The state is q.
✦ is the nonblank tape contents at or to
the right of the tape head.
One move indicated by `; zero, one, or more
moves represented by `* .
✦ Check the reader for the detailed
denition of `.
Example
With input 0101, the sequence of ID's of the TM
is: p0101 ` 0q101 ` 01r01 ` 0s101.
At that point it halts, since state s has no
move when the head is scanning 1.
With input 0111 the sequence is: p0111 ` 0q111 `
01r11 ` 011t1 ` 0111t ` 0111Bt ` .
The TM never halts, but continues to move
right.
Acceptance by Final State and by Halting
One way to dene the language of a TM is by
the set of input strings that cause it to reach an
accepting state.
L(M ) = fw j q0w `* p for some p in F and
any and in , g.
Another way is to dene the set of strings that
cause the TM to halt = have no next move.
H (M ) = fw j q0w `* pX , and (p; X ) is not
denedg.
✦ Subtle point: a TM can appear to halt if
the next move would take the head o the
left end of the tape.
✦ Given any TM, we can mark the left end
so that never happens; i.e., we produce
a modied TM that accepts the same
language and halts rather than fall o
the left end.
Example
The TM M of our previous example has L(M )
equal to those strings in the language of RE
(0 + 1)(0 + 1)0(0 + 1) .
4
H (M ) is the language of + 0 + 1 + (0 + 1)(0 +
1) + (0 + 1)(0 + 1)0(0 + 1) .
Equivalence of Acceptance by Final State
and Halting
We need to show L is L(M1 ) for some TM M1 if
and only if L is H (M2 ) for some TM M2 .
If
Modify M2 as follows:
1. Introduce one accepting state r.
2. Whenever there is no transition for M2 on
state q and symbol X , add a transition to
state r, moving right (so we can't possibly fall
o the left end) and leaving symbol X .
Only-If
Roughly, we let M2 simulate M1 , but if M1 enters
an accepting state, M2 has no next move and so
halts.
Major problem: M1 could halt without
accepting.
✦ To avoid this problem, introduce state r
that moves right on every symbol, staying
in state r and leaving the tape symbols
unchanged.
✦ Give M2 a transition to r (moving right)
on every state-symbol combination that
does not have a rule.
Also, remove all transitions where the state is
an accepting state of M1 , so M2 will halt in
those situations.
Falling O the Left End of Tape
The reader talks about the funny situation where
the TM would halt but falls o the left end of
tape.
This situation is not halting.
Neither does a TM accept if it tries to enter
an accepting state as it falls o the left end.
We can prevent falling o the left end, by
marking the leftmost cell, as in the reader.
But it appears we do not need to do
so in order to prove the equivalence of
halting/accepting, since neither occurs when
the TM falls o the left end.