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.
$\begingroup$ $\endgroup$
0 
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
2 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.
- $\begingroup$ Yes, that'll do, tx. However, can we state that with a single tape it is not doable? $\endgroup$Joezer– Joezer2017-09-13 13:54:26 +00:00Commented Sep 13, 2017 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– adrianN2017-09-13 13:57:54 +00:00Commented Sep 13, 2017 at 13:57