= Solution
For each fixed input length, take the complete truth table of the language. For every accepted string $z\in\{0,1\}^n$, form the minterm
$$
M_z(x)=\bigwedge_{i=1}^n\begin{cases}x_i,&z_i=1,\\\neg x_i,&z_i=0.\end{cases}
$$
An OR of these minterms equals the <indicator function>, since $M_z(x)=1$ precisely at $x=z$. This is the <truth-table upper bound for circuit size>.
Generate the $n$ negated input wires once and share them. With $m\leq2^n$ accepted strings, use at most $m(n-1)$ binary AND gates and $m-1$ binary OR gates, besides the <negations>. Empty truth tables use a constant-zero <Boolean circuit>; length zero is handled by a constant <Boolean circuit>. Thus
$$
\boxed{L\in\mathrm{SIZE}(O(n2^n))\quad\text{for every }L\subseteq\{0,1\}^*}.
$$
This is an existence bound for a nonuniform <circuit family>, even when the language is <undecidable>. It supplies no algorithm for computing the truth tables of an arbitrary language.
Back to article page
