# Why is this TM problem decidable

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 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.
• 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? – Artemis May 1 '18 at 18:41
• 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. – Henning Makholm May 1 '18 at 18:41