TITLE: Turing machine which can find the center of a string
QUESTION [1 upvotes]: 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 ?

REPLY [2 votes]: 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\# $$
{"set_name": "stack_exchange", "score": 1, "question_id": 3418143}