Turing machine which can find the center of a string

Question

Is it possible to do it in $O(n \log n )$ ? or is the best solution $O(n^2)$? if yes, what's the idea to do so ?

Answer 1

If the alphabet is big enough, something like this might do:

The given string consists only of $X$. We use three more symbols $A,B,C$ to indicate $X$ where two flags $\alpha$, $\beta$ are set or not ($X=$ no flag set, $A=$ flag $\alpha$ set, $B=$ flag $\beta$ set, $C=$ both flags set). Moreover, $M$ is supposed to be written at the middle position, and we use another symbol $Y$ as an intermediate boundary marker.

From left to right, on every second $X$ set flag $\alpha$. From right to left, on every second $X$ set flag $\beta$.

From left to right, reset the first, third, fifth, etc. set $\alpha$ flag. From right to left, reset the first, third, fifth, etc. set $\beta$ flag. Repeat these rounds (each time halving the number of set flags) until only ony $\alpha $ (and one $\beta$) flag are set.

Scan for the first set flag. If both $\alpha$ and $\beta$ are set, this is the middle position, write $M$ and terminate (or preferably make one additional run replacing all $Y,A,B,C$ with $X$ for cleanup first). Otherwise, write $Y$, proceed to the right to the next set flag, write $Y$, move back left to the other $Y$.

If these two $Y$ were on adjacent fields, the length was even and the middle consists of two fields (namely, these two $Y$'s). In that case, convert these two $Y$ to $M$ cleanup all other $Y,A,B,C$ to $X$ and terminate.

Repeat all of the above, but now applied only to the string between these $Y$ markers.

Note that for $2^k\le n<2^{k+1}$, we use $k$ rounds, i.e., $O(nk)$ steps to reduce the problem to a string of length $n'<2^k$. This gives us the desired runtime $O(n\log n)$.

---

Here's an example, what happens with an input of length $19$ (red marks the position of the head and only crucial steps between loops are shown): $$\color{red}\#XXXXXXXXXXXXXXXXXXX\# $$ $$\#XAXAXAXAXAXAXAXAXAX\color{red}\# $$ $$\color{red}\#XCXCXCXCXCXCXCXCXCX\# $$ $$\#XBXCXBXCXBXCXBXCXBX\color{red}\# $$ $$\color{red}\#XXXCXXXCXXXCXXXCXXX\# $$ $$\#XXXBXXXCXXXBXXXCXXX\color{red}\# $$ $$\color{red}\#XXXBXXXAXXXBXXXAXXX\# $$ $$\#XXXBXXXXXXXBXXXAXXX\color{red}\# $$ $$\color{red}\#XXXBXXXXXXXXXXXAXXX\# $$ $$\#XXXYXXXXXXXXXXX\color{red}YXXX\# $$ $$\#XXX\color{red}YXXXXXXXXXXXYXXX\# $$ $$\#XXXYXAXAXAXAXAX\color{red}YXXX\# $$ $$\#XXX\color{red}YXCXCXCXCXCXYXXX\# $$ $$\#XXXYXBXCXBXCXBX\color{red}YXXX\# $$ $$\#XXX\color{red}YXXXCXXXCXXXYXXX\# $$ $$\#XXXYXXXBXXXCXXX\color{red}YXXX\# $$ $$\#XXX\color{red}YXXXBXXXAXXXYXXX\# $$ $$\#XXXYXXXYXXX\color{red}YXXXYXXX\# $$ $$\#XXXYXXX\color{red}YXXXYXXXYXXX\# $$ $$\#XXXYXXXYXAX\color{red}YXXXYXXX\# $$ $$\#XXXYXXX\color{red}YXCXYXXXYXXX\# $$ $$\#XXXYXXXYX\color{red}MXYXXXYXXX\# $$ $$\color{red}\#XXXXXXXXXMXXXXXXXXX\# $$