a) Consider the problem of testing whether a turing machine M on an input w ever

Question

a) Consider the problem of testing whether a turing machine M on an input w ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language at show that it is undecidable

b) Consider the problem of testing whether a turing machine M on an input w ever attempts to move its head left at any point during it computation on w. Formulate this problem as a language at show that it is decidable

Please don't copy and paste from some other source. I would prefer handwritten clearly explained work, not a paste from some google search.

Explanation / Answer

(b)

Solution:

In order to determine whether Turing machine moves his head in the left direction or not, user defines the problem in language explained.

LTM = {(M, w) | M attempts to move in head left when it is head in the left while computing w}

build the Turing Machine L as below way.

Thus the LTM   problem is decidble.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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