<<

. 7
( 9)



>>

containing , and a set of states Q, similar to the automaton. The Turing
machine has two special states, the start state s0 and the halt state h. When the
machine reaches the halt state it shuts down. It also has a tape which is in¬nitely
long on the right. If made of paper it can wipe out a forest.
The tape contains squares on which letters of the alphabet and other symbols
can be written or erased. Only a ¬nite number of the squares may contain tape
symbols. All of the squares to the right of the last square containing a tape sym-
bol are considered to be blank. Some of the squares between or in front of letters


169
Turing machines
170


may also be blank. In addition to the tape there is a head which can read any tape
symbol which is on the square of the tape at which the head is pointing. It also
can be in different states just like an automaton and a pushdown automaton. Also
like the automaton, the input can be a letter of the alphabet which can be read
from the tape together with the current state of the machine. Depending on the
input and its current state, the machine, in addition to changing states, can print
a different symbol on the square of the tape in front of it or erase the letter in the
square. In addition or instead, the head can move left or right from the square it
has just read to the next square. The blank can be both read and printed by the
Turing machine, but is not considered an element of the tape symbols. As input,
reading a blank is simply reading the absence of any of the tape symbols. Printing
a blank is considered to be erasing the symbol currently in that square. We use #
for blank. The Turing machine shown below is in state s1 and is reading letter a.

b a ab##¦
s0
s1
h
s4
s3 s2

