[Math] Design a Turing Machine which finds center of a given string with even length

automataturing-machines

A Turing machine is an abstract machine that manipulates symbols on a strip of tape according to a table of rules; to be more exact, it is a mathematical model of computation that defines such a device. (Wikipedia)

Now the question is :
Design a Turing Machine which finds center of a given string with even length.

Note : For example if the given string is $w=a_1a_2\dots a_na_{n+1}\dots a_{2n} \space\space\forall i \space a_i\in \Sigma$, then the turing machine returns $w'=a_1a_2\dots a_nca_{n+1}\dots a_{2n}\space\space c\in\Gamma-\Sigma$ where $\Sigma$ is the alphabet and $\Gamma$ is the Stack Alphabet ( often called tape alphabet ).

Thanks in advance.

Best Answer

A general strategy could be something like:

  1. Put a $c$ at each end of the string.
  2. Keep interchanging the left $c$ with the symbol to the right of it, and the right $c$ with the symbol to the left of it, until there are no more symbols between them. (While you move from one end of the string to the other, you don't need to remember any details about the end you are leaving; everything you need once you get back there is encoded in the symbols on the tape).
  3. Delete one of the two $c$s, and shift each symbol to the right of it one position to the left, until you see empty space.
Related Question