6
$\begingroup$

I have a question, but I don't seem to know enough computer science terminology in order to look up an answer. So I wonder if you guys could help a poor physicist like me.

I would like to know if Boolean circuits are what I would call universal. By this I mean that, given an infinite number of NAND gates and wires, could I solve any problem on any input?

Equivalently (I think) could I simulate any given instance of a universal Turing machine using some particular Boolean circuit? By 'a given instance' I mean that the action table and input tape are set in stone, so we know exactly what process that our Boolean circuit is to simulate before we start wiring all the NAND's together.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ suggest migrate to cs.se $\endgroup$ – vzn Sep 12 '13 at 17:16
  • $\begingroup$ functional completeness, wikipedia $\endgroup$ – vzn Sep 12 '13 at 17:16
  • $\begingroup$ @vzn the question is not aobut that (the OP seems to know that NAND gates are complete), but about equivalence with Turing machines. $\endgroup$ – Denis Sep 12 '13 at 17:50
  • $\begingroup$ still basic/closely related. $\endgroup$ – vzn Sep 12 '13 at 17:57
  • 1
    $\begingroup$ some ref to uniform vs nonuniform circuits (key concept here?) on wikipedia. also suggest not using/reinventing the term "universal" here. the question seems to be asking about the existence of nonuniform circuits but in a mixed up way (because nonuniform circuits can solve the halting problem but that is not equivalent to simulating any TM with circuits) $\endgroup$ – vzn Sep 12 '13 at 18:05
11
$\begingroup$

It is important to remark that a specific boolean circuit only treats inputs of a given size, unlike a Turing Machine that can take inputs of any size.

So a language with inputs of arbitrary size is usually treated by a family of circuits, one for each size of input. The problem with this definition is that it allows circuit to solve uncomputable problems, since we could for instance answer 1 if $|x|\in H$ and $0$ if $|x|\notin H$, where $H\subseteq \mathbb N$ is any set. Take for instance $H$ to be an enconding of the halting problem.

To circumvent this problem, we usually look at uniform families of circuits, where there is a fixed Turing Machine $M$ which on input $n$ outputs the circuit for size $n$ inputs.

There is now a hope that circuits are equivalent to Turing machines.

Unfortunately, the model of circuits have computations that always halt (or you can define circuits with loops that never halt but they are useless). This limitation alone suffices to prove that they cannot be Turing complete, because any Turing-complete model must allow infinite computation.

However notice that you have a uniform family of circuits for any language that is decided by a total Turing machine: on input $n$ you can build your circuit for size $n$ by listing all inputs of size $n$ accepted by your machine. The things that you miss are recursively enumerable languages, such as the Halting problem.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. But couldn't my allowance for an infinite number of gates in the Boolean circuit allow for non-halting problems? $\endgroup$ – Matthew Matic Sep 12 '13 at 12:44
  • 1
    $\begingroup$ The acceptance in this setting must be defined precisely, but it seems that if there is an infinite path in your circuit, then it will never stop no matter what the input is, so it is as useless as looping circuits. $\endgroup$ – Denis Sep 12 '13 at 14:22
4
$\begingroup$

I hope this doesn't come across as picking holes in the question.

The first point, as raised by dkuper, is that ordinary circuits necessarily implement total functions (every input gives either true or false), whereas Turing machines implement partial functions (inputs lead to acceptance, rejection or "no answer", i.e., non-termination). If you want to simulate a Turing machine, you're either going to need to add something to your model of circuits that allows them to compute partial functions, or implement separate circuits for, say, "The machine accepts this input", "The machine rejects this input" and "The machine doesn't halt on this input."

The second point is, what does it mean to have a circuit with infinitely many gates? Any circuit with an infinite number of gates and a single output gate must have an infinite path and/or a gate with infinite in-degree. What does it mean to evaluate an infinite path? Can that be done in finite time? Is it OK to have a gate with infinite in-degree, given that such a thing couldn't possibly be realised? (OK, the infinite tape of a Turing machine can't be physically realised but it suffices to have a finite amount of tape and promise to add more whenever the head reaches the end.)

Now let's look at the more specific questions. The version where the Turing machine $M$ and its input $x$ are fixed, is trivial, as are all problems with a finite number of instances (one, in this case). The circuit is the constant "true" if $M$ accepts $x$, the constant "false" if it rejects and, some circuit with no value if it doesn't halt (or whatever you decided to do to represent non-terminating computations in your circuit model). We know that this circuit exists but, of course, the function that maps $M$ and $x$ to the required circuit is uncomputable.

Finally, the case where the circuit's input is (a coding of) the Turing machine and its input. You have to decide how to code that as the input to an infinite circuit. One way would be to code machine and input as a finite binary string and have the infinite sequence of inputs $x_i$ and $y_i$ ($i>0$) to the circuit such that, the circuit evaluates to false if every $y_i=0$ and, otherwise, putting $\ell=\min\{i\mid y_i=1\}$, the sequence $x_1\dots x_{\ell}$ is the binary string coding the input. Now, take the infinite set $S$ of pairs $(M_j,x_j)$ ($j>0$) such that $M_j$ is a machine that accepts input $x_j$. The required circuit is just an infinite disjunction, where the $j$th disjunct says "My input codes $(M_j,x_j)$"; again, you need to deal with non-terminating computations in some way.

Alternatively, you go the more conventional route of having a family of circuits, one for each input length, as described by dkuper.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You would only need circuits for two of those things. $\;$ $\endgroup$ – user6973 Sep 12 '13 at 18:17
  • 2
    $\begingroup$ One quibble: it seems quite feasible to realise a finite-but-extendable AND, as a series of transistors. This takes longer and longer to settle as one adds inputs, but then a Turing machine also takes longer the more tape we add, waiting for the one-cell-at-a-time mechanics of the machine. $\endgroup$ – András Salamon Sep 12 '13 at 21:01
  • 1
    $\begingroup$ @AndrásSalamon To me, adding more tape feels like supplying consumables, whereas extending an AND gate feels like changing the definition of the circuit. On the other hand, I accept that the concept of consumables appears nowhere in the actual definition of Turing machines, so the distinction is artificial. On the gripping hand, you'd have to define what operations are allowed when extending the AND gate which, itself, feels like computation; with the Turing machine, the "operation" is just "glue more tape on the end." $\endgroup$ – David Richerby Sep 12 '13 at 21:10
1
$\begingroup$

Any Turing machine doing any finite amount of compution can be perfectly emulated with a finite circuit. If you allow the output to become the input in a loop, it becomes Turing machine equivalent.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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