Please explain to me (like I'm an idiot) how the problem Does M on input Λ ever write a nonblank symbol on the tape? given TM M as an input is decidable.

To clarify, how do I show that the question is decidable


Start simulating the TM. Let $N$ be the number of its states.

If the simulation reaches halt or actually does write a nonblank, we are done with the obvious result.

If the simulation ever erases a previously non-blank field we are done because we may assume by induction that we have decidability for all inputs with less nonblank fields.

If we ever stay to the right of the last (or to the left of the first) nonblank tape position for more than $N^2+N+1$ consecutive steps, we are done: The machine can move at most $N$ steps to the right before repeating its state (note: it sees blank input all the time). If the second occurrence is closer to "home" than the first, it will keep moving closer with a net gain of at least one position per $N$ steps, thus will be back after less than $N^2+N+1$ steps. Thus being "far out" for $N^2+N+1$ steps mean that the repeated state happens at the same or a further ut position; hence the machine will loop indefinitely, either essentially in-place, or drifting away into infinity.

Therefore, the whole simulation need only work with a finite tape, namely the input area, extended to the left and right by $N^2+N$ blank fields. But with everything finite, it is clear that the simulation is eventully periodic.

  • $\begingroup$ If we ever stay to the right of the last (or to the left of the first) nonblank tape position for more than N2+N+1N2+N+1 what is the proof for that? $\endgroup$ – Artemis May 1 '18 at 18:41
  • $\begingroup$ The "$N^2+N$ blank fields" bound seems very conservative. I think that as soon as we're reached $2N+1$ squares into blank territory we can write the machine off. If we get that far, then by the pigeonhole principle, the first visit to two of the last $N+1$ squares must have been in the same state, and there are not enough states for the machine to have gone back to read something non-blank between them. $\endgroup$ – Henning Makholm May 1 '18 at 18:41

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.