More formally we have the following de¬nition.
De¬nition 5.1 A deterministic Turing machine is a quintuple
(Q, , , δ, s0 , h)
where Q is the set of states, is a ¬nite set of tape symbols, which includes the
alphabet and #, s0 is the starting state, h is the halt state, and δ is a function
from Q — to Q — — N where N consists of L which indicates a movement
on the tape one position to the left, R which indicates a movement on the tape
one position to the right, and # which indicates that no movement takes place.
Just like any computer, a Turing machine has a program or set of rules which
tell the machine what to do. An example of a rule is
δ(s1 , a) = (s2 , b, L)
which we shall denote as
(s1 , a, s2 , b, L).
This rules says that if the machine is in state s1 and reads the letter a, it is to
change to state s2 , print the letter b in place of the letter a and move one square
to the left. The rule
(s1 , a, s2 , #, R)
5.1 Deterministic Turing machines 171


says that if the machine is in state s1 and reads the letter a, it changes to state
s2 , erases the a and moves one square to the right. The rule
(s1 , #, h, #, #)
says that if the machine is in state s1 and reads a blank then it halts, and thus
does not print anything or move the position on the tape. For consistency we
shall always require that the machine begins in the leftmost square.
It may appear that since δ is a function, the deterministic Turing machine will
either continue forever or reach the halt state. However, if the Turing machine
is reading the leftmost square on the tape and gets the command to move left, it
obviously cannot do so. In such a case we say that the system crashes. Often a
special symbol is placed in the ¬rst box to warn the machine that it is reaching
the end of the tape.
Obviously there is a difference between the machine stopping because it
crashes and stopping when it reaches the halt state. In the second case the
machine has completed its program.
It is obvious that our rules allow us both to print a letter and move the position
on the tape to the left or to the right. Some de¬nitions allow a machine either
to print a letter or to move the head, but not both. Thus it requires two separate
rules to print a letter and move the position on the tape.
We shall begin with a program that simply moves the position of the machine
on the tape from the beginning to the end of a string. The alphabet is = {a, b}
and symbols = {a, b, #}. We shall have the set of states Q = {s0 , s1 , h} and
the set of rules
(s0 , a, s1 , a, R) (s0 , b, s1 , b, R) (s1 , a, s1 , a, R)
(s1 , b, s1 , b, R) (s1 , #, h, #, #, ).
This program leaves everything alone. It simply reads each letter and then moves
right to the next square. When it reaches a blank, it shuts down. However, this
program does do something which we shall later need. It moves the position on
the tape from the beginning of the word to the end of the word. Instead of having
it reach a blank and shut down, we will put it at the beginning of another program
where we want the position of the machine to be at the end of the word. Hence
we shall call this program go-end. As we demonstrate this program, it would
be rather tiresome to continually draw the Turing machine so rather than draw

a b a b b #¦
s0
s1
h
Turing machines
172


which shows the position of the machine at the second square of the tape and
in state s1 , while the ¬rst and third squares of the tape contain an a, the second,
fourth and ¬fth squares contain a b and the other squares are blank; we replace
this with
1
ababb
where the line below the b denotes the location of the head, and the 1 above the
b denotes the current state of the machine. We shall call this the con¬guration
of the Turing machine.
As we begin our program the machine has con¬guration
0
a b a b b.
We then apply rule
(s0 , a, s1 , a, R)
moving the head to the right and changing from state s0 to state s1 and our
machine then has con¬guration
1
a b a b b.
We then apply rule
(s1 , b, s1 , b, R)
moving the head to the right again and our machine then has con¬guration
1
a b a b b.
We then apply rule
(s1 , a, s1 , a, R)
moving the head to the right again and our machine then has con¬guration
1
a b a b b.
We again apply rule
(s1 , a, s1 , a, R)
moving the head to the right again and our machine then has con¬guration
1
a b a b b.
5.1 Deterministic Turing machines 173


We apply the same rule again and have
1
a b a b b #.
We then use rule
(s1 , #, h, #, #, )
and the machine shuts down.
We mentioned previously that if the position on the tape is on the leftmost
position on the tape and gets an instruction to move left, we say that the machine
crashes, and the machine ceases functioning.
We shall now construct a rather unusual program. This program causes the
machine to crash. We shall again let the input alphabet be the set {a, b, #}. We
shall also assume we have states Q = {s0 , s1 , . . . , s j , . . . }. It shall have the rules
(s j , a, s j , a, L) (s j , b, s j , b, L) (s j , #, s j , #, L).
If we have a larger alphabet, we simply add more rules, so that regardless of
what the machine reads when it is in state s j , it continues to go left until it
crashes. This program does not begin at s0 because we want to include it in
other programs when we want to crash the system. We shall call this program
go-crash. State s j is the “suicide” state. When we want to crash the system
we simply instruct it to go to state s j .
It seems pretty silly to think of either go-end or go-crash as complete pro-
grams. We really want to use them inside other programs. We shall refer to
these types of program as subroutines.
The reason for the go-crash program is really theoretical. If δ is a partial
function instead of a function then the Turing machine is still deterministic in the
sense that for every input for which there is a rule, there is a unique output. If for
every input, there is a unique output, then the set of rules would de¬ne a function.
If the rules do not de¬ne a function then there is a state s and an input letter a
for which there is no rule. When this happens, we say that the system hangs,
since it cannot go on. We shall again meet this problem with nondeterministic
automata. Suppose we would like the set of rules to de¬ne a function, but we
still want the program to stop when it is in state s and reads a. The system cannot
hang since the function is de¬ned for every input. We can however add a rule
(s, a, s j , a, L)
which puts the system into the suicide state and causes it to crash using
go-crash. Thus the system crashes instead of hanging and we have expanded
our rules so that we have a function. In this discussion, we will state only
Turing machines
174


relevant rules with the understanding that we could produce a function using
go-crash if we really wanted to do so.
It is perhaps time we considered something a bit more practical for the Turing
machine. We begin by showing some of its properties as a text editor. Our ¬rst
step is not exactly a giant one. We show how to move the position on the tape
to the right n steps. Again we assume both the input and output alphabet are
the set {a, b}. If we have a larger alphabet, we simply add appropriate rules for
each new letter. The set of states Q = {s1 , . . . , s j , . . . , sn , sn+1 }. We shall call
this new subroutine go-right(n). It has the following rules:
(s1 , a, s2 , a, R) (s2 , a, s3 , a, R) (s3 , a, s4 , a, R) · · · (sn , a, sn+1 , a, R)
(s1 , b, s2 , b, R) (s2 , b, s3 , b, R) (s3 , b, s4 , b, R) · · · (sn , b, sn+1 , b, R).

It is easily seen that if we begin in state s1 , each application of a rule, regardless
of the letter read, moves the the position on the tape one step to the right and
increases the state. After n steps the head has been moved to the right by n
squares and we are in state sn+1 . It is hoped that, with little effort, the reader
can create a subroutine for moving to the left by n squares.
Suppose that after moving left or right by n squares, or without moving at
all we want to change the letter in the current square occupied from a to b.
Assuming that we are in state si at the time then we simply use the rule
(si , a, si , b, #).
Moving along, suppose that
= {a1 , a2 , a3 , . . . , an , b1 , b2 , b3 , . . . , bn },
= ∪ {#} and we want to replace
a1 a2 . . . ai , ai+1 . . . a j , . . . an
with
a1 a2 . . . ai , bi+1 . . . b j , a j+1 . . . an .
We ¬rst use go-right(i) to move to the proper position so the head is on ai+1 .
Assume we are in state s , We then use the rules
(s , ai+1 , s1 , bi+1 , R)
(s1 , ai+2 , s2 , bi+2 , R)
(s2 , ai+3 , s3 , bi+3 , R)
(s3 , ai+4 , s4 , bi+4 , R)
.
.
.
(s j’i’1 , a j , s j’i , b j , R)
to replace the letters and use go-left( j) to return to the original spot.
5.1 Deterministic Turing machines 175


The next text edit feature which we shall illustrate is to insert a letter in a
string. We shall ¬nd this feature very handy in the near future. We shall call this
subroutine insert(c). Say that we have a string
a1 a2 · · · ai ai+1 · · · an’1 an
and we want to replace it with
a1 a2 · · · ai cai+1 · · · an’1 an
so that the string ai+1 · · · an’1 an must be moved one square to the right and
c placed in the square formerly occupied by ai+1 . We shall assume that the
string contains no blanks. If it does, a special symbol will have to be used to
denote the end of the string. Actually this is not quite the order in which we
shall proceed. First, for simplicity, assume that the input and output alphabets
are the same and that = {a, b, c} and {a, b, c, #}. We shall assume that we
know the position on the tape in which the c is to be placed (i.e. we know i) and
that we know the length of the string (i.e. we know n). First we use go-right(i)
to place the head where the letter c is to be placed. Assume that we are in state
sx when we reach this square. We are going to need a state for each letter in the
alphabet. Thus we shall need sa , sb , and sc . The process is really rather simple.
When we print c, we need to remember ai+1 so that we can print it in the next
square. We do this by entering sai+1 after we have printed c and then moving
right. In state sai+1 , we print ai+1 in the square occupied by ai+2 and then enter
state sai+2 and again move right. Each time we print a letter, we enter the state
corresponding to the letter destroyed and in this way “remember” this letter
so it can be printed in the next square. Remember in state sai+ j , we print ai+ j
regardless of the letter read. Finally, when we reach a blank square, we print
an and then use go-left(n) to return to the beginning of the string. Also it is
possible that c occurs elsewhere in the string; however, we shall assume that
ai+1 is not already c. Thus our rules for actually printing c and moving over the
other letters are
(sx , a, sa , c, R) (sb , c, sc , b, R) (sx , b, sb , c, R) (sc , a, sa , c, R)
(sc , b, sb , c, R) (sa , b, sb , a, R) (sc , c, sc , c, R) (sa , c, sc , a, R)
(sb , a, sa , b, R) (sb , #, s y , b, #) (sb , b, sb , b, R) (sc , #, s y , c, #)
(sa , a, sa , a, R) (sa , #, s y , a, #)
and we end up in state s y .
For example assume we have the word abbac and want to insert c so that
we have abcbbc. Using go-right(2), we have con¬guration
x
a b b a c.
Turing machines
176


Applying rule
(sx , b, sb , c, R)
we have con¬guration
b
a b c a c.
In the future we will condense this statement to
b
(sx , b, sb , c, R)
a b c a c.
We then have the following rules and con¬gurations
a
(sb , a, sa , b, R)
a b c b c
c
(sa , c, sc , a, R)
a b c b a #
y
(sa , #, s y , a, #)
a b c b a c
and we now use go-left(5) to return to our original position.
Suppose we began at the square of the letter we were replacing and wanted
to return to that square. Instead of placing the c in the square, we would place
a marker, and then when we had ¬nished moving the letters we would return to
the marker and replace it with a c. Details are left to the reader.
The next text edit feature which we shall illustrate is to delete a letter in a
string and close up the empty square. We shall call this subroutine delete(c).
Say that we have a string a1 a2 · · · ai cai+1 · · · an’1 an which contains no blanks
and we want to replace it with a1 a2 · · · ai ai+1 · · · an’1 an . If there is a blank, we
would have to have a special marker to denote the end of the string. There are at
least two ways of doing this. One way is to move over to the square containing
c and replace it with a marker which is not part of the regular alphabet. Then
go to the end of the string and move each letter to the left in a similar manner
to the one we used to move letters to the right in insert(c), replacing the marker
with the letter to its right and then changing states to return to the front of the
word or wherever desired. If the string contains no blanks then a blank can be
used to denote the end of the string. Otherwise a special symbol will need to
be used. The details of this subroutine are left to the reader.
An alternative form is to move to the letter to be deleted, replace it with a
marker, move to the right to ¬nd the next letter and replace the marker with that
letter. Then go right again to the letter which has been duplicated and replace it
5.1 Deterministic Turing machines 177


with a marker. Continue this process until reaching the end of the string. Let
be the special marker. Assume that we have used go-right(i) to reach the letter
c to be deleted. Again assume that we begin in state sx and want to end in state
s y . We shall also let the = {a, b, c} and = {a, b, c} ∪ {#, }. We then have
the following set of rules:
(sx , c, sx , , R) (sx , b, sx , , R) (sx , a, sx , , R) (sx , a, sa , a, L)
(sx , b, sb , b, L) (sx , c, sc , c, L) (sa , , sx , a, R) (sb , , sx , b, R)
(sc , , sx , c, R) (sx , #, sx , #, L) (sx , , s y , #, #).
Note that the marker is not actually needed. It is used to make the rules easier
to read.
For example, suppose we have the string abcbac and wish to remove the c
in the third space. We use go-right(2) to get to the desired space and have the
con¬guration
x
a b c b a c.
We then have the following rules and con¬gurations:
x
(sx , c, sx , , R)
ab bac
b
’ (sx , b, sb , b, L)
ab bac
x
’ (sb , , sx , b, R)
abbbac
x
’ (sx , b, sx , , R)
abb ac
a
’ (sx , a, sa , a, L)
abb ac
x
’ (sa , , sx , a, R)
abbaac
x
’ (sx , a, sx , , R)
a b b a c
c
’ (sx , c, sc , c, L)
a b b a c
x
’ (sc , , sx , c, R)
a b b a c c
x
’ (sx , c, sx , , R)
a b b a c #
x
’ (sx , #, sx , #, L)
a b b a c #.
Turing machines
178


Finally applying rule
(sx , , s y , #, #)
we have con¬guration
y
a b b a c # #
and using go-left(5), we return to the beginning of the string.
Finally we show how to use the Turing machine to duplicate a string. For
simplicity we shall limit the letters in the string to the set {a, b}. If the alphabet
is increased, similar rules to those given will be added for each letter included.
We shall need additional symbols »a , »b , σa , and σb . Brie¬‚y the ¬rst letter of
the string is replaced by »a if the letter is a and by »b if the letter is b. We
then go to the end of the string and place a corresponding σa , or σb . We then
return to the ¬rst symbol and replace it with the original letter, go to the second
letter and repeat the process. We continue until we have a string followed by
corresponding σa s, and σb s. We then replace each σa with an a and σb with a b.
Assume that we start in state sx and end in state s y . We then have the following
set of rules:
(sx , a, sa , »a , R) (sb , #, sx , σb , L) (sa , a, sa , a, R) (sx , a, sx , a, L)
(sx , b, sx , b, L) (sa , σa , sa , σa , R) (sx , σa , sx , σa , L) (sa , σb , sa , σb , R)
(sx , b, sb , »b , R) (sx , »a , sx , a, R) (sb , a, sb , a, R) (sx , »b , sx , b, R)
(sx , σa , sx , a, R) (sb , σa , sb , σa , R) (sx , σb , sx , b, R) (sb , σb , sb , σb , R)
(sa , #, sx , σa , L) (sa , b, sa , b, R) (sx , σb , sx , σb , L) (sb , b, sb , b, R)
(sx , #, s y , #, #).
For example, we shall duplicate the word bab. The initial con¬guration is
x
b a b.
We then have the following rules and con¬gurations:
b
(sx , b, sb , »b , R)
»b a b
b
’ (sb , a, sb , a, R)
»b a b
b
’ (sb , b, sb , b, R)
»b a b #
x
’ (sb , #, sx , σb , L)
»b σb
a b
x
’ (sx , b, sx , b, L)
»b σb
a b
5.1 Deterministic Turing machines 179


x
’ (sx , a, sx , a, L)
»b
a b σb
x
’ (sx , »b , sx , b, R)
b a b σb
a
’ (sx , a, sa , »a , R)
b »a b σb
a
’ (sa , b, sa , b, R)
b »a b σb
a
’ (sa , σb , sa , σb , R)
»a σb
b b #
x
’ (sa , #, sx , σa , L)
»a σb σa
b b
x
’ (sx , σb , sx , σb , L)
»a σb σa
b b
x
’ (sx , b, sx , b, L)
»a
b σb σa
b
x
’ (sx , »a , sx , a, R)
b a b σb σa
b
’ (sx , b, sb , »b , R)
b a »b σb σa
b
’ (sb , σb , sb , σb , R)
b a »b σb σa
b
’ (sb , σb , sb , σb , R)
b a »b σb σa
b
’ (sb , σa , sb , σa , R)
»b σb σa
b a #
x
’ (sb , #, sx , σb , L)
»b
σb σa σb
b a
x
’ (sx , σa , sx , σa , L)
b a »b σb σa σb
x
’ (sx , σb , sx , σb , L)
b a »b σb σa σb
x
’ (sx , »b , sx , b, R)
b a b σb σa σb
x
’ (sx , σb , sx , b, R)
b a b b σa σb
x
’ (sx , σa , sx , a, R)
b a b b a σb
x
’ (sx , σb , sx , b, R)
babbab#
Turing machines
180


and applying rule

(sx , #, s y , #, #)

we have
y
b a b b a b #

and we are done.

De¬nition 5.2 A word w ∈ — is accepted by a Turing machine T if, begin-
ning in the start state, there is a way to read w and be in the halt state. The
language accepted by a Turing machine T is the set of all words accepted by
T.

We next show how to use the machine as an acceptor. We begin by showing
that a Turing machine can recognize a regular language. We already know that
an automaton recognizes a regular language, so what we shall basically do is
program it to imitate an automaton. Assume that we have a word in the Turing
machine which we want the machine to read so that it can determine whether it
wants to accept it. An automaton reads a word beginning with the ¬rst letter and
reads from left to right until it has reached the last letter. We need our Turing
machine to do the same.
s0
# a1 a2 a3 a4 a5 a6 a7

and we are ready to begin.
We have another way of representing a Turing machine which makes it look
more like an automaton. We shall represent the rule

(si , a, s j , b, R)

by the symbol

a
sj
(b,R)
si


so that the program go-end which has rules

(s0 , a, s1 , a, R) (s0 , b, s1 , b, R) (s1 , a, s1 , a, R)
(s1 , b, s1 , b, R) (s1 , #, h, #, #, #)
5.1 Deterministic Turing machines 181


may be represented by

)
a,R




a
(
b
a s1
(b,R)
(a,R)
s0
b




#
(b,R)
h

Notice that the letter above the arrow is the letter which is read by the machine.
We really do not care what is printed out. We could print a # in each square as
it is read or we could simply print back the letter that is read. We shall choose
to do the latter. Each time a letter is read, we wish the machine to move one
square to the left, so that the next letter is read.
We are now ready to imitate an automaton. If the symbol

a
sj
si

occurs in an automaton, we shall imitate it with the rule
(si , a, s j , a, R)

or the symbol
a
(a,L) sj
si

It may be recalled that a word is accepted by an automaton if, after the word is
read, the automaton is in an acceptance state. For every acceptance state s of
the automaton, we will add a rule

(s, #, h, #, #)

shown as

#
(#,#) h
si


so that if the word is accepted by the automaton it will also end up in state s of
the Turing machine, read the # in front of the word and halt. Thus the Turing
Turing machines
182


machine halting will mean that it accepts a word. Further a Turing machine
programmed in this manner accepts the same words as the automaton it is
imitating.
For example, given the automaton

a

s1
a b
s3
s0
s2 a
b


b

we have the corresponding program for the Turing machine

a
(a,R)

b
s1
a (b,R)
) #
(a,R
s0 s3 h
a (#,#)
b
(a,R)
s2
(b,R)

b
(b,R)
#
(#,#)

Since a Turing machine can be programmed to accept the same language as
a given automaton, we have the following theorem:
Theorem 5.1 Every regular language is recognized by a Turing machine.
De¬nition 5.3 The languages recognized by Turing machines are called
recursively enumerable.
We have already shown that regular languages are recursively enumerable
and claimed that context-free languages are recursively enumerable. At this
point we shall show how a Turing machine recognizes the language {a n bn : n
is a positive integer}, which is context-free, and how it recognizes {a n bn cn : n
is a positive integer}, which is not context-free.
We begin by designing a program for a Turing machine that will recognize
the language {a n bn : n is a positive integer}. We basically want the Turing
5.1 Deterministic Turing machines 183


machine to read an a, then read a b, return to read an a, and continue until all
of the as and bs have been read, if there is an equal number of them. We begin
by reading an a in the ¬rst square. We want to know that we have counted this
a, so we shall change it to A. We do this with rule

(s0 , a, s1 , A, R).

We now want to go right until we reach a b, which we shall change to a B. To
get to b, we need to pass over each a without changing it and also after the ¬rst
time we may have to pass over Bs without changing them to reach a b. We do
this with the rules
(s1 , a, s1 , a, R)
(s1 , B, s1 , B, R).

When we reach a b, we want to change it to a B and go back left. We do that
with the rule

(s1 , b, s2 , B, L).

We now need to go back to ¬nd the second a. To do this we go left until we
reach an A. This will tell us that the next letter to the right should be the next
a. To go back, we need to pass over Bs, and as to get to A. We do this with the
rules

(s2 , B, s2 , B, L) (s2 , a, s2 , a, L).

When we reach A, we want to go one square to the right to read another a, if
there is one. We do this with the rule

(s2 , A, s0 , A, R).

This puts us back into the cycle of reading another a and another b. If we run
out of bs before we run out of as the system will be in state s1 and eventually try
to read a blank so it will hang. If we have read the last a, then when we reach
A and go right one square, we will read a B. At this point we need to check to
see if there is another b. First we change state if we are in s0 and read a B. We
do this with rule

(s0 , B, s3 , B, R).

In state s3 , read nothing but Bs and a blank. Thus we have the rules

(s3 , B, s3 , B, R) (s3 , #, h, #, #).
Turing machines
184


This may also be shown as the labeled graph
a B
(B,R)
(a,R)
a
L)
b
a,
s1 (
s2
a (B,L)
B
)
(A,r
s0 (B
,L
A )
(A,R)
(B B #
,R
) s3 (#,#) h

B
(B,R)

For example consider the string aabb. The initial con¬guration is
0
a a b b.
We then have the following rules and con¬gurations:
1
(s0 , a, s1 , A, R)
A a b b
1
’ (s1 , a, s1 , a, R)
A
a bb
2
’ (s1 , b, s2 , B, L)
AaBb
2
’ (s2 , a, s2 , a, L)
AaBb
0
’ (s2 , A, s0 , A, R)
AaBb
1
’ (s0 , a, s1 , A, R)
AABb
1
’ (s1 , B, s1 , B, R)
AABb
2
’ (s1 , b, s2 , B, L)
AABB
2
’ (s2 , B, s2 , B, L)
AABB
2
’ (s2 , B, s2 , B, L)
AABB
0
’ (s2 , A, s0 , A, R)
AABB
5.1 Deterministic Turing machines 185


3
’ (s0 , B, s3 , B, R)
A A B B
3
’ (s3 , B, s3 , B, R)
A A B B #
h
’ (s3 , #, h, #, #)
A A B B #.
Next we design a program for a Turing machine that will recognize the
language {a n bn : n is a positive integer}.
We begin by reading an a in the ¬rst square. We want to know that we have
counted this a, so we shall change it to A. We do this with rule
(s0 , a, s1 , A, R).
We now want to go right until we reach a b, which we shall change to a B. To
get to b, we need to pass over each a without changing it and also after the ¬rst
time we may have to pass over Bs without changing them to reach a b. We do
this with the rules
(s1 , a, s1 , a, R) (s1 , B, s1 , B, R).
When we reach a b, we want to change it to a B and start back to look for
another a. We do this with the rule
(s1 , b, s2 , B, L).
To go back, we need to pass over Bs and as to get to A. We do this with the
rules
(s2 , B, s2 , B, L) (s2 , a, s2 , a, L).
When we reach A, we want to go one square to the right to read another a, if
there is one. We do this with the rule
(s2 , A, s0 , A, R).
This puts us back into the cycle of reading another a and b. If we run out of bs
before we run out of as the system will hang. If we have read the last a, then
when we reach A and go right one square, we will read a B. At this point we
need to check to see if there is another b. First we change state if we are in s0
and read a B. We do this with rule
(s0 , B, s3 , B, R).
In state s3 , we expect to read nothing but Bs, b, and a blank. Thus we have the
rules
(s3 , B, s3 , B, R) (s3 , b, s4 , B, R) (s4 , #, h, #, #).
Turing machines
186


We now design a program for a Turing machine that will recognize the
language {a n bn cn : n is a positive integer}. In a manner similar to the previous
example we want the Turing machine to read an a, then read a b, then read a c,
and continue until all of the as, bs, and cs have been read, if there are an equal
number of them. We begin by reading an a in the ¬rst square. We want to know
that we have counted this a, so we shall change it to A. We do this with rule
(s0 , a, s1 , A, R).
We now want to go right until we reach a b, which we shall change to a B. To
get to b, we need to pass over each a without changing it and also after the ¬rst
time we may have to pass over Bs without changing them to reach a b. We do
this with the rules
(s1 , a, s1 , a, R) (s1 , B, s1 , B, R).
When we reach a b, we want to change it to a B and continue onward. We do
that with the rule
(s1 , b, s2 , B, R).
We now need to continue until we ¬nd a c. We will need to pass over bs and
Cs. We do this with the rules
(s2 , b, s2 , b, R) (s2 , C, s2 , C, R).
We next want to read c, replace it with a C, and start back to look for another
a. We do this with the rule
(s2 , c, s3 , C, L).
To go back, we need to pass over Cs, bs, Bs, and as to get to A. We do this
with the rules
(s3 , C, s3 , C, L) (s3 , b, s3 , b, L) (s3 , B, s3 , B, L) (s3 , a, s3 , a, L).
When we reach A, we want to go one square to the right to read another a, if
there is one. We do this with the rule
(s3 , A, s0 , A, R).
This puts us back into the cycle of reading another a, b, and c. If we run out
of bs or cs before we run out of as the system will hang. If we have read the
last a, then when we reach A and go right one square, we will read a B. At this
point we need to check to see if there is another b. First we change state if we
are in s0 and read a B. We do this with rule
(s0 , B, s4 , B, R).
5.1 Deterministic Turing machines 187


In state s4 , we expect to read nothing but Bs, Cs, and a blank. Thus we have
the rules

(s4 , B, s4 , B, R) (s4 , C, s4 , C, R) (s4 , #, h, #, #).

This may also be shown as the labeled directed graph

a B
(B,R)
(a,R) b
)
,R
b
(b
s1 s2
a (B,R) C
R)
(A, C
s0 (a,L) (C,L) (C,
R)
c)
a
A
,L
(A,R s3 (C
)
b B
(b,L) (B,L)
B
(B
,R
) s4 # h
(#,#)
(B,R) (C,R)
BC

For example consider the string aabbcc. The initial con¬guration is

0
a a b b c c

We then have the following rules and con¬gurations:

1
(s0 , a, s1 , A, R)
A abbcc
1
’ (s1 , a, s1 , a, R)
A abbcc
2
’ (s1 , b, s2 , B, R)
A aBbcc
2
’ (s2 , b, s2 , b, R)
A aBbcc
3
’ (s2 , c, s3 , C, L)
A a B b C c.
3
’ (s3 , b, s3 , b, L)
A aBbCc
3
’ (s3 , B, s3 , B, L)
A aBbCc
Turing machines
188


3
’ (s3 , a, s3 , a, L)
AaBbCc
0
’ (s3 , A, s0 , A, R)
AaBbCc
1
’ (s0 , a, s1 , A, R)
AABbCc
1
’ (s1 , B, s1 , B, R)
AABbCc
2
’ (s1 , b, s2 , B, R)
AABBCc
2
’ (s2 , C, s2 , C, R)
AABBCc
3
’ (s2 , c, s3 , C, L)
AABBCC
3
’ (s3 , C, s3 , C, L)
AABBCC
3
’ (s3 , B, s3 , B, L)
AABBCC
3
’ (s3 , B, s3 , B, L)
AABBCC
0
’ (s3 , A, s0 , A, R)
AABBCC
4
’ (s0 , B, s4 , B, R)
AABBCC
4
’ (s4 , B, s4 , B, R)
AABBCC
4
’ (s4 , C, s4 , C, R)
AABBCC
4
’ (s4 , C, s4 , C, R)
A A B B C C #
h
’ (s4 , #, h, #, #)
A A B B C C #.

We now show how to perform two arithmetic operations on a Turing machine.
The ¬rst of these is addition, which is trivial. Suppose we have p, represented
by a string of 1s of length p, and q represented by a string of 1s of length q, so
we have the con¬guration

0
1 ... 1 . . . 1.
1 1 #1 1 11
5.1 Deterministic Turing machines 189


We simply use delete(#) to delete the blank, and we have
0
1 ... 1 1 ... 1
1 1 1 1 1
which is a string of 1s of length p + q, which represents p + q.
We now sketch a method of multiplying positive integers p and q, which
are represented by strings of 1s of lengths p and q respectively. Details of the
multiplication are left to the reader. We begin with the con¬guration
0
1 ... 1 1 . . . 1.
1 1 # 11 1
Replace the ¬rst 1 with β. Replace the second 1 with β (if there is no second 1,
move left and delete β, leaving only the string q). Otherwise, move to the end
of the string of 1s of length q. Place a blank (so that the length of q is retained),
and place another string of 1s of length q after the blank. Return to β and then
go right to the next 1 in the string for p. Replace the 1 with β and again place a
string of 1s of length q at the end of the third string. Continue this until there are
no more 1s in the string for p. At that point when the machine tries to read a 1
from p, it will read a #. Go to end of the third string. Go left deleting all blanks.
Then continue left until reaching a β. Delete all βs to produce the answer.


Exercises
(1) Supply the details for the Turing machine program delete(c).
(2) Design a Turing machine for the program go-left(n) which moves the head
of the machine to the left n squares.
(3) Design a Turing machine for insert(c) which begins at the square of the
letter we were replacing and returns to that square. (Hint: Instead of placing
the c in the square, we would place a marker, and then when we had ¬nished
moving the letters we would return to the marker and replace it with a c.)
(4) Design a Turing machine for delete(c) where the machine moves over to
the square containing c and replaces it with a marker which is not part of
the regular alphabet. It then goes to the end of the string and moves each
letter to the left in a similar manner to the one we use to move letters to
the right in insert(c). It replaces the marker with the letter to its right and
then changes states to remain where the letter was inserted.
(5) Design a Turing machine that multiplies two positive integers.
(6) Design a Turing machine that subtracts a smaller number from a larger
one.
(7) Design a Turing machine that accepts the language described by the
expression ab— c— (b ∨ ac).
Turing machines
190


(8) Design a Turing machine that accepts the language described by the
expression abc(b ∨ ac)— b
(9) Design a Turing machine that accepts all strings in a and b except aba
and abb.
(10) Design a Turing machine that accepts the language described by the
expression (aa — bb— )— .
(11) Write the list of rules and con¬gurations to describe the results when the
program that accepts a n bn for a positive number n tries to read a 2 b3 .
(12) Write the list of rules and con¬gurations to describe the results when the
program that accepts a n bn for a positive number n tries to read a 3 b2 .
(13) Write the list of rules and con¬gurations to describe the results when the
program which accepts a n bn cn for a positive number n tries to read a 3 b2 c3 .
(14) Design a Turing machine that accepts the language of all strings in a and
b that have the same number of as and bs.
(15) For a given string s consisting of as and bs, de¬ne reverse(s) to be the
string s written backwards. Thus reverse(abbb) = bbba. Design a Turing
machine that, given a string s, prints its reverse.
(16) A palindrome over the set {a, b, c} is a string such that s = reverse(s).
Thus abbcbba, abba, abcba, and cbaabc are palindromes. An even palin-
drome has an even number of letters in the string and an odd palindrome
has an odd number of letters in the string. Design a Turing machine that
accepts all even palindromes.
(17) Design a Turing machine that accepts all odd palindromes.
(18) Design a Turing machine that accepts all words of the form a n bn a n for
any positive integer n.
(19) Design a Turing machine that accepts all words of the form ww where w
is a string of as and bs.



5.2 Nondeterministic Turing machines and acceptance of
context-free languages
We begin by showing that a context-free language can be accepted by a non-
deterministic Turing machine and then show that any language accepted by a
nondeterministic Turing machine is accepted by a deterministic Turing machine.
De¬nition 5.4 A Turing machine is not deterministic if δ is a ¬nite subset of
(Q — ) — (Q — — N ).
Thus δ is replaced by a relation, which we shall denote by θ. Thus θ(s, a)
is a subset of (Q — — N ). Since a context-free language is accepted by a
5.2 Nondeterministic Turing machines and CFLs 191


pushdown automata, we show that a pushdown automaton can be imitated by a
Turing machine and hence this Turing machine accepts a context-free language.
The only problem at this point is that a pushdown automaton is not deterministic
and hence the Turing machine we create is not deterministic. Thus we must show
that any language accepted by a nondeterministic Turing machine is accepted
by a deterministic Turing machine.
Theorem 5.2 A context-free language is accepted by a nondeterministic Tur-
ing machine.
Proof We shall prove this theorem informally assuming that the steps in the
conversion can be easily replaced by subroutines in a Turing machine. When
at a given step, we have the word w to read and ω in the stack of the pushdown
automata, we shall associate this with w∇ω on the tape of the Turing machine.
The word w is accepted if w∇# is converted to #∇#. Assume the tape begins
with a blank followed by the word. Assume also that the Turing machine is
positioned at the ¬rst letter of the word.
For each of the rules for a pushdown automaton, we shall give the corre-
sponding instructions for a Turing machine.
((a, s, E), (t, D)) In state s, a is read and E is popped, go to state t
1
and push D.
((a, s, »), (t, D)) In state s, a is read, go to state t and push D.
2
((», s, »), (s, D)) In state s, push D.
3
((a, s, E), (t, »)) In state s, and a is read, pop E and go to state t.
4
((», s, E), (s, »)) In state s, pop E.
5
((a, s, »), (t, »)) In state s, read a and go to state t.
6
((a, s, »), (s, »)) In state s, read a.
7

1. Go to the ¬rst position after ∇, delete E and insert D. Return to a and delete
a. Go to state t.
2. Go to the ¬rst position after ∇, insert D. Return to a and delete a. Go to
state t.
3. Go to the ¬rst position after ∇, insert D. Return to the original letter. Go to
state s.
4. Go to the ¬rst position after ∇, delete E. Return to a and delete a. Go to
state t.
5. Go to the ¬rst position after ∇, delete E. Return to the original position. Go
to state s.
6. Delete a. Go to state t.
7. Delete a. Go to state s.
Turing machines
192


We now show that a language accepted by a nondeterministic Turing machine
T is accepted by a deterministic Turing machine T . Since T is nondeterministic,
and, θ(s, x) is a subset of (Q — — N ), if θ (s, x) contains k elements, we
shall denote them by θ0 (s, x), θ1 (s, x), θ2 (s, x) . . . θk’1 (s, x). Thus each of the
θi (s, x) is well de¬ned. For example we could have θ0 (s, x) = (s , b, R), so the
rule is (s, x, s , b, R) and θ1 (s, x) = (s , C, L), so the rule is (s, x, s , C, L).
We number the elements in each θ(si , ai ) for each state si and each ai in .
Hence if we are in state s and and have input x, and are given an integer j,
we can use θ j (s, x) to supply the rule to use. Assume that we never need more
than n + 1 integers to label the subsets for any θ(si , ai ), then if we have a
sequence of nonnegative integers m 1 , m 2 , . . . , m p less than or equal to n, we
could sequentially apply θm 1 ,θm 2 , . . . , θm p , which together with the state and
input would give us the rules to use. If we apply all possible relevant sequences,
we can produce all possible computations. Hence if a word is accepted by the
Turing machine T , it will be accepted in one of these computations.
The next problem is the production of the sequences of integers. We shall
label these sequences N0 , N1 , N2 , . . . , Ni , . . . We begin with N0 = 0 and sim-
ply count in base n + 1. Thus the sequences are
(0), (1), (2), . . . , (n), (1, 0), (1, 1), (1, 2), (1, 3), . . . , (1, n), (2, 0), . . .
The sequence following
(1, 3, 4, 3, 2, 3)
is
(1, 3, 4, 3, 2, 4),
and the sequence following
(1, 3, 4, n, n, n)
is
(1, 3, 5, 0, 0, 0).
The subroutine in which a Turing machine changes the number Nk to Nk+1 is
straightforward and is left to the reader in the problems, with the warning that
as the length of the sequence is increased, it is increased to the right on the tape.
We next have to decide how to proceed in reading a given word. We will
place the word to be read, followed by | and the current sequence on the tape.
At each step we will mark the letter being read, keeping track of the state the
machine is in, and then proceed to the right to locate the proper number in
the sequence. If the machine is in state s, and we mark a, we shall use as as
5.2 Nondeterministic Turing machines and CFLs 193


the marker. Thus we retain information about both the letter read and the current
state of the machine. As we use a number in the sequence we mark it with a , so
that we proceed each time to the ¬rst unmarked number in the sequence, select
it, mark it, and then return to the marked letter with the information needed to
select the proper path for the Turing machine to take, given the state and the
letter being read. For example suppose the Turing machine is in state s, reads
letter a, and ¬nds that j is the number selected, it then proceeds with θ j (s, a)
to supply the rule to use.
As an illustration suppose we have
s4
|
a s1 bs2 as3 b b a a 1 2 2 13 1 2.
We change b to bs4 so we have

s4
|
as1 bs2 as3 bs4 b a a 1 2 2 131 2.

We then move to 1, the ¬rst unmarked integer and mark it, so we have
s4 q1
|
as1 bs2 a s3 bs4 b a a 1 2 2 1 312
where the subscript of the state is the number selected. We then return to bs4
where we have θ — (q1 , bs4 ) = θ1 (s4 , b).
The instructions could be as follows
θ — (si , ±) = θsi (t1 , ±si , R)
θ — (t1 , x) = (t1 , x, R) for x =|
θ — (t1 , |) = (t2 , |, R)
θ — (t2 , n ) = (t2 , n , R) for integer n
θ — (t2 , m) = (qm , m , L) for ¬rst unmarked integer m
θ — (qm , n ) = (qm , n , L) for all marked integers n
θ — (qm , x) = (qm , x, L) if x is an unmarked letter of the alphabet
θ — (qm , ±) = θm (si , ±) if a is marked by si .
Informally we state the procedure for testing a word for acceptance by a Turing
machine as follows: First, given the word, duplicate the word and follow it by
the ¬rst sequence so that we have

w#w | 0.

Perform the process above for testing the second copy of the word w following
the sequence #. At the beginning, the machine is positioned at the ¬rst letter of
w. If θ — (t2 , #) occurs and the word is not accepted, the end of the sequence has
Turing machines
194


been reached. Erase the symbols between # and |, again duplicate w after the #,
proceed to the next sequence and repeat the process until the word is accepted or
the length of the sequence exceeds m n+1 , where there are m productions begin-
ning with θ — (si , ±i ) and n is larger than the number of productions beginning
with any θ — (si , ±i ) in the nondeterministic Turing machine of the word, since
all possibilities have been tried. Since the new Turing machine which we shall
call T just de¬ned is deterministic and a word is accepted by T if and only
if it is accepted by T , we have shown that a word is accepted by a nondeter-
ministic Turing machine if and only if it is accepted by a deterministic Turing
machine.
We ¬nally conclude that if a word is context-free, it is accepted by a Turing
machine.


Exercises
(1) In Theorem 5.2 write a subroutine for producing the sequence of integers
used for showing that a language accepted by a nondeterministic Turing
machine can be accepted by a deterministic Turing machine.
Find Turing machines (not necessarily deterministic) that accept the
context-free languages.
(2) The language containing twice as many as as bs.
(3) The language containing the same number of as and bs.
(4) The language {a n bn : n = 1, 2, . . . }.
(5) The language {a n bk cn : k, n = 1, 2, . . . }.
(6) The language of palindromes of odd length on the alphabet {a, b, c}.
(7) The language of palindromes of even length on the alphabet {a, b, c}.
(8) The language of all palindromes on the alphabet {a, b, c}.
(9) The language {a n bn a m bm : m, n = 1, 2, . . . }.
(10) The language {a n b2n a m b2m : m, n = 1, 2, . . . }.



5.3 The halting problem for Turing machines
One of the more frustrating problems running a computer problem occurs when
the computer continues to run with no end in sight. One has the dilemma of
deciding whether the computer has just not ¬nished the problem, and perhaps
in ¬ve minutes or ¬ve hours it will ¬nish the problem, or if it is in a loop and
will continue to run forever. This would be particularly true if the machine were
as inef¬cient as a Turing machine. It would be nice if one could determine in
5.3 The halting problem for Turing machines 195


advance whether the machine was going to halt, which is equivalent to solving
the problem. Assuming Church™s Thesis, if there was an algorithmic step by
step way of determining whether a machine was going to halt, then a program
could be written for a Turing machine that could determine whether a machine
was going to halt.
This particular problem is called the halting problem and is formally stated
as follows:

Halting Problem Is there an algorithm which will determine whether, for
any given Turing machine T and any input string w, the Turing machine T ,
given the input string w, will reach the halt state?

Before answering this question, we look at some related properties of a
Turing machine. When we were looking at acceptance of regular languages
by a Turing machine, a word was accepted if the machine reached the halt
state. Otherwise, the machine crashes, hangs, or loops. Any language which is
accepted in this manner is called Turing acceptable.
It would be nice if the Turing machine, when a word was read by it, would
print Y at the beginning of the tape if the word were in the language and N if
the word were not in the language.

De¬nition 5.5 A language L is Turing decidable if there exists a Turing
machine that, when a string is input, prints Y on the tape if the word is in L
and N if the word is not in L.

Theorem 5.3 If a language is Turing decidable then it is Turing acceptable.

Proof If a language L is Turing decidable, then there is a Turing machine that
prints Y if the word is in L and N if the word is not in L. Modify this machine
so that instead of printing N , it goes into an in¬nite loop and instead of printing
Y , goes into the halt state. Thus the new machine halts if a word is in L and
goes into an in¬nite loop if the word is not in L. Thus L is Turing acceptable.


Theorem 5.4 If a language L is Turing decidable, then its complement L =
A— ’ L is Turing decidable.

Proof If a language L is Turing decidable, then there is a Turing machine that
prints Y if the word is in L and N if the word is not in L. Modify this machine
so that instead of printing Y , it prints N and instead of printing N , it prints Y .
This new machine prints Y if the word is in L and N if the word is not in L .
Thus L is Turing decidable.
Turing machines
196


Theorem 5.5 A language L is Turing decidable if and only if both L and L
are Turing acceptable.

Proof If a language L is Turing decidable then by Theorem 5.4, its comple-
ment L is also Turing decidable. But by Theorem 5.3, L and L are then both
Turing acceptable.
Conversely, if L and L are both Turing acceptable, then there are machines
M and M that accept languages L and L respectively. Place the input string
in both M and M . If the input string is accepted by M, then print the letter Y .
If the input string is accepted by M , then print the letter N . Since this process
is algorithmic, by Church™s Thesis, it can be duplicated by a Turing machine
M . Hence L is Turing decidable and, by Theorem 5.4, its complement L is
also Turing decidable.

Before proceeding further we need to show that every Turing machine with
alphabet A = {a, b} can be uniquely described by a string of as and bs. It is
obvious that a Turing machine is uniquely determined by the set of rules for
the machine. We shall show this for the set of states S = {s1 , s2 , s3 , . . . , sn }. It
may be recalled that a rule has the form

(si , a, s j , b, L)

where the ¬rst and third components are states, the second and fourth compo-
nents are letters of a set of tape symbols which contains the alphabet. We may
also have #, and , which may be used as a marker in . The last component is
either L or R. At times we have also included # in the last component, but this
was not really necessary. It was merely used in the halt statement to indicate
that the machine had halted and so had ceased moving. We proceed with the
encoding as follows: If the ¬rst component is si , we begin with a string of as
of length i. Thus if the ¬rst component is s3 , we begin with aaa. We follow
this with a b, which is used as a divider. For the symbols a, b, #, and , we
add to the string aa, bb, ab, and ba respectively. Thus if the ¬rst component is
s4 and the next component is a, then our string at this point is aaaabaa. We
follow this with the string of as corresponding to the state s j and then another
b for a divider. We include a for L and b for R as the fourth component. Thus
the string for (s4 , b, s2 , #, R) is aaaabbbaababb, where aaaa represents s4 , b
is a divider, bb represents b, aa represents s2 , b is a divider, ab represents #,
and b represents R. Once we have a string for each rule, we then concatenate
or connect all of the strings together to form one long string of as and bs that
represent the Turing machine.
5.3 The halting problem for Turing machines 197


It is also possible to decode the string. For example suppose we had the string
ababaaabbbb . . . , the ¬rst a represents s1 , the b is a divider, ab represents #,
aaa represents s3 , b is a divider, bb represents b, and b represents R. We have
decoded the rule (s1 , #, s3 , b, R) and we continue reading the string to get the
next rule. Denote the string that represents the Turing machine M by c(M).
Suppose we want to display a string that represents a Turing machine fol-
lowed by input to be read by the machine. This is easily done by taking the
string for the Turing machine M followed by a b and then followed by the input.
Since no rule starts with a b, ¬nding a b would indicate to the decoder that data
followed rather than another rule. Thus the string representing machine M with
input w is c(M)bw.
Consider the language L 0 which consists of all strings c(M)bw representing
a Turing machine M followed by an input word w where the Turing machine
accepts that input word. It is simple to construct a Turing machine M M that
accepts L 0 . Given a string t, M M ¬rst decodes t and if it represents a Turing
machine M followed by input data, it inputs the data into the machine M,
which can be recovered from the string t, and M M accepts the input c(M)bw
if and only if M accepts the input string t. Therefore L 0 is Turing acceptable.
If, in addition L 0 is Turing decidable, then every Turing acceptable language
is Turing decidable. To show this we know that if L 0 is Turing decidable, then
there exists a Turing machine, say M M2 , which, given any input string w, will
print Y if w is in L 0 and N if w is not in L 0 . Assume that we have a Turing
acceptable language L, then it is accepted by a Turing machine M(L). We can
now construct a Turing machine M (L) which, given an input string s, prints Y
if s is in L and N if s is not in L. The Turing machine M (L) is constructed by
simply taking the string c(M(L)), adding the input string s to form c(M(L))bs
and then using it as an input string s for M M2 . If M M2 prints Y for the input
s then machine M(L) accepts s, so M (L) prints Y . If M M2 prints N for the
input s then machine M(L) does not accept s, so M (L) prints N . Thus L is
Turing decidable. It thus follows that every acceptable language is decidable if
and only if L 0 is decidable.
We now show that L 0 is not Turing decidable. We claim that if L 0 is Turing
decidable then the language L 1 = {c(M) such that M accepts c(M) is Turing
decidable}. To show this, assume that L 0 is Turing decidable. We construct M1
as follows: Given an input string s, we simply take the string sbs and use it
as input for M M2 . If M M2 prints Y then s = c(M) for some M that accepts
c(M). Therefore s ∈ L 1 and M1 prints Y . If M M2 prints N then s = c(M) for
any machine M that accepts c(M), so that s ∈ L 1 and M1 prints N . Thus L 1 is
/
Turing decidable.
Turing machines
198


We now show that L 1 is not Turing decidable. Since by Theorem 5.4, L 1
is Turing decidable if and only if L 1 is, we shall prove that L 1 is not Turing
decidable. The language L 1 = {{w : w ∈ {a, b}— } and either w = c(M) for any
machine M or w = c(M) for some machine M but M does not accept w}. Here
we are reminded of Russell™s paradox. Let M1 be a machine that accepts L 1 ,
then is it true that c(M1 ) ∈ L 1 ? If so then M1 does not accept c(M1 ) by de¬nition
of L 1 . But M1 does accept c(M1 ) because it accepts every element of L 1 , and
we have a contradiction. Conversely assume c(M1 ) ∈ L 1 . Then c(M1 ) ∈ L 1 so
/
that M1 accepts c(M1 ) by de¬nition of L 1 . But M1 only accepts elements of L 1
so that c(M1 ) ∈ L 1 , again a contradiction. Hence L 1 is not Turing acceptable
and certainly not Turing decidable.
Since we have shown that L 0 is Turing acceptable but not Turing decidable,
we have the following theorem:

Theorem 5.6 There exists a language that is Turing acceptable but not Turing
decidable.

Since L 0 is Turing acceptable but not Turing decidable, the following theo-
rem follows from Theorem 5.5:

Theorem 5.7 There exists a language which is Turing acceptable but whose
complement is not Turing acceptable.

We have also solved the halting problem since a string is acceptable if and
only if the machine reaches the halt state. Hence the algorithm that would satisfy
the halting problem is the algorithm which describes M M2 and it does not
exist.

Theorem 5.8 Given a Turing machine T and an input string w, there is no
algorithm which will determine whether the Turing machine T , given the input
string w, will reach the halt state.


Exercises
(1) Show that a ¬nite set is Turing decidable.
(2) Find the string representing the rule (s5 , , s2 , a, R).
(3) Find c(M) where M is the machine de¬ned by the rules

(s1 , a, s2 , a, R) (s1 , b, s2 , b, R) (s2 , a, s2 , a, R)
(s2 , b, s2 , b, R) (s1 , #, s3 , #, R).
5.3 The halting problem for Turing machines 199


(4) Find c(M) where M is the machine de¬ned by the rules
(s1 , a, s2 , #, R) (s1 , b, s2 , a, R) (s2 , a, s2 , #, R)
(s2 , b, s2 , a, R) (s1 , #, s3 , #, R).
(5) Find the rule that corresponds to the string aaabababbaa.
(6) Find the rule that corresponds to the string aabbbaaabbab.
(7) Which of the following strings correspond to rules?
(a) baaabbaabb
(b) aabbbaaabbbb

<<

. 7
( 9)



>>