<p>Note the beginning of the sentence you quoted.  It says</p>

<blockquote>
  <p><strong>In their non-uniform versions</strong> these circuit complexity classes contain problems which are not computable at all in the ordinary sense (e.g., any unary language is in AC<sup>0</sup>).</p>
</blockquote>

<p>The nonuniform version of AC<sup>0</sup> is defined as the class of problems which are decided by a (not necessarily uniform) family of boolean circuits of polynomial size and constant depth with unbounded fan-in.  Since there is no uniformity condition, you can use completely different circuits for different lengths, implying that you can decide any unary languages (including undecidable ones).  This is the motivation of the uniformity condition.  For detail, see Proposition 11.2 of <em>Computational Complexity</em> by Papadimitriou.</p>

CC BY-SA 2.5
2010-09-24T18:24:16.767Z
2010-09-24T18:30:13.133Z
2010-09-24T18:30:13.133Z
Tsuyoshi Ito
<p>Barrington, Immerman, and Straubing state</p>

<blockquote>
  <p>circuit complexity classes contain problems which are not computable at all in the ordinary sense (e.g., any unary language is in $\text{AC}^0$)</p>
</blockquote>

<p>I'd appreciate clarification of this statement; it seems to imply that $\text{AC}^0$ contains even undecidable languages.</p>

<p></p>

<p>Could someone please point out my error, or explain what the authors might mean?</p>

<ul>
<li>Barrington, D.A.M., Immerman, N., and Straubing, H., <a href="http://www.cs.umass.edu/~immerman/pub/bis.pdf" rel="nofollow"><em>On Uniformity within $NC^1$</em></a>, JCSS <strong>41</strong> 274–306, 1990.  doi: <a href="http://dx.doi.org/10.1016/0022-0000%2890%2990022-D" rel="nofollow">10.1016/0022-0000(90)90022-D</a></li>
</ul>

<cc.complexity-theory><complexity-classes>
Unary languages in $AC^0$?
András Salamon
# Unary languages in $AC^0$?

(Asked by: username_0 on 2010-09-24)

Barrington, Immerman, and Straubing state

> circuit complexity classes contain problems which are not computable at all in the ordinary sense (e.g., any unary language is in $\text{AC}^0$)

I'd appreciate clarification of this statement; it seems to imply that $\text{AC}^0$ contains even undecidable languages.

Could someone please point out my error, or explain what the authors might mean?

* Barrington, D.A.M., Immerman, N., and Straubing, H., [*On Uniformity within $NC^1$*](http://www.cs.umass.edu/~immerman/pub/bis.pdf), JCSS **41** 274–306, 1990. doi: [10.1016/0022-0000(90)90022-D](http://dx.doi.org/10.1016/0022-0000%2890%2990022-D)

**Tags:** cc.complexity-theory, complexity-classes


---

## 1 answers

### Answer by username_1 on 2010-09-24. Score: 6 | Accepted answer

Note the beginning of the sentence you quoted. It says

> **In their non-uniform versions** these circuit complexity classes contain problems which are not computable at all in the ordinary sense (e.g., any unary language is in AC0).

The nonuniform version of AC0 is defined as the class of problems which are decided by a (not necessarily uniform) family of boolean circuits of polynomial size and constant depth with unbounded fan-in. Since there is no uniformity condition, you can use completely different circuits for different lengths, implying that you can decide any unary languages (including undecidable ones). This is the motivation of the uniformity condition. For detail, see Proposition 11.2 of *Computational Complexity* by Papadimitriou.


---

