The computing revolution may have made the line graph of human progress look like a barely tilted horizon, broken by a near-vertical spurt towards Moore’s Law-defined heights of technological miracle - but it didn’t arrive with a definition attached to it. What is “computation” really, and when theorists from psychology, biology or physics describe a process that they study as “computational”, what insight is there to be gained from this statement?
Computing science juggles multiple personas, all of whom in one way or another make use of mathematics. Some practitioners deal with the bells and whistles, with graphical user interfaces, data storage, and input devices. Others concern themselves with the nittygritty of operating systems and computer hardware. Some devise algorithms to solve mathematics problems using minimal space and time, while still others use mathematics to determine which problems a computer in principle is capable of solving. And this is where, all of a sudden, the no-nonsense business of programming and circuit design suddenly comes face to face with eerie metaphysical conundrums, for if the powers of computers are inherently limited, what does that suggest about physical reality?
We often hear that computers really are just “ones and zeroes”, that they deep down consist of strings like 0110 0010. Of course, these ones and zeroes are not literal, but labels given to the two types of states that the computer circuitry is engineered to reliably distinguish between: the presence or absence of current. In decimal representation - which uses a “base” of ten unique symbol rather than two - 0110 0010 translates to 98, but having to distinguish between ten different states would make the computer more complex and less robust. It is therefore out of convenience that we store information as “bits” – or two-valued system states – and it would be just as valid to say that a computer deep down consists of binary patterns, which depending on context could be used to symbolise just about anything (for example, 0110 0010 may encode “rain”).
Computation happens when one binary pattern is deterministically transformed into a different pattern. More technically, a correlation is established between input and output, such that their bits share “mutual information”. In the Timeless Abstractland of Mathematics, such transformations are known as “functions”, and through their meticulously reliable mechanical interior, computers give these causally inert entities a physical existence with temporal and spatial extent.
Not all mathematical functions can be physically implemented – only a subset can, which is referred to as “computable” - but unreduced mappings of “If this exact input, give this exact output” are easy to implement physically. Using a two-valued formal system called “Boolean algebra”, any desired bit transformation can be specified in terms of algebraic operators like AND, OR and NOT – tiny little look-up tables whose physical realisations are known as “logic gates”. Logic gates can be thought of as myopic decision-makers, deciding whether to forward a 1 or 0 depending on input combination. When connected in sequence or parallel so as to correspond to the nested structure of a Boolean formula, they form a logical circuit, which is just another, more complex mathematical function.
Functions are not always of the form of “If the input string is 0110, then output 1”. Rather than hard-coding every possible input combination, we may wish to describe a class of strings more generally, like “If the string starts with 0 and ends with a 0, then output 1”. Such a set of strings is known as a “language”, and involves presenting a function with the string sequentially, checking whether the first symbol is 0, immediately output 0 if not, or else proceed to check whether the last symbol is 0. Such sequential processing requires memory, and it turns out that languages fall naturally into four different classes, called the “Chomsky hierarchy”, each demanding a computing device with a different type of memory access, in order to recognise (i.e. output 1) a member string of that language.
The invention of computers was motivated not by text processing needs, but by a wish to mechanise mathematical algorithms, like those used in division and multiplication. This meant outsourcing cognitive labour to a machine that didn’t run on mental energies. The development of an efficient way of representing numbers and calculational intermediates on external media like notebooks and blackboards had already come a long way to disburden the brain’s working memory, and a machine capable of understanding instructions like “Find the logarithm of 78” would be the natural culmination of this trend towards greater automation, and indeed Alan Turing would go on to conceive of his computation device (which embodies the top tier of the Chomsky hierarchy) by way of analogy with human mathematicians.
Both uses of computers connote strictly sequential procedures, unlike the massive parallelism we experience in nature, but just as a bit-flipping contraption can be used as a stand-in for a human mathematician, a computer program can be used as a stand-in for a physical process. Suppose we have an equation or algorithm believed to model a phenomenon accurately, if somewhat simplistically. An algorithmic description of a system’s behavior would constitute a “theory”, which like functions are recursive definitions: it is a collection of facts that implies more facts. By running it on some input values, we can watch the structure hidden inside an equation unfold along a time-axis, at a rate much faster than the phenomenon itself, then feed the result into our predictions. Sure enough, the computer won’t represent qualitative changes – a rainy weather simulation won’t make the computer wet – but if the model is accurate, then the symbolic transformations map onto those being symbolised. In this context, computation really is just about expressing vague statements about causation in precise “If-then” statements that a machine can imitate.
Logic gates can be implemented in an infinite number of ways: the only real criterion is that the analogous input combination results in the same output, and that some amplification mechanism ensures that the signal (i.e. the distinction between 0 and 1) is not degraded. In modern computers, this is done through “transistors”, but transistors are in no way metaphysically privileged: it is easy to conceive of how neurons, molecules and elementary particles all can serve as logic gates. Does this justify saying that all change observable in Nature truly is computation?
There are at least three objections to this. One is that “computation” generally refers to mechanisms that deal with discontinuous (digital) variables – clocks that tick, words chunked into bytes, and bits that are either 1 or 0 without any in-betweens. Mankind has experimented with “analogue” computers that symbolise processes, e.g. mathematical algorithms, using continuous variables like voltage, but from an engineering perspective these proved inferior. The notion of “universal computation”, of being able to transform any bit string into any other, is a digital concept - no analogue device has ever reached the degree of universality achieved in digital computers. However, physical phenomena in nature pay no attention to engineering preferences, and physicists often tend to model things like distance and volume as continuous quantities with infinite precision. Whether nature is “computational” in a digital sense is therefore a question of fundamental physics, if indeed it is answerable at all. Intellectual powerhouses like Aristotle, Pythagoras, Newton and Cantor addressed the issue, but made little progress in deciding whether the fabric of reality is granular or not.
Another more esoteric concern is that of whether the physical world is capable of feats that a computer cannot simulate. There are well-defined limits to the capabilities of computers – the “Halting problem” of determining whether an input program will ever end is for example proven to be non-computable. While it is hard to conceive of “hypercomputational” processes out in the wild, they cannot be empirically ruled out.
A final objection is that natural processes are not computational because we should reserve the “computing” term for physical systems that are programmable and generalpurpose. A tea-strainer can trivially process information in that it distinguishes between leaves and water, and a hand can be used for arithmetic, but neither’s matter is configured in a way that allows them to casually solve differential equations, or implement Tetris. In principle they can – even atoms colliding in a gas are capable of universal computation - but in practice they cannot, and systems are “computers” only if they practically are. Laptops and mainframes are, because they are analogous to the Chomsky hierarchy’s top-tier device called “Turing machines”, whose recognition abilities are so general that they can be constructed so as to accept and simulate the specification of any other Turing machine, becoming “Universal Turing machines” capable of running any algorithm. This allows us to meaningfully distinguish between “software” and “hardware”, whereas with natural systems the distinction makes no sense.
Mark Twain once said: “To a man with a hammer, everything looks like a nail.” Theory development often proceeds from metaphors borrowed from technological innovations, but unlike clockworks and steam engines – which also have served as metaphors for the Universe – there genuinely doesn’t seem to exist a physical process that in principle cannot be simulated by a computer, and therefore no revolutionary new technology can conceivably replace computers. This led cognitive scientist Philip Johnson-Laird, in the context of brain research, to call the computer “the final metaphor”. Only benefits seem to come from viewing the natural world through a computational lens, because the faster we cast things in algorithmic terms, the sooner we can begin to build falsifiable, highprecision simulations on actual computers, which is nothing less than the ultimate goal of science.