The actions of the machine are determined by a finite set of \"quintuples\" of t

Question

The actions of the machine are determined by a finite set of "quintuples" of the following form: (p, x: y, dir, q where p and q are states of the machine are symbols in the machine's alphabet, and x and y dir is a direction the RWH might move either L for left or R for right. Let T be the Turing Machine whose quintuples are: (4, 0:1, R, 3) 0, 0:0, R, 0) (2, 0:0, R, 4) (2, 1: 1, R, 0) (0, 1:0, R, 1) (4, 1:1, R, 4) (3, 0:1, R, 1) (1, 0:0, R, 2) (3, 1: 1, R, 2) (1, 1:0, R, 3) (a) Walk through the operation of machine T applied to the following input tapes. Assume the RWH starts in state s 0 reading the leftmost nonblank character (i) 001 10011 (ii) 111110 (iii) 1001010 Civ) 001 1001 (b) What function does this machine evaluate? That is, if the input tape contains the binary representation of the integer n, what is left on the tape when T halts? Hint: look at the input and output strings in decimal (c) The final state is 0,1 etc. Interpret this value as a function of the input integer n

Explanation / Answer

a) i) 101110011101

ii) 0101011110110

iii) 1101001010110

iv) 1010011001010

b) f(x,y) = x+y - n

c) f(x,y) = x+y-n =(0,1)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.