<p>Like Emil says, the answer is yes, because the length (in binary) of the input string is actually computable by a deterministic logtime Turing machine, so is <em>a fortiori</em> in $\mathsf{FO}$.</p>

<p>You may find this stated as Lemma 13 of Buss's <a href="http://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean/paper.pdf">The Boolean formula value problem is in ALOGTIME</a>.  The idea, attributed to Dowd, is to use the query tape to do binary search (under the convention that the machine gets an "out of range" response if the query tape contains a binary number exceeding the length of the input).  I cut-and-paste the proof for quick reference (the number $n$ referenced in the proof is the length of the input, i.e., the desired output; the "index tape" is what Emil and I called query tape):</p>

<blockquote>
  <p>The [...] Turing machine proceeds as follows. First determine the least value of $i$ such that $n &lt; 2^i$: this is easily done in $O(\log n)$ time since we assume that the index tape and its tape head are unaffected when the input tape is accessed. Once the value $2^i$ is obtained, written on the [index] tape, it is now easy to do a binary search to determine the value of $n$. Finally the index tape is copied to the output tape.</p>
</blockquote>

<p>(NB: the paper actually says "Once the value $2^i$ is obtained, written on the <em>input</em> tape", etc., but it must be a typo, the computation described is obviously done by writing on the index/query tape. Besides, the input tape is usually read-only in this setting).</p>

CC BY-SA 3.0
2016-02-10T12:34:18.350Z
Thanks. :) I understand what Emil wrote. It feels that the machine's query tape mechanism is already doing this computation. In terms of FO it feels like saying that the language already contains $\mathsf{bit}$ relations and we can define the length of the input using the query $\mathsf{bit}(\max, i)$. I don't have $\mathsf{bit}(\max, i)$ in the language but it shouldn't matter because it is definable from order. I have to look at Immerman's book.
Kaveh
CC BY-SA 3.0
2016-02-12T16:42:18.847Z
[Immerman 98, p. 16](https://books.google.ca/books?id=a53eBwAAQBAJ&pg=PA16) explains how to obtain $\mathsf{bit}$ from $\mathsf{plus}$ and $\mathsf{sum}$. $\mathsf{FO(wo\ bit)}$ (with order but without arithmetic) is equal to star-free $\mathsf{Reg}$ so it cannot define $\mathsf{bit}$.
Kaveh
CC BY-SA 3.0
2016-02-10T10:14:21.593Z
2016-02-10T11:48:47.550Z
2016-02-10T11:48:47.550Z
Damiano Mazza
<p>Consider the following problem:</p>

<p><strong>Input</strong>: A binary string $w$.<br>
<strong>Output</strong>: $|w|$ as a binary number.</p>

<p>Is it possible to compute this 
in $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ 
(or equivalently in $\mathsf{AltTime}(O(1),O(\lg n))$ or $\mathsf{FO}$)?</p>

CC BY-SA 3.0
2016-02-09T17:16:31.487Z
The length of a string is outright computable in DLOGTIME in this setup (i.e., with input accessed through a query tape, not erased after each query).
Emil Jeřábek
CC BY-SA 3.0
2016-02-10T19:24:48.680Z
@RickyDemer: The same. In fact, the finite automata implementing rational uniformity have the binary representation of the length of the input directly on one of their tapes by definition, so they don’t even need to compute it.
Emil Jeřábek
<cc.complexity-theory><circuit-complexity><uniformity>
Is length uniform AC0 computable?
Kaveh
# Is length uniform AC0 computable?

(Asked by: username_0 on 2016-02-09)

Consider the following problem:

**Input**: A binary string $w$.  
**Output**: $|w|$ as a binary number.

Is it possible to compute this
in $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$
(or equivalently in $\mathsf{AltTime}(O(1),O(\lg n))$ or $\mathsf{FO}$)?

**Tags:** cc.complexity-theory, circuit-complexity, uniformity

> **Comments:**
> **username_1**: The length of a string is outright computable in DLOGTIME in this setup (i.e., with input accessed through a query tape, not erased after each query).  
> **username_1**: @RickyDemer: The same. In fact, the finite automata implementing rational uniformity have the binary representation of the length of the input directly on one of their tapes by definition, so they don’t even need to compute it.  

---

## 1 answers

### Answer by username_2 on 2016-02-10. Score: 6 | Accepted answer

Like Emil says, the answer is yes, because the length (in binary) of the input string is actually computable by a deterministic logtime Turing machine, so is *a fortiori* in $\mathsf{FO}$.

You may find this stated as Lemma 13 of Buss's [The Boolean formula value problem is in ALOGTIME](http://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean/paper.pdf). The idea, attributed to Dowd, is to use the query tape to do binary search (under the convention that the machine gets an "out of range" response if the query tape contains a binary number exceeding the length of the input). I cut-and-paste the proof for quick reference (the number $n$ referenced in the proof is the length of the input, i.e., the desired output; the "index tape" is what Emil and I called query tape):

> The [...] Turing machine proceeds as follows. First determine the least value of $i$ such that $n < 2^i$: this is easily done in $O(\log n)$ time since we assume that the index tape and its tape head are unaffected when the input tape is accessed. Once the value $2^i$ is obtained, written on the [index] tape, it is now easy to do a binary search to determine the value of $n$. Finally the index tape is copied to the output tape.

(NB: the paper actually says "Once the value $2^i$ is obtained, written on the *input* tape", etc., but it must be a typo, the computation described is obviously done by writing on the index/query tape. Besides, the input tape is usually read-only in this setting).

> **Comments:**
> **username_0**: Thanks. :) I understand what Emil wrote. It feels that the machine's query tape mechanism is already doing this computation. In terms of FO it feels like saying that the language already contains $\mathsf{bit}$ relations and we can define the length of the input using the query $\mathsf{bit}(\max, i)$. I don't have $\mathsf{bit}(\max, i)$ in the language but it shouldn't matter because it is definable from order. I have to look at Immerman's book.  
> **username_0**: [Immerman 98, p. 16](https://books.google.ca/books?id=a53eBwAAQBAJ&pg=PA16) explains how to obtain $\mathsf{bit}$ from $\mathsf{plus}$ and $\mathsf{sum}$. $\mathsf{FO(wo\ bit)}$ (with order but without arithmetic) is equal to star-free $\mathsf{Reg}$ so it cannot define $\mathsf{bit}$.  

---

