When I was laid off, I remember wondering
whether the
WARN Act applied to high-tech companies' layoffs and concluding
that it probably didn't, because nobody was mentioning it. Perhaps
they just hadn't heard about it. I know lots of people at companies
which apparently had "mass layoffs" under the meaning of that Act,
and nobody who received an advance notification. Usually these
technology startups (perhaps unlike factories) didn't know
what their financial position would be in 60 days. The decision to
make the layoffs was definitely often formed on shorter time scales
than that.
(From a Crackmonkey post.)
So, which gates (single-valued Boolean logic relations) with n inputs
are universal?
There are 2^2^n such gates, and I know some specific cases of
universal and non-universal gates, but not an efficient way to
determine whether an arbitrary gate is universal.
For n=1, the gate {0: 0, 1: 1} is not universal, and {0: 1, 1: 0} is
universal.
For n=2, the gates are
{00: 0, 01: 0, 10: 0, 11: 0} # ZERO
{00: 0, 01: 0, 10: 0, 11: 1} # AND
{00: 0, 01: 0, 10: 1, 11: 0} # NOTIMP (NOT (A IMP B))
{00: 0, 01: 0, 10: 1, 11: 1} # A
{00: 0, 01: 1, 10: 0, 11: 0} # NOTRIMP
{00: 0, 01: 1, 10: 0, 11: 1} # B
{00: 0, 01: 1, 10: 1, 11: 0} # XOR
{00: 0, 01: 1, 10: 1, 11: 1} # OR
{00: 1, 01: 0, 10: 0, 11: 0} # NOR
{00: 1, 01: 0, 10: 0, 11: 1} # XNOR
{00: 1, 01: 0, 10: 1, 11: 0} # NOTB
{00: 1, 01: 0, 10: 1, 11: 1} # RIMP (B IMP A)
{00: 1, 01: 1, 10: 0, 11: 0} # NOTA
{00: 1, 01: 1, 10: 0, 11: 1} # IMP
{00: 1, 01: 1, 10: 1, 11: 0} # NAND
{00: 1, 01: 1, 10: 1, 11: 1} # ONE
and I know that 5 are universal (AND, OR, XOR, XNOR, IMP) and
6 are not (ZERO, ONE, A, B, NOTA, NOTB, AND, OR) and I don't know
about the other 3. (By symmetry, RIMP must be.)
What does it mean for a gate to be universal? It means that, by
applying it to itself in various ways, you can produce any other
gate. For example, to produce NOT from NAND, you can do X NAND X=NOT X.
And then you can get AND: NOT (X NAND Y)=X AND Y. And OR:
NOT((NOT X) AND (NOT Y))=X OR Y. (Thanks, DeMorgan.) And now XOR:
(X AND NOT Y) OR (Y AND NOT X). And XNOR: NOT (X XOR Y). And IMP:
NOT (X AND NOT Y). Anyway, that's just one example -- the universality
of NAND. But how to we know if an arbitrary gate is universal? How
many gates with n inputs are universal?
