0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Commented May 7, 2020 at 20:18

1 Answer 1

Reset to default
1
$\begingroup$

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.

Repeat the following:

  • Go back to towards the beginning of the input until you find a marked position on the work tape.
  • If the position immediately to the right is already marked, report the current position as the middle of the input.
  • Otherwise, remove the mark from the current position (i.e., write the empty symbol), move right, and mark the current position.
  • Advance towards the end of the input until you find a marked position on the work tape.
  • If the position immediately to the left is already marked, report that position as the middle of the input.
  • Otherwise, remove the mark from the current position, move left, and mark the current position.
Improve this answer
$\endgroup$
2
  • $\begingroup$ Do I understand correctly? For n=6, working tape looks like x----x, -x--x-, --xx--. At any point in time there are at most 2 cells used. $\endgroup$ Commented May 7, 2020 at 20:28
  • $\begingroup$ Yes, that's exactly the idea. Each iteration discards one cell from the left and one cell from the right by moving the marks closed to the center. $\endgroup$ Commented May 7, 2020 at 20:30

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.