The print problem: How to show it is not decidable?

797 Views Asked by At

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!

1

There are 1 best solutions below

7
On BEST ANSWER

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.