Electronic – name for “chips out of which one can build a CPU”

cpudigital-logic

Some people enjoy building "homebrew" CPUs out of simpler ICs.

Is there a name for "chips out of which one can build a CPU, if you have enough of them"?
Is there a name for the other chips, "chips that one cannot build a CPU out of, no matter how many of them you have"?

One can build a CPU out of sufficiently large quantities of 4:1 mux chips
( multiplexers are the tactical Nuke of Logic Design ).
One can build a CPU out of (somewhat larger) quantities of 2-in NAND gates. Or from 2-in NOR gates. Or from a few (perhaps one) CPLD or FPGA.

However,

One cannot build a CPU out of 2-in XOR gates alone.
One cannot build a CPU entirely out of diode-resistor logic alone.
One cannot build a CPU entirely out of D-type flip-flops alone.

Is there some term or phrase for distinguishing these two categories of chips that is less awkward than "chips out of which one can build a CPU"?

Best Answer

You need to be able to do NOT and one of AND and OR. Using Demorgan's laws, either of these functions can be transformed into the other, and thence into all other logical functions.

This is known as functional completeness or expressive adequacy. The components or functions which create such a system are known as Sheffer functions (after Henry Sheffer, who published a proof on the topic) or sole sufficient operators.

Also of interest is the fact that you can combine a quartet of NAND gates to make a D-type flip flop, and from there a memory cell, which is also required to create Turing completeness.

ProofWiki's article on the topic is good reading.