1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Apr 8 at 17:09
  • $\begingroup$ @D.W. I am asking here because nobody else replies and it could be helpful to other students in the future who appear to have the same question, I agree with you that in this case the answer could be a yes/no, but I disagree with the fact that it won't help me, I am studying hard for an exam and having these type of replies would help me find out if I am prepared or not (and fix my solutions), I also believe that these type of questions are useful to other students who find themselves having to solve the same problem, I will try to edit the question in a better way! $\endgroup$
    – Stecco
    Apr 8 at 19:33

1 Answer 1

2
$\begingroup$

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...

$\endgroup$
1
  • $\begingroup$ Oh thanks, I didn't think that M could do that, but makes perfect sense what you have suggested! However I do not entirely understand your tip "fiddle around with the tape alphabet", do you mean I should define better the language of N? Thank you for the help! $\endgroup$
    – Stecco
    Apr 8 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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