9
\$\begingroup\$

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"?

\$\endgroup\$
4
  • 6
    \$\begingroup\$ A problem I have with this question (which means maybe you can improve it, or I'm missing something) is that you are being vague on the how you evaluate being able to "build a CPU" out of. Is this a design (logic) question, or a IC family question? Are you asking to determine the logic requirements to design Turing complete computer? \$\endgroup\$
    – mctylr
    Commented Mar 27, 2011 at 22:09
  • 1
    \$\begingroup\$ @mctylr: Yes -- What do you call the kind of chips, such as the 4:1 mux, that enable one to design a Turing-complete computer entirely from that chip? I suspect that every IC family has an IC from which (in sufficient numbers) one can build a Turing-complete computer; and has some other IC that, alone, is inadequate to build a Turing-complete computer. What terminology can I use to distinguish the first kind of chip from the second kind of chip? \$\endgroup\$
    – davidcary
    Commented Mar 27, 2011 at 23:27
  • 1
    \$\begingroup\$ related: Is there a name for “physical things out of which one can build a Turing machine”? \$\endgroup\$
    – davidcary
    Commented Mar 27, 2011 at 23:27
  • \$\begingroup\$ @reemrevnivek: I thought "diode" had something to do with "diode-resistor logic". \$\endgroup\$
    – davidcary
    Commented Mar 28, 2011 at 22:25

3 Answers 3

Reset to default
16
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ One person on the Wikipedia functional completeness discussion page claims that Fredkin gates are not functionally complete (since if you apply all 0 inputs to one or more Fredkin gates wired in any conceivable arrangement, you can't ever get a 1 at any output), and yet others claim you can build a CPU entirely out of Fredkin gates. So is a Fredkin gate actually "functionally complete", or am I looking for some broader category that includes "functionally complete" and also Fredkin gates? \$\endgroup\$
    – davidcary
    Commented Mar 28, 2011 at 21:17
  • \$\begingroup\$ @David - This is a little off topic, but if you read the article on Fredkin gates, you'll find that the Fredkin gate has the property of swapping the last two bits if the first bit is 1, and it's also reversible. If you allow 1 and 0 to be hard-coded, it's easy to get any other logic function with a few Fredkin gates. However, if you allow hard-coding, it's no longer reversible, and thus not a proper Fredkin gate (according to some). Reversibility is a category independent from functional completeness, and I think functional completeness is sufficient for your problem. \$\endgroup\$
    – Kevin Vermeer
    Commented Mar 28, 2011 at 21:33
  • \$\begingroup\$ If you apply all 0 inputs to one or more 4:1 muxes wired in any conceivable arrangement, you can't ever get a 1 at any output. So is a mux chip actually "functionally complete", even though it is never mentioned on that otherwise excellent ProofWiki page, or am I looking for some broader category that includes "functionally complete" and also 4:1 mux chips? \$\endgroup\$
    – davidcary
    Commented Mar 28, 2011 at 22:15
  • \$\begingroup\$ @David - The 4:1 mux is a specialized device found in electronics. In the field of electronics, we're rarely, if ever, interested of assembling a computer entirely from one type of IC, and in the field of theoretical computer science (the domain of ProofWiki and the term "functional completeness"), muxes and other specialized ICs are assembled from standard logic gates. In this no-man's land, I think you get to define your own terms. \$\endgroup\$
    – Kevin Vermeer
    Commented Mar 29, 2011 at 12:46
  • \$\begingroup\$ @reemrevnivek: When manufacturing a product, it often saves time, money, and storage space to use a few kinds of generic components that I can buy in bulk from several manufacturers, rather than separately "optimizing" each part and using super-specialized components that are only useful in one place in one product and whose manufacturer will likely declare it "no longer recommended for new designs" in a couple of years. p.s.: ever heard of the Cray-1 or the Apollo Guidance Module? Everything except the memory entirely from one type of IC. \$\endgroup\$
    – davidcary
    Commented Mar 29, 2011 at 17:33
5
\$\begingroup\$

The set of "chips you can build a computer out of" can be assembled into Turing complete machines. The rest are cannot.

All logic gates can be assembled from sets of either only NAND or only NOR gates. If your IC in question can act as either or of these, it can be made into a Turing machine.

I don't know of a specific term to describe such a set.

These questions may also help:

https://stackoverflow.com/questions/4908893/what-logic-gates-are-required-for-turing-completeness

https://stackoverflow.com/questions/7284/what-is-turing-complete

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Excellent. So the one kind of chip is "a chip that can act either like a NAND gate, or act like a NOR gate, or both", and the other kind of chip is "a chip that can't act like a NAND gate, neither can it act like a NOR gate". Conceptually much simpler. That's probably adequate, but I was hoping for a phrase that rolled off my tongue a little bit easier. \$\endgroup\$
    – davidcary
    Commented Mar 28, 2011 at 0:03
2
\$\begingroup\$

I agree with the view that 4:1 multiplexers are wonderful. A couple years ago, I implemented an 8K bank-switched memory controller for an Atari 2600 using a single 74xx153/74xx253 and an RC de-glitching circuit. The controller has to both provide an output which is the inverse of the A12 input, and it has to latch A6 when A11 is high and A12 low. "Back in the day" (early 1980's), bank-switching cartridges would either use custom silicon or three TTL chips; using an off-the-shelf 74xx153, however (which was available back then) the job can be done in one chip.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.