Next: Gödel and unfathomable complexity Up: Structure and essence Previous: Essence as a Platonic   Contents

# Structure in computing and mathematics

That science and mathematics deal only with structure is a conceptual leap. I will explain some of what led me to this conclusion as an undergraduate. Computers were a comparative novelty in the late 60's and I was able to work with one of these extraordinary machines. I could program it to do complex tasks using simple instructions. The low level or ``assembly language'' for computers contains instructions like move the value stored in one place to a different place or add the values stored at two locations together and put the result in a third place.

The computer itself was constructed from simple operations. You could build all the logic that controlled the computer from three circuits. Two of these circuits had two inputs and one output. The other circuit has a single input and output. The inputs and outputs are voltage levels where one voltage (actually a range of voltages) represents the number one and a different voltage represents the number zero. The first circuit is a logical AND. Its output is one if and only if both of its inputs are one. Otherwise its output is zero. The next is an OR circuit. It outputs a one only if either or both of its inputs are one. The third NOT circuit has an output that is the opposite of the input. The input/output function of these three circuits is shown in Table 3.1 on page  with `true' and `false' substituting for 1 and 0. Every logic circuit in any computer no matter how complex can be built out of these three simple circuits.

I was struck by how much complexity could be constructed from such simple building blocks. My interest and wonder was further aroused by the idea of a Universal Turing Machine. This is a very simple computer that could simulate any program that any computer or other mechanistic process could ever possibly do. This is a theoretical result that ignores the time the program runs for. It cannot be proven since computer and mechanistic process do not have a precise definition, In the 1930's there were a number of proposals to define mechanistic calculation. The idea was to characterize those functions that could be calculated by following exact rules. All of the major contenders turned out to be equivalent. They all could generate the same set of functions. One of these was a Universal Turing Machine. One can program this very simple machine to do any program that ever has been or ever will be written. Church's Thesis implies that the functions computable by a Universal Turing Machine fully characterize what we mean by effectively or mechanistically computable. This conjecture is almost universally accepted.

I started to realize how everything at least in the world of computers was structure. The AND, OR and NOT circuits were so simple that they had no real content to them. The important thing was how they were put together to form more complex circuits. The programs that controlled these machines were a long sequence of ones and zeros. One did not write programs that way but it was clear how the symbolic names one typed were translated into a sequence of ones and zeros. The computer did this translation just as computers do today.

The sense that everything is structure was expanded when I studied set theory. All of mathematics was constructed with the single primitive entity of the empty set. One can represent the structures of set theory by the ones and zeros in a computer. In this sense mathematics and computer science seemed to deal with the same structures. The difference between what one constructs in mathematics and what one can program a computer to do depends on the infinite. In mathematics one can write an expression that asserts something is true for all integers. With a computer one can only test a finite subset of integers in a finite time. The role of the infinite in set theory does not prevent everything from being structural. Everything in computing is structure devoid of essence and the same is true in mathematics.