CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 329
Computing with a Turing Machine
The above is a static (one-step) description of a Turing machineM. Now we discuss its dynamics.Definition 13.9: Acomputationof a Turing machineMis a sequence of picturesα 1 ,α 2 ,...,αmsuch that
αi− 1 →αi, fori= 1 , 2 ,...,m, andαmis a terminal picture.
In other words, a computation is a sequence
α 0 →α 1 →α 2 →...→αm
which cannot be extended sinceαmis terminal. We will let term(α)denote the final picture of a computation
beginning withα. Thus term(α 0 )=αmin the above computation.
Turing Machines with Input
The following definition applies.Definition 13.10: Aninputfor a Turing machineMis a tape expressionW. Theinitial picturefor an inputW
isα(W)whereα(W)=s 0 (W ).
Observe that the initial pictureα(W)of the inputWis obtained by placing the initial states 0 in front of the
input tape expressionW. In other words, the Turing machineMbegins in its initial states 0 and it is scanning the
first letter ofW.
Definition 13.11: LetMbe aTuring machine and letWbe an input.We sayMhalts onWif there is a computation
beginning with the initial pictureα(W).
That is, given an inputW, we can form the initial pictureα(W)=s 0 (W )and applyMto obtain the sequence
α(W)→α 1 →α 2 →...Two things can happen:
(1)M halts onW.That is, the sequence ends with some terminal Pictureαr.
(2)M does not halt onW.That is, the sequence never ends.Grammars and Turing Machines
Turing machines may be used to recognize languages. Specifically, supposeMis a Turing machine with tape
setA. LetLbe the set of wordsWinAsuch thatMhalts in the accepting statesYwhenWis the input. We will
then writeL=L(M), and we will say thatMrecognizes the languageL. Thus an inputWdoes not belong to
L(M)ifMdoes not halt onWor ifMhalts onWbut not in the accepting statesY.
The following theorem is the main result of this subsection; its proof lies beyond the scope of this text.
Theorem 13.3: A languageLis recognizable by a Turing machineMif and only ifLis a type 0 language.
Remark:The reason for three halt states is thatsYandsNare used for recognizing languages, whereassHis
used for computations discussed in the next section.
EXAMPLE 13.3 SupposeaTuringmachineMwithtapesetA={a, b,c}containsthefollowingfourquintuples:
q 1 =s 0 aas 0 R, q 2 =s 0 bbs 0 R, q 3 =s 0 BBsNR, q 4 =s 0 ccsYR
(a) SupposeW=W(a,b,c)is an input Without anyc’s.
By the quintuplesq 1 andq 2 ,Mstays in states 0 and moves to the right until it encounters a blank
symbolB. ThenMchanges its state to the nonaccepting statesNand halts.
(b) SupposeW=W(a,b,c)is an input with at least onecsymbol.
By the quintupleq 4 , whenMinitially meets the firstcinWit changes its state to the accepting statesY
and halts.ThusMrecognizes the languageLof all wordsWina, b, cwith at least one letterc. That is,L=L(M).