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

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 333

(b) Mis in states 2 and scanning the last letter of the tape expressionw=abca.

(c) The input is the tape expressionw= 14 B 12.

The pictureαis obtained by placing the state symbol before the tape letter being scanned. Initially,Mis in

states 0 scanning the first letter of an input. Thus:

(a) α=aas 3 bca;(b)α=abcs 2 a;(c)α=s 01111 B11.

13.4. Supposeα=aas 2 bais a picture. Findβsuch thatα→βif the Turing machineMhas the quintuple

qwhere: (a)q=s 2 bas 1 L;(b)q=s 2 bbs 3 R;(c)q=s 2 bas 2 R;(d)q=s 3 abs 1 L.

(a) HereMerasesband writesa, changes its state tos 1 , and moves left. Thusβ=as 1 aaa.

(b) HereMdoes not change the scanned letterb, changes its state tos 3 , and moves right. Thusβ=aabs 3 a.

(c) HereMerasesband writesa, keeps its states 2 , and moves right. Thusβ=aaas 2 a.

(d) Hereqhas no effect onαsinceqdoes not begin withs 2 b.

13.5. LetA={a, b}and letL={arbs|r> 0 ,s > 0 }, that is,Lconsists of all wordsWbeginning with one

or morea’s and followed by one or moreb’s. Find a Turing machineMwhich recognizesL.

The strategy is that we wantMto: (1) move right over all thea’s; (2) move right over theb’s, and (3) halt in the

accepting statesYwhen it meets the blank symbolB. The following quintuples do this:

q 1 =s 0 aas 1 R, q 2 =s 1 aas 1 R, q 3 =s 1 bbs 2 R, q 4 =s 2 bbs 2 R, q 5 =s 2 BBsYR,

Specifically,q 1 andq 2 do (1),q 3 andq 4 do (2), andq 5 does (3).

However, we also wantMto non-accept an input wordWwhich does not belong toL. Thus we also need the

following quintuples:

q 6 =s 0 BBsNR, q 7 =s 0 bbsNR, q 8 =s 1 BBsNR, q 9 =s 2 aasNR

Hereq 6 is used if the inputW=λ=B, the empty word;q 7 is used if the inputWis an expression beginning with b;

q 8 is used if the inputWonly containsa’s; andq 9 is used if the inputWcontains the letter a following a letterb.

COMPUTABLE FUNCTIONS

13.6. Find〈m〉if: (a)m=5; (b)m=( 4 , 0 , 3 );(c)m=( 3 ,− 2 , 5 ).

Recall〈n〉= 1 n+^1 = 11 nand〈(n 1 ,n 2 ,...nr)〉=〈n 1 〉B〈n 2 〉B···B〈nr〉. Thus:

(a) 〈m〉= 16 = 111111

(b) 〈m〉= 15 B 11 B 14 = 11111 B 1 B 1111

(c) 〈m〉is not defined for negative integers.

13.7. Find [E] for the expressions:

(a) E=alls 2 Bb111; (c)E=〈m〉wherem=( 4 , 1 , 2 );

(b) E=aas 3 bb;(d)E=〈m〉wherem=(n 1 ,n 2 ,...,nr).

Recall that [E] counts the number of 1s inE. Thus:

(a) [E]=5; (b)[E]=0; (c)[E]=10 sinceE= 15 B1^2 B 13 ;

(d) [E]=n 1 +n 2 +···+nr+rsince the number of 1s contributed by eachnktoEisnk+1.

13.8. Letfbe the functionf (n)=n−1 whenn>0 andf( 0 )=0. Show thatfis computable.

We need to find a Turing machineMwhich computesf. Specifically, we wantMto erase two of the 1s in the

input〈n〉whenn>0, but only one 1 whenn=0. This is accomplished with the following quintuples:

q 1 =s 01 Bs 1 R, q 2 =s 1 BBsHR, q 3 =s 11 BsHR

Hereq 1 erases the first 1 and movesMright. If there is only one 1, thenMis now scanning a blank symbolBand

q 2 tells the computer to halt. Otherwise,q 3 erases the second 1 and haltsM.