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>:
- Build a new Turing Machine N as follows
- Execute decisor H on input
- Return the output
N = On any input:
- 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