Were being asked to determine the whether this Turing Machine is decidable or not

"Given a two way, one-tape DTM $M$ whose tape set is $\Gamma=${$a,b,B$} and a string $x\in${$a,b$}*, determine whether $M$ will ever overwrite a symbol $a$ by a symbol $b$ in its computation on input $x$"

I'm not looking for answers, just hints on how to even approach this problem. Like, would we declare a language which is a subset of that language, and then apply reducibility?


A TM cannot be "decidable". What you are asking is whether the language that you describe is decidable.

Hint: the language $A_{TM}=\{<M,w>: M \text{ accepts }w\}$ is undecidable even if we restrict to TMs with a binary work alphabet. Try to reduce from this problem, by utilizing only the letters $\{a,B\}$ from $\Gamma$. Then, you can use $b$ only when you need it.

Please comment if you need further hints.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.