World's most popular travel blog for travel bloggers.

# [Answers] Turing machine that can tell if it ends in standard position?

, ,
Problem Detail:

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.

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.