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

328 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13

The above action byMmay be described by a five-letter expression called aquintuplewhich we define

below.

Definition 13.5: A quintupleqis a five-letter expression of the following form:

q=

(

si,ak,al,sj,

{

L

R

})

That is, the first letter ofqis a state symbol, the second is a tape symbol, the third is a tape symbol, the fourth

is a state symbol, and the last is a direction symbolLorR.

Next we give a formal definition of a Turing machine.

Definition 13.6:A Turing machineMis a finite set of quintuples such that:

(i) No two quintuples begin with the same first two letters.

(ii) No quintuple begins withsH,sY,orsN.

Condition (i) in the definition guarantees that the machineMcannot do more than one thing at any given

step, and condition (ii) guarantees thatMhalts in statesH,sY,orsN.

The following is an alternative equivalent definition.

Definition 13.6

′

: Turing machineMis a partial function from

S\{sH,sYorsN}×A into A×S×d

The term partial function simply means that domain ofMis a subset ofS\{sH,sY,orsN}×A.

The action of the Turing machine described above can now be formally defined.

Definition 13.7: Letαandβbe pictures. We write

α→β

if one of the following holds wherea,b,care tape letters andPandQare tape expressions (possibly empty):

(i) α=PsiacQ,β=PbsjcQandMcontains the quintupleq=siabsjR.

(ii) α=PcsiaQ,β=PsjcbQandMcontains the quintupleq=siabsjL.

(iii) α=Psia,β=PbsjBandMcontains the quintupleq=siabsjR.

(iv) α=siaQ,β=sjBbQandMcontains the quintupleq=siabsjL.

Observe that, in all four cases,Mreplacesaon the tape byb(where we permitb=a), andMchanges its

state fromsitosj(where we permitsj=si). Furthermore:

(i) HereMmoves to the right.

(ii) HereMmoves to the left.

(iii) HereMmoves to the right; however, sinceMis scanning the rightmost letter, it must add the blank symbol
Bon the right.

(iv) HereMmoves to the left; however, sinceMis scanning the leftmost letter, it must add the blank symbolB

on the left.

Definition 13.8: A pictureαis said to beterminalif there is no pictureβsuch thatα→β.

In particular, any pictureαin one of the three halt states must be terminal since no quintuple begins withsH,

sYorsn.