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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.