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.

  • $\begingroup$ What progress have you made on this task yourself? Anything in particular you're stuck with? $\endgroup$ – Henning Makholm Jun 3 '16 at 15:37
  • $\begingroup$ @HenningMakholm I'm stuck on how to find the middle ... i mean how the head moves right and left on the tape to find the middle ... excuse me if this question is stupid... it's been 2 days since i've seen turing machines in my books :) $\endgroup$ – Arman Malekzadeh Jun 3 '16 at 15:51

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.