5
$\begingroup$

I wonder the following reduction is correct.

I'm trying to show that the following problem "PRINT_BLANK" is not decidable.

Input: (a coding of) Turing machine M. Question: Does the machine never types "blank" on the stripe when it runs on x?

An attempt for reduction: $AcceptProblem \leq PrintBlank: f(\langle M,x\rangle)= M'.$

Given $M$ and $x$, we'll construct $M'$: For an input $y$ for $M'_x$, $M'_x$ simulates running of M on $w$. if $M$ accepts $w$, $M'_x$ writes "blank" and accepts y, otherwise it writes $x$ itself on the tape and rejects.

Any help?

Thanks!

  • 0
    You made a mistake: what happens when M already writes a blank during it's execution?2012-08-06

1 Answers 1

4

HINT: to make your reduction work, you should alter $M$ slightly, can you figure out how? If not, let me know.

EDIT: What happens when M already writes a blank during it's execution.

  • 0
    Writing otherwise does not matter, since you only have to output a blank when $M$ halts and accepts. You are not running $M'$ you are simply constructing it. You are just given an instance for one problem, and generating an instance for another problem. In this case you construct $M'$, but you do not run $M$ while constructing $M'$ do you?2012-08-11