3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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?).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, that's helpful. So the idea, if I understand correctly, is that the sequence of circuits need not itself be defined by a partial recursive function, and if arbitrary sequences are allowed you end up running into theoretical limits regarding computational reasonableness. You can change this, I guess, by stating that the sequence must be a partial recursive function or a Turing machine. What I wonder is, is there a way to tweak the definition such that Turing-completeness somehow shakes out of it, rather than building it in? $\endgroup$
    – Mike Battaglia
    Sep 22, 2017 at 0:02
  • $\begingroup$ I guess this is the same issue that one faces when looking at Turing machines which can accept infinite-length input strings: you can then solve the halting problem given Chaitin's constant as input. Limiting to finite length fixes that; not clear how to do so for Boolean circuits though. $\endgroup$
    – Mike Battaglia
    Sep 22, 2017 at 0:04
  • 1
    $\begingroup$ @MikeBattaglia, yup, exactly! Agreed. What you're wondering makes a lot of sense, and I don't have an answer or a way to tweak the definition, but it seems interesting to me too. We're on the same page. $\endgroup$
    – D.W. ♦
    Sep 22, 2017 at 0:33
  • $\begingroup$ Hm. I wonder, if you go with the uniform version and demand all circuits be generated by a partial recursive function, what analogue to the halting problem do you get in this model? Is "infinite satisfiability" equivalent to the halting problem, or something like that? $\endgroup$
    – Mike Battaglia
    Sep 22, 2017 at 4:35

Your Answer

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

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