1
$\begingroup$

Suppose I have a Turing machine that takes as input any string of length $n$, where $n$ is odd, and the Turing machine returns the middle character of the string.

What time complexity class is this in? Is it in $O(n)$ because the tape head must scan $n/2$ places to the right, counting as it goes, or is there a quicker, say $O(\log n)$ machine that could accomplish this task?

$\endgroup$
1
  • $\begingroup$ Certainly $\Omega(n)$ as the head must make at least $\frac n2$ moves (or more if $n$ is not given as an argument). Remains to check if there is an $O(n)$ program. $\endgroup$
    – user16034
    Commented Aug 11, 2022 at 13:56

1 Answer 1

1
$\begingroup$

For Turing machines with at least two tapes the problem can be solved in $\Theta(n)$ time, meaning that there exists a Turing machine that solves it using $O(n)$ steps and that all Turing machines must use $\Omega(n)$ steps (see also Yves Daoust's comment).

For Turing machines with one tape, the time needed to solve the problem is between $\Omega(n)$ and $O(n \log n)$.

The running time of your particular Turing machine depends on the details of the machine itself.

A possible two-tape Turing machine that requires time $O(n)$ works in multiple "rounds". Each round starts with the head placed on the first non-blank symbol of the tape and works as follows:

  • Check whether the tape contains a single (non-blank) symbol (i.e., the next symbol is blank). If so, halt (that symbol is exactly the sought one). Otherwise reset the head to the first symbol.

  • Determine whether the number $m$ of (non-blank) symbols currently on the tape is of the form $4k+1$ or $4k+3$, for some $k \in \mathbb{Z}$.

    • If $m=4k+1$, delete every other symbol in the tape (i.e., replace them with the blank symbol) starting with the second symbol. After this step the number of non blank symbols is $1 + \frac{m-1}{2} = 1 + \frac{4k}{2} = 2k+1$ and the middle non-blank symbol (i.e., the $k+1$-th symbol) is unaffected.

    • If $m=4k+3$, delete every other symbol in the tape starting with the first symbol. After this step the number of non blank symbols is $\frac{m-1}{2} = \frac{4k+2}{2} = 2k+1$ and the middle non-blank symbol is unaffected.

  • Now the tape consists of alternating blank and non-blank symbols. Compact all the non-blank symbols so that they are contiguous (using the second tape). Place the head on the first non-blank symbol and move to the next round.

To see that the running time is indeed $O(n)$, notice that the last round starts with only one symbol and requires constant time, while every other round has $1+\ell \ge 3$ symbols (i.e., the middle symbol plus $\ell$ "additional" symbols) and requires at most $c \ell$ steps (for some constant $c$ independent of $\ell$). Moreover each such round at least halves the number of additional symbols.

Initially $\ell=n-1$ and hence the overall number of steps is at most: $$ O(1) + \sum_{i=0}^{\infty} \frac{c(n-1)}{2^i} = O(1) + 2 c(n-1) = O(n). $$

A possible single-tape Turing machine that requires time $O(n \log n)$ also works in multiple "rounds". The idea of each round is as follows:

  • If the length of the input is smaller than a (sufficiently large constant) explicitly move to the middle character and halt.
  • Mark all the input cells with a "left" mark
  • While there are at least 6 marks, scan the tape from left to right and delete every other "left" mark starting from the leftmost one
  • Mark all the input cells with a "right" mark
  • While there are at least 6 marks, scan the tape from right to left and delete every other "right" mark starting from the rightmost one
  • Delete all symbols to the left of the leftmost "left" mark
  • Delete all symbols to the right of the rightmost "right" mark
  • Remove all marks, reset the head positions, and move to the next round (notice that the middle symbol has not changed).

Notice that each round (but the last) reduces the number of symbols by at least a constant fraction, and that a round with $m$ symbols requires $O(m \log m)$ time.

$\endgroup$
2
  • $\begingroup$ "Compact all the non-blank symbols so that they are contiguous." Please explain how you do that. How many steps are needed? $\endgroup$
    – John L.
    Commented Aug 11, 2022 at 19:32
  • $\begingroup$ @JohnL. Thanks for pointing this out. Indeed I don't know how to perform that step in linear time with a single tape (it is trivial if we have an extra working tape). I have edited the answer accordingly and sketched a $O(n \log n)$-time solution that works on a single tape. I'm not sure that linear-time "compaction" is possible at all: if it were, it would allow to prove the linear speedup theorem (whose tape "compression" step can be thought as replacing each block of symbols with a super-symbol and then compacting) also for single-tape TMs, but I only see it claimed for at least two tapes. $\endgroup$
    – Steven
    Commented Aug 11, 2022 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.