Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
You made a mistake: what happens when M already writes a blank during it's execution? – sxd Aug 6 '12 at 17:41
up vote 4 down vote accepted

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.

share|cite|improve this answer
It's not even a hint :) – Jozef Aug 7 '12 at 10:20
@Jozef, read my comment, can you figure it out now? – sxd Aug 7 '12 at 10:43
no, can you please extend your answer? – Jozef Aug 10 '12 at 19:18
Oh I get your hint- I can writ # instead of blank on running on M, but besides that the reduction isn't correct any way, what if M does not stops? right? – Jozef Aug 10 '12 at 19:42
That does not matter, since you are not running $M$, you are creating an other machine that runs $M$, these two situations are entirely different! Think about it! About my hint: Indeed, that is the only mistake you made! In the transition function of $M$ you have to replace the blank symbol with something different. Apart from that, your reduction is correct. – sxd Aug 11 '12 at 13:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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