Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 327

Basic Definitions

ATuring machineMinvolves three disjoint nonempty sets:

(1) A finitetapeset whereB=a 0 is the “blank” symbol:

A={a 1 ,a 2 ,...,am}∪{B}

(2) A finitestateset wheres 0 is theinitial state:

S={s 1 ,s 2 ,...,sn}∪{s 0 }∪{sH,sY,sN}

HeresH(HALT) is the halting state,sY(YES) is the accepting state, andsN(NO) is the nonaccepting

state.

(3) Adirectionset whereLdenotes “left” andRdenotes “right:”

d={L, R}

Definition 13.1: Anexpressionis a finite (possibly empty) sequence of elements fromA∪S∪d.

In other words, an expression is a word whose letters (symbols) come from the setsA,S, andd.

Definition 13.2:Atape expressionis an expression using only elements from the tape setA.

The Turing machineMmay be viewed as a read/write tape head which moves back and forth along an infinite
tape. The tape is divided lengthwise into squares (cells), and each square may be blank or hold one tape symbol.
At each step in time, the Turing machineMis in a certain internal statesiscanning one of the tape symbolsaj
on the tape. We assume that only a finite number of nonblank symbols appear on the tape.
Figure 13-3(a) is a picture of a Turing machineMin states 2 scanning the second symbol wherea 1 a 3 Ba 1 a 1
is printed on the tape. (Note again thatBis the blank symbol.) This picture may be represented by the expression
α=a 1 s 2 a 3 Ba 1 a 1 where we write the states 2 ofMbefore the tape symbola 3 thatMis scanning. Observe that
αis an expression using only the tape alphabetAexcept for the state symbols 2 which is not at the end of the
expression since it appears before the tape symbola 3 thatMis scanning. Figure 13-3 shows two other informal
pictures and their corresponding picture expressions.

Fig. 13-3

We give formal definitions.

Definition 13.3: Apictureαis an expression as follows wherePandQare tape expressions (possibly empty):

α=PsiakQ

Definition 13.4: Letα=PsiakQbe a picture. We say that the Turing machineMis in statesiscanning the
letterakand that theexpression on the tapeis the expressionPakQ, that is, without its state symbolsi.

As mentioned above, at each step in time the Turing machineMis in a certain statesiand is scanning a tape
symbolak. The Turing machineMis able to do the following three things simultaneously:

(i) Merases the scanned symbolakand writes in its place a tape symbolal(where we permital=ak).

(ii) Mchanges its internal statessito a statesj(where we permitsj=sj).

(iii)Mmovesonesquaretotheleftormovesonesquaretotheright.