It is known that $\{ SUM, MULT \}$ is Turing-complete, i.e. every Turing machine has an equivalent circuit made up of $SUM$ and $MULT$ gates.

By the way, I could not come up with designing $MOD$ function with $SUM$- and $MULT$-only circuit. How can one construct such a circuit?

P.S. The Turing machine is simple. Assuming $\#x\#y\#$ as the input, it suffices to go back and forth and cross $y$ of the remaining entries of $x$ as much as possible.


Turing machines and circuits are very different models of computation: Turing machines are a uniform model and circuits are a non-uniform model. Turing machines accept inputs of an arbitrary length, whereas circuits accept inputs of a fixed length. We can convert Turing machines to equivalent circuits in which the properties of the machine we started with are reflected. For example, a Turing machine running in polynomial time can be converted to a sequence of circuits of polynomial size.

If we have a sequence of circuits, one for each possible length of input, we can interpret the sequence as computing a function. As mentioned above, one way of generating such a sequence of circuits is from a Turing machine. Circuits which can be generated by a Turing machine, which accepts $n$ as input and outputs the circuit handling inputs of length $n$, are known as uniform circuits. (There are various more refined notions of uniformity, in which the Turing machine has some resource restrictions.) However, not all sequences of circuits arise in this way. For example, if $L$ is any length in which membership depends only on the length of the input, then $L$ can be computed by a sequence of circuits. However, $L$ need not even be computable. For example, consider the language of all inputs of length $n$ such that the $n$th Turing machine halts on the empty input.

You say that $\{SUM,MULT\}$ is Turing-complete, but there are a few problems with this statement. First, you seem to think of SUM and MULT as gates, which are components of circuits. As explained above, a model for circuits can't really be Turing-complete, though a set of gates can be complete in the sense that using it you can compute any function. Second, we usually (but not always) think of circuits as Boolean-valued. You haven't explained what the domain of SUM and MULT is, but I suspect that it is not $\{0,1\}$. In that case you have to explain exactly what circuit model you are interested in, and what notion of completeness you are interested in: while Boolean circuits can compute all functions $\{0,1\}^n \to \{0,1\}$, the same doesn't necessarily hold in other circuit models such as algebraic circuits.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the answer. So, where can I read more on the topic of Turing-completeness of the circuit models, both algebraic and Boolean? $\endgroup$ – Ali Shakiba Jan 8 '18 at 19:17
  • 1
    $\begingroup$ Turing-completeness doesn't really apply to circuits. $\endgroup$ – Yuval Filmus Jan 8 '18 at 21:24

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.