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 ?

  • $\begingroup$ Should the machine be deterministic or can it be nondeterministic? (see your comment to the answer by David.) $\endgroup$ – Hendrik Jan Dec 6 '15 at 14:04
  • $\begingroup$ Deterministic or nondeterministic. Both types are allowed. $\endgroup$ – POC Dec 6 '15 at 14:15
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Dec 6 '15 at 14:24

All Turing machines are fixed in advance, independent of the input. This applies to all aspects of the machine: the state set, the alphabet, the transition function, the number of tapes. The only thing that changes from input to input is the input!

| cite | improve this answer | |
  • $\begingroup$ Thanks, so this can't work, which algorithm should be used in the solution ? My next idea is to create non-deterministic one with two secondary tapes. We will pick the middle by non-determinism and copy first half into tape 1 and copy second half into tape 2, and then check if they are same. But this will satisfy the condition only if we pick the middle correct, so I think this is not the solution. $\endgroup$ – POC Dec 6 '15 at 10:38

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.