2
$\begingroup$

Is it possible to find a TM with O(n) complexity that finds the middle of an input string? Or at least to prove that it cannot be done?

I can use a two-taped TM if it helps.

$\endgroup$
2
$\begingroup$

With a two tape TM it is not difficult:

Move to the right on the input tape. Every second step write something to the secondary tape. Once you reach a blank on the input tape (i.e. the end of the input), start moving to the left on the input tape. Each step delete a symbol from the secondary tape. You have reached the middle if the second tape is empty.

$\endgroup$
  • $\begingroup$ Yes, that'll do, tx. However, can we state that with a single tape it is not doable? $\endgroup$ – Joezer Sep 13 '17 at 13:54
  • 1
    $\begingroup$ My intuition says its not possible in linear time without a second tape, but I'm bad at lower bound proofs. $\endgroup$ – adrianN Sep 13 '17 at 13:57

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.