Consider the family of circuits $\{C_n\}_{n\in \mathbb{N}}$ that are big enough to compute every Boolean function for $n$ variables. We can label the nodes in order starting at the inputs and working down the layers, so that $2^{2^n}$ refers to the last, deepest node in the circuit.

A decidable problem corresponds to a path through the output nodes of these $C_n$, where each output node gives the answer to the problem for an input of length $n$. I believe this is the case because we say that a family of circuits can decide a problem if there is some Turing machine that generates the correct circuit for a given length. So a Turing machine should be able to generate $C_n$ up to the node that we select as output since we have an algorithm to pick what that output is. There should be countably infinite paths that refer to decidable problems (we can choose the path in finite time), so my question is, how do we enumerate them?

First I tried something simple. To select the node for the $n$th circuit, we could try $$f_n(k) = k\bmod M$$

The naive choice is $M = 2^{2^n}$, but this would not cover every path; each circuit would loop in sync, and so nodes from lower $n$ would only match with specific nodes from higher $n$. So we choose $M$ as the first prime larger than $2^{2^n}$. Just fill in the extra with repeats of some of the output functions.

But looking closer, this only selects circuits with polynomial size. For any $k$, you can always make $n$ large enough such that $n^c > f_n(k)$. The exponential circuits are "infinitely far away."

So I tried to be a little more clever. It's possible to enumerate every binary fraction in $(0,1)$ as the ratio of the sequences A006257/A062383 (see comment there) in an even way, dividing the interval into finer and finer divisions. The sequence goes like $\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},...$ OEIS gives functions for each sequence so let's put them together,

$$ \begin{align} g_n(k) &= (2^{2^n})\frac{2(m-2^{\lfloor\log m\rfloor})+1}{2^{\lceil\log(m+1)\rceil}}\\ \text{where}\quad m &= k\bmod M \end{align} $$

Except now, $g_n(k)$ only gives exponential-sized circuits! To see this, there's a result from Shannon that shows the fraction of Boolean functions computable with circuits of size less than $2^n/n$ is vanishingly small as $n$ increases. So for any $k$, there will always be an $n$ large enough that the $2^n/n$ bound is lower than the fraction computed within $g_n(k)$. So now the polynomial-sized circuits are infinitely far away.

In order to cover both sets, I suppose I could weave these two functions together by giving one to the even numbers and one to the odd numbers, but I don't even know if that yet guarantees we cover all the paths. Is there a nicer way to do this enumeration?

  • $\begingroup$ I don't understand what connection you are drawing between an algorithm and a path through $C_n$. Can you edit your question to elaborate on that? It is straightforward to enumerate all decidable problems: you enumerate all deciders, and every decider has a finite description (since it is a Turing machine and Turing machines have a finite description), so there is no need to go via circuits. $\endgroup$
    – D.W.
    Commented Jan 25, 2022 at 18:42
  • $\begingroup$ @D.W. I re-worded that paragraph. Is it more correct? I wanted to enumerate circuits specifically to see if I could get any new insight on the size of a circuit vs. maybe some pattern that shows up. I don't think it's straightforward to go from Turing machine description to circuit size, right? $\endgroup$ Commented Jan 26, 2022 at 0:33

1 Answer 1


One way to describe a circuit is as follows. Suppose that the inputs are $x_1,\ldots,x_n$. The remaining gates of the input compute functions $x_{n+1},\ldots,x_m$, where each $x_i$ is one of the following:

  • $x_i = \lnot x_j$ for some $j < i$.
  • $x_i = x_j \lor x_k$ for some $j,k < i$.
  • $x_i = x_j \land x_k$ for some $j,k < i$.

This is known as a straight-line program, and you can express it textually in many ways. Now you can go over all straight-line programs of the appropriate size.

  • $\begingroup$ While I see how this works for an individual $n$, how do I stitch it together to cover all lengths simultaneously (i.e. I'm needing to enumerate all programs for a given $n$, and then all combinations of those programs over all lengths)? I'm running into the same problem as with $f_n$ above, that given only one parameter $k$ with which to index these programs for every $C_n$, there will be some $n$ large enough that the program description is small, if I try to index these programs with $k\bmod M$ again. Am I misunderstanding your answer? $\endgroup$ Commented Jan 27, 2022 at 3:37
  • $\begingroup$ You can’t describe an arbitrary infinite family of circuits using a single integer, since there are too many such families. $\endgroup$ Commented Jan 27, 2022 at 6:46
  • $\begingroup$ But the set of uniform families is not too big, right? I thought that's what my method above was enumerating. Maybe I should ask my question like this. In the set of uniform circuit families, there are some that are polynomial size and some that aren't. Can we enumerate these subsets together nicely (avoiding the issue I ran into in the OP)? $\endgroup$ Commented Jan 27, 2022 at 8:31
  • $\begingroup$ If your circuit family is uniform, then it is described by some Turing machine. You can enumerate over Turing machines. $\endgroup$ Commented Jan 27, 2022 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.