14

In connection with this question it occurred to me to wonder: what is the time complexity for a single-tape single-head Turing machine to compute the length of its input? To be specific, let's say that the tape alphabet is $\{0,1,b\}$, the input is a string in $(0+1)^*$ surrounded by blanks, the machine starts at the leftmost input symbol, and it must terminate at the leftmost symbol of a string in $(0+1)^*$ (again surrounded by blanks) that gives the binary representation of the input length. This can also be thought of as the problem of converting a number from unary to binary.

It's easy to solve this on a two-tape machine or two-head machine in linear time (just scan the input with one head while using the other head to repeatedly increment a counter; incrementing is a constant amortized time operation). But the single-head solutions I can come up with are only $O(n\log n)$ (e.g. repeatedly increment a counter and then shift it by one position along the tape). Is there a matching lower bound?

I tried some searches but phrases like "one head" and "input length" are so common as to make it difficult to search the literature for known results on this problem.

Community
  • 1
David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • Interesting.. This is less obvious than it appears it should be.

    I'm curious if there's a relation between a lower bound for this and a lower bound for oblivious TM simulation. (Any TM solving this problem would, by definition, be oblivious (or have unnecessary code).)

     – Daniel Apon Sep 14 '13 at 03:12

1 Answers1

12

It cannot be computed in time $o(n\lg n)$.

Let $M$ be a machine which given an input string $x$ halts with the size of $x$ written in binary on the tape.

We can add a simple (zero-space linear-time) DFA to $M$ to check if the size of the input is a power of two: just check that the first bit is 1 and the rest is zero.

Let's assume that $M$ runs time $o(n \lg n)$. Then we can decide in time $o(n \lg n)$ that the size of input is a power of two. In other words, the following language is decidable in $\mathsf{DTime}(n \lg n)$. $$L = \{ 0^i \mid \exists k \ i = 2^k\}$$ It follows from $\mathsf{DTime}(o(n \lg n)) = \mathsf{Reg}$ that $L$ should be regular. But it is easy to check that the language is not regular. So $M$ cannot run in time $o(n \lg n)$.

Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • I miss something here: When you say that $\mathsf{DTime}(o(n\lg n))=\mathsf{Reg}$, are you considering computations on a single-tape machine? Usually I think, two-tape machines are used to define complexity classes. A very related question is where does the above result come from? – Bruno Sep 16 '13 at 14:02
  • @Bruno, yes, I am talking about single-tape Turing machines. I am not sure what is the standard to define the complexity classes, various books use different models. The original papers of complexity theory were using multiple-tape ones I think but it seems that has changed, see this. For $\mathsf{DTime}(n \lg n) = \mathsf{Reg}$ you can find it in "Classical Recursion Theory" vol. II and "Handbook of Theoretical Computer Science". – Kaveh Sep 16 '13 at 17:16
  • Thanks for the pointers, I had a look in "Classical Recursion Theory" vol. II. For the fact that it has changed, it is not so clear for me. For instance, Sipser's book uses single-tape TMs to define time complexity classes, but Hopcroft-Ullman's book and the most recent Arora-Barak's and Goldreich's use multitape TMs. – Bruno Sep 17 '13 at 13:23
  • 1
    @Bruno, I think what is the more common definition of DTime is more complicated. E.g. the commonly stated claim that "the time hierarchy theorem is not known to be tight" is only true for single-tape machines, for two-tape machines it has been known to be tight since 1982. – Kaveh Sep 17 '13 at 17:56
  • Actually, this consideration on the time hierarchy theorem only exists in textbooks using a single-tape TM as model (e.g. Sipser's). But in other ones, there is nothing about non-tightness (Arora-Barak, Goldreich, etc...). Of course, all of this is not of great importance, but it just seems to me that saying that $\mathsf{DTime}$ is usually defined using single-tape TMs is not true: some authors use single-tape TMs, some others use multitape TMs, and many authors are vague on this issue... In other words, there does not seem to be a consensus on this question. – Bruno Sep 18 '13 at 09:07