Consider a Turing machine whose head can read two consecutive cells at the same

Question

Consider a Turing machine whose head can read two consecutive cells at the same time. The transition function for this machine is of the form delta: (q_i, a, b) = (q_j, c, d, {L, R}). This can be interpreted as when in state q_i, if the contents of the two cells beneath the head are a and b respectively then enter state q_j, change the contents of the two cells to c and d respectively, and then move the head one cell position cither left or right. Explain how this new definition is equivalent to the standard definition of Turing machines.

Explanation / Answer

TM definition of a Turing Machine is as a 7-tuple (S, A, I, T, q0, B, F) where -

S = { qi ,qj ) is finite set of states

A = { a,b,c,d, _ } is the set of allowed symbols on tape

I = { a,b } is the input alphabet

T : (qi,a,b) = (qj,c,d,{Left_shift, Right_shift}) is the transition function .

q0 :{qi} is the initial state .

B : { _ } is the blank symbol . Underscore is taken just as an example , it can be any other as per circumstances .

F : {qj} is the set of final states

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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