The article of mine Jim Propp is looking for is: A Curious New Result in Switching Theory, Math Intelligencer Vol 12 No 1, 1990 pp 21 - 32, about which, I can hardly refrain from adding, I recently received some complimentary remarks from Don Knuth. BTW, the piece goes into great detail on the matter of bootstrapping the puzzle solution so as to make two NOT-gates act like four. In this context, a quote from the article I cannot resist is: "Grateful thanks are due to Jim Propp, formerly of the Dept of Mathematics, University of Maryland, whose searching criticisms brought to light various errors and made for substantial improvements to an earlier draft of this paper." So now we know there are two Jim Propps. Lee Sallows At 12:12 PM 1/1/2006 -0600, you wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun