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

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 cannot overwrite the input tape.

We have finite amount of working-memory tapes to compute with (in case more than 1 is useful).

Space-complexity is the maximum amount of non-empty tape cells to ever appear across all work tapes at any point during the execution.

(That way, in practice, this can correspond to virtualizing a Turing machine and adding or removing physical hard drives to back each logical working-memory tape.)

Each pointer can be moved left or right one cell.

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?

If we can do better, in general, then there's a system of representing integers more space-efficient than polynomial bases (decimal, binary, etc.).

For example, if we had access to the corresponding busy-beaver machine for n/2, then we could use that (and instead of printing out a 0, we could move our input tape by 1). However, in general, we cannot compute the (optimal) busy-beaver for n/2.

So, is there a way to compute a "sub-optimal busy-beaver" and use that to get to n/2 instead of a O(log(n)) counter?

• How do you define the space complexity? Is it the maximum amount of non-empty tape cells to ever appear across all work tapes at any point during the execution, or the total amount of distinct cells of work tapes that are ever written to during the whole execution? May 7 '20 at 20:18

You can do this with constant amount of memory (according to your definition of space complexity). Assume $$n \ge 2$$ (the complementary case is trivial). Mark the work tape on the starting position of the input, then move right until you reach the end of the input and mark the last position of the input on the work tape.