I've always been curious about the feedback/loops restriction. Does anyone know how much things can be improved for boolean _functions_ that are implemented with feedback and/or loops? I suspect that latency can't be improved, but I suspect that the # of gates can be improved over the no feedback/loop version.
(To be clear, I'm thinking about implementing functions using circuits that might have state, but the initial state is irrelevant to the output. For example, a boolean circuit might utilize some sort of hash table lookup to implement an initial guess that is verified before being output. In this case, the (mean) latency could be improved over the no-state version.)
This reminds me of old puzzle I learned about from Lee Sallows, solved with Bruce Smith, and can no longer remember how to solve: How can you use two NOT-gates, as many AND-gates as you like, and as many OR-gates as you like, in order to create a circuit with three inputs and three outputs that acts like three NOT-gates in parallel? (And why can't this trick be bootstrapped to make two NOT-gates act like four?) If anyone can point me to the write-up of this that appeared in the Mathematical Intelligencer a couple of decades ago, I'd be grateful! (A Google-search failed to reveal it.) Jim Propp