<< стр. 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
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
Suppose we began at the square of the letter we were replacing and wanted
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
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 # #
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

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)СОДЕРЖАНИЕ >>