1
$\begingroup$

I am going to design a Turing machine for doubling any words. My algorithm is such that for word X as input, the output will be in the form X@X which @ is a character. How can design an one-tape Turing machine that give exactly XX as its output? For example, X=abba, XX=abbaabba. Thank you in advance for consideration.

$\endgroup$
1
1
$\begingroup$

Design a Turing machine $T$ that takes as an input a word with an unique occurrence of the "@" symbol and shifts all symbols after "@" one position to their left (thus overwriting "@" and replacing the last symbol of the word with the blank symbol).

This can be done by finding the end of the input word, setting the machine state to store the "blank" symbol, moving to the left, and then iteratively performing the following step:

  • simultaneously store the current symbol in the machine state, write the stored symbol on the current cell of the tape, and move left.

The above repeats until the read symbol is "@". When that happens the stored symbol is written in place of "@" and the machine halts.

Compose the Turing machine you already designed with $T$.

$\endgroup$
2
  • $\begingroup$ Thsnks for your answer! Is it possible to do this work without composing two machines? I mean by using one and only one Turing machine? $\endgroup$
    – Aram
    Sep 11 '21 at 12:40
  • $\begingroup$ The second machine $T$ is just there for the sake of presentation. Of course the you can use a single machine that first does what you've already done and then what I described. $\endgroup$
    – Steven
    Sep 11 '21 at 12:45

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.