# k-tape turing machine

I want to create multi-tape Turing machine that recognize language {ww, $w \in {a,b}$}. With condition that max. steps is less or equal than $\frac{3}{2}\left | x \right | + 2$. Where x is word from language. I have an idea to create x-tapes to solve this problem, but can be the number of tapes not known before reading from input(read-only) tape, and for n-length there will be n-tapes, is that possible ?

• Should the machine be deterministic or can it be nondeterministic? (see your comment to the answer by David.) – Hendrik Jan Dec 6 '15 at 14:04
• Deterministic or nondeterministic. Both types are allowed. – POC Dec 6 '15 at 14:15
• Then you own suggestion in the comment works! From input tape copy to tape 1, guess middle, then copy remainder to tape 2. This takes $|x|$ steps. Now the heads on tapes 1 and 2 are at the end of the "halves", then check in reverse. Either the two parts are the same, or you discover they are unequal in time at most the shortest of the two halves. Plus a few steps for bookkeeping and changing direction. – Hendrik Jan Dec 6 '15 at 14:24