<p>It cannot be computed in time $o(n\lg n)$.</p>

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

<p>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.</p>

<p>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)$.</p>

CC BY-SA 3.0
2013-09-16T14:02:51.250Z
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
CC BY-SA 3.0
2013-09-16T17:16:12.083Z
@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](http://cstheory.stackexchange.com/q/10990/186). 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
CC BY-SA 3.0
2013-09-17T13:23:58.920Z
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
CC BY-SA 3.0
2013-09-17T17:56:43.997Z
@Bruno, I think what is the more common definition of [DTime](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#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
CC BY-SA 3.0
2013-09-18T09:07:51.390Z
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
CC BY-SA 3.0
2013-09-15T06:24:58.837Z
2013-09-15T21:36:01.293Z
2013-09-15T21:36:01.293Z
Kaveh
<p>In connection with <a href="https://cstheory.stackexchange.com/questions/18969/can-we-compute-n-from-the-binary-digits-of-3n-in-on-time">this question</a> 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.</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2013-09-14T03:12:30.650Z
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
<turing-machines>
Computing input length on a one-tape Turing machine
David Eppstein
# Computing input length on a one-tape Turing machine

(Asked by: username_0 on 2013-09-13)

In connection with [this question](https://cstheory.stackexchange.com/questions/18969/can-we-compute-n-from-the-binary-digits-of-3n-in-on-time) 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.

**Tags:** turing-machines
> **Comments:**
> **username_1**: 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).)  

---

## 1 answers

### Answer by username_2 on 2013-09-15. Score: 12 | Accepted answer

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)$.

> **Comments:**
> **username_3**: 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?  
> **username_2**: @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](http://cstheory.stackexchange.com/q/10990/186). For $\mathsf{DTime}(n \lg n) = \mathsf{Reg}$ you can find it in "Classical Recursion Theory" vol. II and "Handbook of Theoretical Computer Science".  
> **username_3**: 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.  
> **username_2**: @Bruno, I think what is the more common definition of [DTime](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#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.  
> **username_3**: 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.  

---

