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 ?
3
-
$\begingroup$ Should the machine be deterministic or can it be nondeterministic? (see your comment to the answer by David.) $\endgroup$– Hendrik JanCommented Dec 6, 2015 at 14:04
-
$\begingroup$ Deterministic or nondeterministic. Both types are allowed. $\endgroup$– POCCommented Dec 6, 2015 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 JanCommented Dec 6, 2015 at 14:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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!
answered Dec 6, 2015 at 10:08
-
$\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$– POCCommented Dec 6, 2015 at 10:38