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.

  • 1
    It's not even a hint :)2012-08-07
  • 0
    @Jozef, read my comment, can you figure it out now?2012-08-07
  • 0
    no, can you please extend your answer?2012-08-10
  • 0
    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?2012-08-10
  • 0
    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.2012-08-11
  • 0
    yes, but I wrote "otherwise" it "writes..."- what is this otherwise? if it rejected- fine, if it didn't stop with a result and in loop, also $M'$ would be in loop and until it doesn't stop it doesn't write blank, and it's fine. I should just emphasize it in my proof, do you get what I'm saying?2012-08-11
  • 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