Does checking the middle bit of an input require a log(n) space pointer? (Reusing space)

Question

Let n be an even integer.

Let I be an input of length n.

Positions start at 0: the first bit is bit 0. The second bit is bit 1. etc.

The decision problem is, "Is bit n/2 equal to 1"?

The input is on a tape.

We have a single pointer to the input. We may move the pointer left or right. We cannot overwrite the input tape.

We have a single working-memory tape to compute with. We have a single pointer to it. We may write a 0 or a 1. We may move the pointer left or right. We may not move to the left of, or overwrite the start symbol of the working-memory tape. The working-memory tape is initialized to either the start symbol or immediately to the right.

Space-complexity is the position of the largest cell we write to. This way we "reuse" space.[1]

One way to decide the problem is with a counter of length O(log(n)): Initialize to 0's, then increment until the counter equals n/2, then check the bit.

That takes O(log(n)) space.

Can we do better? Or is O(log(n)) the best space-complexity we can do?

[1] If space complexity was just the total in-use space at any given point in time, we could "move around" the space we're using, using a larger total range of space, but only a smaller portion at any point in time. Defining space as the max position keeps us from "moving around" the space we're using.

Answer 1

You can do this using $O(1)$ space, using two pointers. Initially, the first pointer is at the left end of the input, and the second pointer is at its right end. Each round, advance both pointers toward the middle, until they meet. This requires no additional space at all!

(The latter, assuming we can enlarge the tape alphabet. Otherwise we can still make do with constant additional space, by implementing the pointers as spaces.)