[math-fun] simulating three inverters with two inverters
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
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
On 1 Jan 2006 at 19:53, Lee Sallows wrote:
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.
Is this available online anywhere? /bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
Alas, no. I believe attachments are not allowed on math-fun, but I'll be happy to send a PDF version to anyone interested. Lee At 11:24 PM 1/5/2006 -0500, you wrote:
On 1 Jan 2006 at 19:53, Lee Sallows wrote:
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.
Is this available online anywhere? /bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I haven't seen the article, but the idea is quite old -- from the 50s or 60s, at least. Jack Dennis played with it in the 60s, I know. An interesting question was whether all of the electrical gain and signal restoration could be concentrated in two inverters, using essentially passive diode logic everywhere else. This is the construction: Think in terms of the number of input variables that are on, rather than which ones. Let the inputs be A, B, C. Define 0, 1, 2, 3 as the logic variables counting how many inputs are true. Now: /A = 0 + 1 (C + B) + 2 BC /B = 0 + 1 (A + C) + 2 AC /C = 0 + 1 (A + B) + 2 AB Now, we just need to make the signals 0, 1, 2. AB + BC + CA = 2 + 3 invert this to give 0 + 1 A + B + C = 1 + 2 + 3, so (0 + 1) (A + B + C) = 1 ABC = 3, so 1 + ABC = (1 + 3) Invert this to give (0 + 2) (0 + 1) ( 0 + 2) = 0 (0 + 2) (2 + 3) = 2 Done. On Jan 5, 2006, at 11:24 PM, Bernie Cosell wrote:
On 1 Jan 2006 at 19:53, Lee Sallows wrote:
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.
Is this available online anywhere? /bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Bernie Cosell -
James Propp -
Lee Sallows -
Tom Knight