I always thought that combinational logic circuits could only solve problems that didn't require memory, but then something struck me.
Whenever we are modelling a binary adder with a Finite State Machine, we consider it as a problem that requires memory ( we need to know whether the previous digit addition led to a carry or not ) . That's why we need two states, "no carry" and "carry".
But then we can easily see how binary adders with carriers can be solved by combinational logic circuits, which seemingly don't have memory.
It seems to me that the memory is somehow encoded in the way we put the individual adders in serial ( C_out of the last adder goes into the C_in of the current adder )
Comparing the Finite State Machine solution to the problem with the Combinational Logic solution to the problem , it seems like the former decides to do one digit addition at a time, regulated by a clock and that's why the memory needs to be in form of states . And it seems like the latter decides to do all digit additions at the same time, so there is no need for clocks and somehow the memory for the previous carriers is implemented via a serial cascading connection between the adders.
Just like we can have a FSM as well as a Combinational Logic version for the problem of arithmetic addition with carriers, i'm thinking whether we can actually convert ANY finite state machine into a Combinational Logic Circuit that does the same job, provided we arrange one subcircuit for every possible job that is done in the FSM in one clock ( one digit addition in the last case ) , put all those in parallel, and somehow encode the memory in a serial cascading connection.
Is it true ?
This doubt came because i'm trying to link all concepts i have recently learned in Theory of Computation ( Automata, Turing Machines, Computational Complexity : Time Complexity and Space complexity ) with combinational logic circuits .
Thanks a lot in advance.
Best Answer
No, you can not translate a (nontrivial) circuit that has memory to a combinatorial (feedback-less) circuit.
The outputs of a combinatorial circuit are by definition a function of its inputs (and nothing else).
Take the simplest non-combinatorial circuit: the Set-Rest memory cell (two cross-couples NANDS or NORS). When the inputs have the 'remember' value the outputs are a function of the past. This is simply not possible with any combinatorial circuit.