Unary languages in $AC^0$? 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$, JCSS 41 274–306, 1990.  doi: 10.1016/0022-0000(90)90022-D
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.