A common definition of a Turing Machine allows for the machine to not move after

Question

A common definition of a Turing Machine allows for the machine to not move after reading a symbol, instead of always having to move one cell to the left or to the right. Consider a variant Turing Machine whose transition function may also produce a triple Delta function (q, s) = (q^1, a^1, S), where the.S indicates that the read/write head of the TM does not move. Describe how a standard 1-tape Turing machine can be used to simulate the running of one of these variant (but still 1-tape) machines. More precisely, given a specification T = (Q, Sigma, Delta function q_8, q_accept, q_reject) of a variant TM, give a definition of a standard TM T' which essentially does the same things that T does.

Explanation / Answer

Consider the following answer:
B1 Let L be a regular language over an alphabet . Show that there is some TM that decides L.
Solution: Let M = (Q, , , q0, F) be a DFA that accepts L and let M0
be the TM (Q {qaccept, qreject), , {t}, 0
, q0, qaccept, qreject), where
• if (q, a) = (q0,a0),then 0(q, a)=(q0,a,R),for any qQ and
a ,
• if q F,then 0(q, t)=(qaccep,t,R),and

• if q / F then 0 (q, t) = (qreject, t, R).
Then M0 decides L.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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