While an EE undergrad I attended some lectures that presented a nice characterization of boolean circuits in terms of how many nested loops they have. In complexity, boolean circuits are often thought of as dags, but in real hardware cycles are common. Now, modulo some technicalities regarding what a loop is and what constitutes a nested loop, the claim was basically that in order to implement in hardware an automaton one needs two nested loops, and in order to implement a processor one needs three nested loops. (I might be off-by-one with these counts.)
Two things bother me:
- There was nothing like a formal proof.
- I didn't see this anywhere else.
Did anyone investigate precise statements of this kind?
Sort of background: In case you wonder why are cycles useful at all in real hardware, here is a simple example. Connect two inverters in a cycle. (An inverter is a gate that computes the boolean function NOT.) This circuit has two stable equilibriums (and an unstable one). Absent any outside intervention, the circuit will simply stay in one of the two states. However, it is possible to force the circuit into one particular state by applying an external signal. The situation can be seen like this: While the cycle is connected to the outside signal "we read the input," and otherwise we simply "remember the last value we saw." So one loop helps us remember stuff.