News for hackers. Stuff that matters.
Re:Universal Logic Gates (2015) by kragen on Monday June 17, 2019 @04:06AM (#20200862)
Although I have a soft spot for abjunction (as discussed in my wall-of-text comment deeper in the thread), my favorite universal gate is the three-input conditional: x if y else z, or y ? x : z in C or JS syntax, the element from which BDDs are built. (Like abjunction, it's falsehood-preserving, and it's also truth-preserving, so unlike NAND and NOR, it is only "universal" if you have access to constants TRUE and FALSE.) As Darius Bacon has pointed out, one way to generalize it to continuous variables, or variables over arbitrary fields, is as the lerp operation commonly provided by GPUs: yx + (1-y)z, or, without using constants, x + y(z-x). In GF(2), subtraction and addition are both XOR, so that ends up being x ^ y & (z ^ x), which is a correct definition of the operation for bits.

The universal reversible gates like the Fredkin gate and the Toffoli gate are also really interesting and potentially important.

Designing circuits with separate combinational gates and registers is fairly easy, but it treats the temporal separation of cause and effect as a sort of defect in the universe, and consequently we have to be cautious about glitches (when we don't clock) and metastable states resulting from inadequate setup and hold times (when we do clock). Suppose we continue to discretize time with clocks just as in the current RTL paradigm; can we find a finite state machine that is minimal and universal in some NAND-like sense, and also admits a reasonably tractable design methodology? Would it have two binary inputs, one binary output, and one bit of state? Is it just a J-K flip-flop?

There are no comments on this comment yet.