Studying for an exam and considering the general set of languages that solve the problem of whether or not some condition is fulfilled while processing a string.

I consider the language L_overwrite which solves the problem of if one arbitrary character overwrites another different one.

I'll call these arbitrary characters x and y. The problem is then: "Does y ever overwrite x?".

To attempt at solving this problem I've tried a reduction from A_tm. I consider altering the input TM by moving all transitions to the q_accept to q_reject; then any time y would be overridden by x move to q_accept. This is what the total function 'f' does. Additionally to handle the case where the input does not encode for a Turing machine M and a valid input string w then the function outputs the empty string.

I'm stuck attempting to prove that where z is a string constructed from the alphabet that: f(z) is an element of Overwrite_tm iff x is an element of A_tm.

Have I shot myself in the foot with my chosen function? If not, how do I move forward?

Thank you for the help.

I've looked at the following two questions:

Determining if a TM decidable or not, with limited information

Turing machine M overwrites a non-blank char by B (Blank)?

  • $\begingroup$ You are reducing in the "wrong direction". In order to prove that a language is undecidable, you have to show that you would be able to solve the halting problem if you had an oracle for it. Notice that you're doing the vice-versa. $\endgroup$ – quicksort Apr 15 '18 at 17:32
  • $\begingroup$ I'm attempting a many to one reduction. To be clear you're suggesting that I say "Overwrite_tm is reducible to A_tm" instead of "A_tm is reducible to Overwrite_tm"? $\endgroup$ – Parker Wieck Apr 15 '18 at 17:42

Your Answer

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

Browse other questions tagged or ask your own question.