Turing machine that can tell if it ends in standard position?

Question

Suppose we have a TM $M$ with alphabet $\{0, 1 \}$ with n states. Say $M$ halts in standard position if it is scanning the left-most $1$ of a non-broken string of $1$s (and everything else on the tape is $0$.

Suppose the tape is initially consists of a bunch of $1$s, a $0$, a bunch of $1$s, a $0$, and so on for a finite number of $1$ and then the rest is $0$. $M$ is initially scanning the left-most $1$.

Is there a turing machine that can appended to this guy so that, whenever it is about to halt, it checks if it is in standard position? If it is standard position, then it returns to standard position and halts. If it is not in standard position, then it does not halt. This standard position checking could depend on the turing machine (and probably had to depend on the number of states at least) but should not depend on the initial state of the tape.

I thought that arguing that the TM only has to check $n+1$ $0$s beyond the last $1$ in either direction because the turing machine cannot add a $1$ that far away from the last $1$, but there are counter examples. For example, there is a 3-state machine that, when given the tape 100 _ 1, it changes $1$ to $0$ for "spots" 2-100 and then halts at the second argument.

Answer 1

In most of the models of Turing Machines there is a separate blank symbol $B$. Sometimes we may even have a start symbol $\rhd$. This makes it easy to check if $M$ halts in standard position.

If $0$ is also treated as the blank symbol, and the tape is initialized with 0's on both side of inputs (with no separate blank symbol) then the analysis of computation becomes a little bit difficult (Where is the boundary?).

In your case, it is doable without much hassle as 0's in the input always occur singly. First rewrite the whole input as 2-bit alphabet, converting 0 to 10 and 1 to 11, B will be 00 and start symbol $\rhd$ will be 01. Now we are happy to go. We just need to modify the Turing Machine to consider 2 bits at a time.

Answer 2

If your TM is about to halt, do as follows:

• Check it is reading a 1, if not, go loop
• Go back to the start of the tape (might have to mark it somehow and shift everything over when starting), skipping only 0s. If you find a 1, go loop.
• Advance until you see the first 1. Advance over a stretch of 1 (to reach a 0 or blank)
• If you reached a blank, the tape ends in 1s. Go back to the last 0 (or tape start), advance one space and halt
• If you reached 0, the used tape should end in 0s. Read to the end of the used tape. If you hit a 1, go loop.
• Upon finding a blank, go right over 0s, then 1s, stop at the first 0 (or tape start).
• Move right one space (to the first 1), and halt