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: