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.
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.