Construct Turing Machine which accepts the language $ww$

Problem Detail: 

I try to construct a TM that accepts the language $\{ ww \mid w \in \{a,b\}^* \}$.

Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second $w$ begins.

Is there a trick for this?

Asked By : Kagutsuchi

Answered By : Klaus Draeger

Here is a sketch for how a deterministic machine might work:

1. place a marker in front of the input.
2. go through the input, checking if the length is even. If not, reject.
3. place a marker behind the input.
4. going back and forth, move the markers towards each other until they meet in the middle.
5. as long as the halves are nonempty, compare and erase their first letters and reject if not equal.
6. accept.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43639