Infinite Boolean circuits as a model of computation

Question

Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a Turing machine that can output, for some input length N, the correct Boolean circuit for that N.

However, I wonder if it is instead possible, if not a bit abstract, to instead look at finite Boolean circuits that "converge" to some well-defined infinite circuit in the large limit of N, which can handle any input size of arbitrarily large but finite length, and get an equivalent model of computation.

My intuition is that this is often the case, because it is quite common for Boolean circuits to be able to handle not only their own input size, but all smaller input sizes as well. For example, an adder that works on inputs of N bits can handle inputs of length < N by zero-padding the highest undefined bits; this is equivalent to setting the undefined bits to zero by default. So we can easily imagine this series of circuits converging to something like ripple adder extending infinitely to the left, and for which we consider only those inputs with finitely many nonzero bits.

What I am really trying to understand is the simplest way to extend the notion of Boolean circuit to get something that is Turing-complete. For example, we can give a finite state machine an infinite queue and make it Turing complete. By looking at infinite Boolean circuits that can handle arbitrarily large input with finite support, can we likewise obtain Turing-completeness, with an analogue of the halting problem, etc? If not, how could we do it?

Answer 1

Your idea is equivalent in power to non-uniform circuits. Thus, it doesn't formalize the concept you want it to formalize. You were hoping that your notion of an infinite circuit would capture the power of uniform circuits / Turing machines, but it doesn't -- like non-uniform circuits, it is "too powerful" (more powerful than any uniform model). Thus an infinite circuit is essentially still a non-uniform model of computation, even if it doesn't look like it on the surface.

Consider the following infinite circuit $C$: if the $i$th bit of the input is 1 and the $i+1$st bit is 0, then the $i$th output bit is $c_i$, otherwise that output bit is 0. Here $c_i$ is a constant that is 1 if the $i$th Turing machine (in some canonical enumeration of all Turing machines) halts, or 0 otherwise.

This circuit is an infinite circuit, in your sense. You can think of it as a sequence of circuits $C_1,C_2,\dots$, where $C_N$ is the circuit that takes $N$ bits of input and produces $N$ bits of output, obtained by zero-padding its input and feeding that to $C$. Thus that sequence of circuits "converges" to $C$.

However, $C$ has the following peculiar property: given $C$, you can solve the halting problem. In particular, if you feed in $i$ in unary as input to $C$, then the output will indicate whether the $i$th Turing machine halts or not. Thus, infinite circuits can solve undecidable problems. Like non-uniform circuits, infinite circuits are in some sense "too powerful" -- they're not realistic.

So your construction doesn't really eliminate any of the issues with the non-uniform circuit model. It just recreates them, in a slightly different guise.

---

A separate challenge with your infinite circuit idea is that it is not clear how to handle circuits that produce a single bit of output. Normally, in circuit complexity, we study circuits that take $N$ bits of input and produce a single bit of output. It's not clear how such a sequence of circuits can "converge" to a single infinite circuit (what is its single output bit, and how is it computed?).