# How do we enumerate every algorithm in the circuit model?

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?

• 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.
– D.W.
Jan 25, 2022 at 18:42
• @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? Jan 26, 2022 at 0:33

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$$.
• 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? Jan 27, 2022 at 3:37