two tape Turing machine that accepts L = {ww | w belongs to {0,1}*} in Linear time

1k Views Asked by At

Describe a Turing Machine with two tapes that accepts $$L = \{ww \mid w \in \{0,1\}^*\} $$ in a linear time complexity. The input will be on Tape $\#1$ and the marker will point to the first element of the tape.

basically my idea was to copy the first string to the other going to the middle in the first tape, going to the start in the second tape and comparing the 1st half of the word with the second. but the problem is that there is no STAY operation for the marker, only Left or Right.

much appreciated.