Logic operations and universality
Knowing that the circuits in practical computers use only a small set of basic logic operations—often just NandNand—it is sometimes assumed that if a particular system could be shown to emulate logic operations like NandNand, then this would immediately establish its universality. But at least on the face of it, this is not correct. For somehow there also has to be a way to store arbitrarily large amounts of data—and to apply suitable combinations of NandNand operations to it. Yet while practical computers have elaborate circuits containing huge numbers of NandNand operations, we now know that for example simple cellular automata that can be implemented with just a few NandNand operations (see page 619) are enough. And from what I have discovered in this book, it may well be that in fact most systems capable of supporting even a single NandNand operation will actually turn out to be universal. But the point is that in any particular case this will not normally be an easy matter to demonstrate. (Compare page 807.)
