Construct a turing machine that accepts L = {ww : w belongs to {a,b}*}

Question

Construct a Turing machine that accepts $L = \{ww : w \in \{a,b\}^*\}$?

Answer 1

Can you write a machine that turns $$ \ldots 0 0 0 x \alpha y 0 \beta 0 \gamma 0 0 0\ldots$$ (where $x,y\in \{a,b\}$ and $\alpha,\beta,\gamma\in\{a,b\}^\star$) into $$ \ldots 0 0 0 \alpha 0 x\beta 0 y\gamma 0 0 0 \ldots$$ and the halts in a REJECT state if it sees $$ \ldots 0 0 0 x 0 \ldots$$ ?

Can you write a machine that turns $$ \ldots \alpha x 0 y \beta\ldots$$ into $$ \ldots \alpha 0 \beta\ldots$$ if $x=y$ and halts with REJECT if $x\ne y$?

Answer 2

First check whether the input word is even. If so, construct a new word next to the input word by removing alternately the first and last letter from your input word and appending it to your new word. When you're done, check whether the new word is a palindrome.