A Turing machine both writes to its tape and moves left or right with each trans

Question

A Turing machine both writes to its tape and moves left or right with each transition. The output of the transition function includes both an element of Gamma symbol specifying the symbol to write to the tape, and an element of the set {L, R}, specifying a direction to move the head.

In this problem, we consider a more limited Turing machine that can either write to its tape or move its head, but not both, in each transition. For these machines, the output of the machine will include an element of ( Gamma U {perpendicular symbol}), with perpendicular symbol a special symbol meaning do not write to tape, as well as an element of {L, R, perpendicular symbol}, with perpendicular symbol a special symbol meaning do not move the head. All together:

Delta: (Q {qaccept, qreject}) x gamma -> Q x (gamma U {perpendicular symbol}) x {L, R, perpendicular symbol}

We require that  the output of the transition function have  perpendicular symbol either in place of a symbol to write or in place of a direction  to move, but  not  both, the  machine  must  either write to tape or move its head.

a.  Turing  machines  that  can  either  write  or move are  described  using the  same 7- tuple  as the  ordinary  Turing  machines  in Sipser (book), except for the  modification  to delta given above.  The  start  configurations  and accepting configurations  are the same as for ordinary  Turing  machines.  However, the rules for how a configuration Ci  yields a configuration Ci+1 are different.

Give the rules for how Ci  yields Ci+1 for a Turing  machine that  can either write or move, including the special-case rules that apply when the machine's read head is close to either edge of the area it has used so far on the tape.

b.  Explain how to simulate  a Turing  machine that  can either write or move (but  not both at once) on an ordinary Turing machine (that can both write and move with each transition).

c.  Explain how to simulate an ordinary Turing machine (that can both write and move with each transition) on a Turing machine that can either write or move (but  not both at once).

I'm sorry there are titles in place for the actual symbols, I was not sure how to insert the specific symbols.

Explanation / Answer

Limited Turing Machine problem, explain how it can write or move and how to simulate it

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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