Logic operations and universality

Knowing that the circuits in practical computers use only a small set of basic logic operations—often just Nand—it is sometimes assumed that if a particular system could be shown to emulate logic operations like Nand, 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 Nand operations to it. Yet while practical computers have elaborate circuits containing huge numbers of Nand operations, we now know that for example simple cellular automata that can be implemented with just a few Nand 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 Nand 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.)