How do we enumerate every algorithm in the circuit model?

Question

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?

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.