Prove that Turing Machine ever writes a blank symbol over a non blank symbol is undecidable

Question

I have been given the following problem from the book Introduction to the Theory of Computation by Martin Sipser and was wondering if my solution is correct: Determine if a Turing Machine ever writes a blank symbol over a non blank symbol over the course of its computation on whatever string given on input, formulate this problem as a language and prove that it is undecidable.

This is my solution:

The langauge is the following: L ={<M> | M is a single tape Turing Machine and M writes a blank symbol over a non blank symbol during the course of its computation on any input string}.

---

This is my solution to part 1.

Let's assume that L is a decidable language and H is its decisor, we can then prove that there exists a decisor for ATM (impossible!).

On input <M , w>:

1. Build a new Turing Machine N as follows
2. Execute decisor H on input
3. Return the output

N = On any input:

1. Execute M on input w and if it accepts write a blank symbol on a non blank symbol in the tape then accept otherwise reject

---

Answer 1

The overall structure of your proof is fine, but the construction of N is insufficient. You are making sure that if M halts, then N will overwrite a non-blank with a blank. However, you also need to make sure that if M does not halt, then N never overwrites a non-blank with a blank - but it might, because M might do that.

You'll want to fiddle around with the tape alphabet that N is using a bit to fix this. When M attempts to do overwrite a non-blank with a blank, N needs to do something that keeps the "spirit" of the algorithm but doesn't involve writing a blank...