Weaker, but similar conditions to Turing completeness?

Question

A model of computation is called Turing complete if it can simulate any Turing machine.

This rules out for example a combinational logic circuit.

However, there is a sense in which combinational logic circuits can solve all problems that Turing machines can: while it is not the case that we can find for Turing machine $T$ a circuit that computes the same function $\{0,1\}^*\to\{0,1\}$ as $T$, it is nevertheless the case that we can find for each $n$, a circuit that computes the same function $\{0,1\}^n\to\{0,1\}$ as T does for inputs of size $n$.

Is there a term for whether a model of computation can compute the same functions as arbitrary Turing machines in this less restrictive sense?

Answer 1

The automaton as represented by a combinational logic circuit (CLC) is called combinational logic. Its model of computation is given an input, a CLC is used to compute the output. The name of that model of computation can also be called combinational logic. (This is similar to Turing machine, which is a kind of computing machine and also the name of the model of computation associate to it.)

The question has been answered. However, you might suspect there is no actual information in the answer so far. You may ask further, what is exactly that model of computation? How to understand it?

Firstly let us be clear, a combinational logic is the digital logic where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the history of the input and which can be used to build finite automatons.

Define a Turing machine (TM) as bounded-computing if there is a natural number $n$ such that it always halts before $n$ transitions. Define bounded computation as the following model of computation: given an input, a bounded-computing TM is used to compute the output.

A finite language is a language in which the number of words is finite. What are the languages that are accepted by the bounded-computing TMs? The answer is finite languages.

What is the computation done by a CLC? For any given $n$ and $m$, and a function $f:\{0,1\}^n\to\{0,1\}^m$, there is a combinational logic circuit (CLC) that outputs $f(s)$ given $s\in\{0,1\}^n$ as input. That is all a CLC can do. Note that the input are limited to strings of same length, which is, however, not a limitation of its computing capability since a CLC can pad shorter inputs to longer inputs of the same longer length. Another apparent limitation is that the input can only be words made up from two symbols, 0 and 1. That is not an actual limitation, either, since we can encode any finitely many symbols by two symbols. For example, the $i^{\text{th}}$ symbol can be encoded as $011\cdots1$ where the number of $1$s is $i$.

As it might have become intuitively clear by now, the computation by a CLC and computation by a bounded-computing TM are weakly computational equivalent. (Weak computational equivalence of two models of computation means the set of functions computed by one of them is "the same" as the set of functions computed by the other. Strong computational equivalence means there exists a simulation between the two How to show two models of computation are equivalent?). The detail of a demonstration of the weak computational equivalence is not shown here. However, the ideas are pretty simple. Now we know that combinational logic is computational equivalent to bounding computing. Hopefully, that provides a bit of insight into what is combinational logic as a model of computation.

There is a model of computation called combinatory logic, which is weakly computational equivalent to Turing machine but is not relevant here.

Answer 2

Unrestricted Boolean circuits are not very interesting, since they can compute any function. The class of Boolean functions they compute is the class of all Boolean functions.

In order to make Boolean circuits more interesting, we need to put restrictions on them. The following seem to be the most common restrictions:

• Upper bounds on the size.

• Upper bounds on the depth, sometimes in conjunction with upper bounds on the arity.

• Uniformity requirements.

What seems most pertinent in your case are uniformity requirements. These posit that the circuits from different $n$ "come from the same mold". More formally, a uniform family of circuits is a family of circuits $C_n$, one for each input length, such that there is a Turing machine which on input $n$ outputs $C_n$. It is an easy exercise that a function can be computed by a uniform family of circuits if and only if it is computable.

To make the definition more interesting, we sometimes ask that the Turing machine generating the circuits be efficient. In more extreme cases, we ask for an extremely efficient Turing machine that generates the individual bits in a description of the circuit.