n be an even integer.
i be an input of length
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.
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
So, is there a way to compute a "sub-optimal busy-beaver" and use that to get to
n/2 instead of a