8
$\begingroup$

I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything I have learned recently in Theory of Computation.

I was wondering whether combinational logic circuits can implement computations in the same way finite state machines can. They seem radically different :

Finite State Machines, however, have a well-defined memory in the form of the states that it can be in. Combinational logic circuits, however, don't have a well-defined memory so to implement algorithms that need memory they kinda use some weird method of serial connection ( see how $C_{out}$ of previous adder is connected to $C_{in}$ of current adder in the image bellow ) .

However radically different might seem, they both seems to be doing computations. For instance, both can implement an algorithm for binary addition ( and even binary multiplication ) however different those implementations might be :

FSM :
enter image description here

Combinational Logic Circuit ( C, as in $C_{in}$ and $C_{out}$, stands for Carry ) :
enter image description here

I'm even thinking ( although still very uncertain ) that we can convert every FSM into a corresponding Combinational Logic Circuit.

So, i'm asking myself :

Can Combinational Logic Circuits also be considered a instantaneous kind of model of computation ? Can we apply all concepts we learn in Computability Theory and Computational Complexity Theory, like space complexity and computability, to it ?

On one hand, it seems like they don't fit as a model of computation because they don't have elementary operations ( like reading/writing of a tape, function reduction, steps on the proof search of logical programming paradigma ), they implement their computations instantaneously.
But on the other hand, they seem to be fit as a model of computation because we can model all kinds of computation with them ( binary addition is one example ), and they can be viewed abstractly ( by only focusing on the truth-tables and the logical gates and forgetting about the physical circuit that might implement it ).
So, what do you guys think ?

Also, if it can indeed be considered as a (instantaneous kind of ) model of computation, do you guys have any example of other similar ( also a instantaneous kind of ) model of computation ?

Thanks a lot in advance

$\endgroup$
9
$\begingroup$

Logic circuits are common in complexity theory, where they go by the name circuits. There is a big difference between circuits and models of computation such as the Turing machine: each circuit can only handle inputs of fixed size. In order to fix this, under the circuit computation model, for every input length $n$ there is a circuit $C_n$, and together they compute a function on strings of arbitrary length. This computation model, as stated, is too strong: it can compute uncomputable functions, indeed all functions. The problem is that an infinite sequence of circuits doesn't necessarily have a finite description. In order to fix this problem, we usually demand that the circuits be uniform, that is, that they be generated by some Turing machine, which on input $n$ generates $C_n$.

The circuit model is especially popular in complexity theory, even without the uniformity restriction. The reason is the following observation: a Turing machine running in polynomial time can be converted to a (uniform) sequence of circuits of polynomial size, using essentially the ideas of Cook's theorem (which shows that SAT is NP-complete). Hence if you want to prove that a certain problem cannot be solved in polynomial time, it is enough to show that it cannot be solved by polynomial size circuits.

$\endgroup$
  • $\begingroup$ I think I understand the gist of this answer. Correct me if I'm wrong: time complexity of a Turing machine bounds the spatial complexity of an analogous circuit machin. But I don't understand this statement: "[The circuit] computation model, as stated, is too strong: it can compute uncomputable functions, indeed all functions." The model itself is too strong? Or your initial statement of the model is stronger than the model atually is? $\endgroup$ – kdbanman Feb 7 '15 at 16:31
  • $\begingroup$ Unrestricted circuits are too strong a computational model. You have to restrict them somehow - either restrict their size or structure, or demand that they be uniform, or both. $\endgroup$ – Yuval Filmus Feb 7 '15 at 17:36
  • $\begingroup$ Why restrict the model, though? What constraint must they conform to? If they are a theoretical construct, then can't they do whatever we like? $\endgroup$ – kdbanman Feb 7 '15 at 17:51
  • $\begingroup$ They can, but then they're not useful for complexity theory, since they can compute every possible function. $\endgroup$ – Yuval Filmus Feb 7 '15 at 17:52

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.