Understanding the universality of computation

The Turing principle is so fundamental to our understanding of reality that David Deutsch considers it to be one of the four main constituents of his “theory of everything” (the other three being quantum theory, neo-Darwinian theory of evolution, and Popper’s theory of epistemology).

The Church-Turing Conjecture

In 1936, mathematicians Alan Turing, Alonzo Church, and Emil Post — trying to understand the precise nature of “computing” (or “calculating” or “proving”) — independently conjectured that what can or cannot be computed does not depend on things like the design of the computer, but is universal. This is now known as the Church-Turing conjecture (or hypothesis or thesis) and can be stated as follows:

Everything that is computable can be computed by a Turing machine. ¹ Here, I have stated the Church-Turing thesis in its most common form. We now know that it can at best be true for classical computation. Quantum computers can compute things a Turing machine cannot. I will come to that shortly.

The Turing machine is not a very complex object. The example that Alan Turing gave was that of a long strip of paper with a mechanism to read, write, and erase symbols on it, and move to other parts of the strip depending on the symbols. But this is just one implementation of the Turing machine, which is an abstract concept. It’s irrelevant what material the computer is made of — it just needs to satisfy the read-write-erase-move criteria (i.e., be Turing-complete). This makes the Turing machine a universal computer (an abstract one), a computer that can do what any other computer can do.

The epoch-making genius of Alan Turing, and why he deserves special mention among the other mathematicians who came at this, was that his model was the closest to being physical (as opposed to abstract mathematical) and he fully understood and articulated this universality of computation: the fact that there is nothing special about the hardware of a computer — the nature of computation does not depend on which physical object is performing it. He conjectured that one device as simple as the Turing machine can perform any possible computation — it just needs to be provided with the right algorithm (software) to do so. If something is computable, a Turing machine can compute it; if something is uncomputable, no other possible object can compute it.

Remember that this was before the “age of computing” ² What is really meant by this is the age of digital, programmable computing. Because computers have existed since much before that, as I discuss below. . Turing later went on to propose, quite correctly, that a universal computer such as a Turing machine could even be made to “think”, i.e., become intelligent, if it is provided with the right “programming”. This is why Alan Turing is considered one of the “founding fathers” of the fields of computer science as well as artificial intelligence. (Interestingly, Ada Lovelace, almost a hundred years before Turing, came close to understanding this universality, suggesting that computers could be made to do much more than number-crunching, such as music generation, but she erroneously ruled out the possibility of their originating autonomous thought. ³ This is no surprise and is rather understandable for the time, because remember that this was even before Darwin published his theory of evolution. It was not yet conceived how ordinary matter could become capable of thinking and feeling. ).

It might seem like an abrupt jump to go from “being able to compute everything that is computable” to “being able to simulate a mind”. I will explain the connection shortly.

But first, I hasten to add that it is now known that the above-stated Church-Turing hypothesis could at best only be true of classical computation, because quantum computers are capable of performing computations that no classical computer can (a Turing machine is a classical computer). One example of such a computation is the generation of true random numbers. But that is not a fatal blow to the hypothesis. As I mentioned, the Turing machine is just one example that Turing used to prove that it is possible for one machine to perform any possible computation. To make the Turing machine truly universal, we just need to modify its design to make it a quantum computer. So, restating the Church-Turing hypothesis to take that fact into account:

There exists an abstract universal computer that can compute everything that is computable.

Stating the hypothesis this way also takes the focus off a single design of a computer — the Turing machine. I think many people learning about this focus too much on the Turing machine itself and miss the truly astonishing part: the nature of reality is such that one computer, no matter where it is in the universe and no matter what it is made of, can compute what anything else in the universe can compute.

Computation connects mathematics to physics

Turing did not explicitly state it ⁴ At least not to my knowledge. , but it is implicit in his work that “everything that is computable” ⁵ In Turing's words, what 'would naturally be regarded as computable'. refers to everything that is computable in physical reality, because the laws of physics determine what is and is not computable.

To compute means to perform a calculation. It refers to the physical application of some mathematical theory (rules and formulae). Given a (physical) input, a computer processes it (using some physical medium) and provides a certain (physical) output. Humans have been building computing devices since prehistoric times. Using tally marks or even your fingers to do counting is like using a crude computer. The abacus was a more sophisticated early computer. The ancient Greeks built devices to predict eclipses, e.g., the Antikythera mechanism. The modern word “computer” has come to mean a programmable computer, meaning we can relatively easily change the algorithm/software it uses to convert an input into an output without changing anything about the hardware. But these are just a special case of a “computer” in the deeper sense.

So computing is how mathematics (which is abstract) interacts with physical reality. Even if a mathematician is working on “pure mathematics” without using a conventional computer, she is still using some physical system, mainly her brain along with maybe pen and paper, to perform computations. Mathematically proving a theorem is exactly equivalent to performing some computation (usually using the computer known as the human brain).

When we re-examine the Church-Turing conjecture while keeping this physical definition of computation in mind, it has been suggested that it be called the “Turing principle”, not a hypothesis or a conjecture, to make it clear that it is a physical principle, comparable to, for example, the laws of thermodynamics or the gravitational equivalence principle. So the Turing principle can be stated as follows:

There exists an abstract universal computer that can perform any computation that any physical object can perform.

We are still talking about an abstract universal computer. However, note that the only thing that makes the Turing machine abstract instead of real is that it requires unlimited hardware resources: unlimited memory (i.e., an infinitely long paper tape), unlimited running time (no limit to how much time it can take to perform computations), and an unlimited energy supply. This is needed to remove the limitation of computations that can be performed in principle but are not practicable because they require infeasible amounts of memory and/or time. In order to translate the abstraction of the Turing machine into a real physical device, all we need to say is that such a physically possible device can compute anything that is computable, as long as we provide it with enough paper tape, time, and energy. Similarly, the quantum equivalent of the Turing machine can also be conceived, and has been described by David Deutsch.

Clearly, given the above, it must be possible to build a physical universal computer. It will only be limited by the hardware that it has access to. And we can continue to supply it with resources (energy and memory) until we run out of matter in the universe. So we can do away with talking about abstract computers and talk about physically possible computers:

It is possible to build a universal computer, a physical object that can perform any computation that any other physical object can perform.

Simulating anything in the universe

Now, why should “everything that is computable” be of interest to anybody other than mathematicians and theoretical computer scientists? Why should the Turing principle deserve to be considered a part of any viable “theory of everything”?

The answer: Because computers can simulate physical reality. It turns out that simulating physical processes using a computer has also been common since prehistoric times. Consider a goat herder putting tally marks on a wooden stick to count his goats. As the goats leave the pen, he puts a tally mark on a stick for each goat. When the goats return, he checks whether the number of tally marks is equal to the number of goats. If they are not, either some goats are missing or he has got somebody else’s goats (assuming his calculation is accurate). So one physical system, the goats, is being simulated by a completely different physical system: tally marks on a wooden stick. Note that in order to do this, the goat herder must assume that the laws of physics are such that it is irrelevant what physical system he uses to simulate the count of goats. Of course, this example is that of a very crude simulation, and we know that we can do much better.

Simulating physical processes using computers is nowadays known as generating virtual reality. The hardware that exists today can already generate sounds indistinguishable from natural sounds to the human ear. Indeed, it’s meaningless to ask whether a sound is “real” or “artificial” if it is causing the exact same effect on the listener’s ear and brain. The technology of computer-generated graphics is rapidly improving, and those for other senses like touch, smell, and taste are also not difficult to foresee. To create a perfect simulation of reality, the hardware advances that need to be made are relatively trivial compared to the software advances. The software advances in question are no different from advances in understanding the physics of the real world. Thus, it is in principle possible to create a virtual reality rendering that is indistinguishable from actual reality, if we knew the real laws of physics to arbitrary accuracy ⁶ For an in-depth discussion of how reality and virtual reality relate to each other, see Chapter 5 (Virtual Reality) of David Deutsch's book, The Fabric of Reality. . To take the converse of that: Computers can perfectly simulate (a given part of) reality because reality is rather like a computer; the initial conditions are the input, the laws are the software/program, and the final conditions are the output ⁷ That is not to suggest that we are likely living in a simulation. The 'simulation hypothesis' (as championed by Nick Bostrom) is a bad explanation for a multitude of reasons outside the scope of this article. Suffice it to say that it leads to infinite regress and is equivalent to belief in the supernatural. . This breathtaking insight is due to David Deutsch, who has stated the strongest, all-embracing, physical form of the Turing principle, known as the Church–Turing–Deutsch principle:

Every finite physical process can be perfectly simulated by a finite universal computer.

These days we take for granted the ability of computers to simulate everything from the aerodynamics of a vehicle to the collision of galaxies. The Turing principle (in its strongest form that Deutsch has argued for) makes it clear that our computers can simulate any part of reality with perfect accuracy, given the right program. This is a profound fact about reality that has far-reaching consequences.

David Deutsch uses the term “self-similarity” for this remarkable property of reality: ⁸ Quote from Chapter 4 of The Fabric of Reality.

… physical reality is self-similar on several levels: among the stupendous complexities of the universe and multiverse, some patterns are nevertheless endlessly repeated. Earth and Jupiter are in many ways dramatically dissimilar planets, but they both move in ellipses, and they are made of the same set of a hundred or so chemical elements (albeit in different proportions), and so are their parallel-universe counterparts. The evidence that so impressed Galileo and his contemporaries also exists on other planets and in distant galaxies. The evidence being considered at this moment by physicists and astronomers would also have been available a billion years ago, and will still be available a billion years hence. The very existence of general, explanatory theories implies that disparate objects and events are physically alike in some ways. The light reaching us from distant galaxies is, after all, only light, but it looks to us like galaxies. Thus reality contains not only evidence, but also the means (such as our minds, and our artefacts) of understanding it.

It is the presence of self-similarity that makes the world comprehensible to beings like us. The Turing principle shows one of the ways in which reality is self-similar. There is something exceptionally computation-friendly about the laws of physics as we find them.

Virtual reality is how we understand

The human brain is a physical object, a universal computer — at least a classical universal computer since it is Turing-complete (it can mimic a Turing machine, e.g., by using the read-write-erase-move procedure mentioned earlier). Our experience of the world is literally virtual reality. We never see what is “really out there”. We don’t even see what is in our brains: electrochemical phenomena. What we actually experience is the (clearly inaccurate) virtual reality rendering of that which is out there. The program/software that dictates how the raw sensory input is processed into the virtual reality that we end up experiencing is partly inborn and partly acquired throughout life.

To improve our understanding of the world, we habitually update the program of the brain by acquiring new theories. The Turing principle implies that what makes us intelligent, and able to comprehend the world better than any other animal, could not be any magical property of the hardware of our brain. The hardware is irrelevant as long as it is a universal computer, which is a very low bar since something as simple as a Turing machine (or more accurately its quantum counterpart) is a universal computer. Our personal computers and most programming languages are also Turing-complete and have been for decades. What makes us intelligent is the programming of our brain and the fact that we are able to update that programming. Not only does that make us “more intelligent than other animals”, but it makes us qualitatively different from them: Creating and updating virtual reality is our ecological niche. We are the only (remaining ⁹ Our now-extinct cousins such as Neanderthals also most likely occupied this niche. ) species whose members rely mainly on updating their virtual reality rendering (i.e., creating knowledge) to survive.

We understand the world by creating explanations and updating our inborn assumptions. For example, there is nothing in our genes that tells us how to make fire. Or how to make arrows and other sharp objects to hunt or fend off animals much bigger than us. Once someone has created a theory, the same ability to generate virtual reality also allows us to pass on that information to other members of our species, so they don’t have to “rediscover fire” or “reinvent the wheel” (meme replication requires that knowledge be encoded in some medium, such as speech or writing, and then decoded by another individual creatively, i.e., by creating a virtual reality rendering of the encoded message). The virtual reality renderings in the brains of other animals, insofar as there are any, are defined by their genes. They cannot update the program in any significant way in their lifetime ¹⁰ When a parrot learns to 'talk like humans', its brain has not done anything different from what its genes have encoded. There is evidence to suggest that some species of great apes, such as chimpanzees, can learn new skills in their lifetime (e.g., a new way of cracking a nut) and pass this knowledge on to other members of the species. However, this process is so time-consuming and inefficient that it does not make any real difference to their ability to understand the world. , but we can. This fact has incidentally given us the ability to reason about everything — the Turing principle necessitates that there is no limit to how accurate our rendering of reality can become. When our intuitions tell us that the Earth is flat, we can reason by creating explanations and testing them against reality. No matter how strong our intuitions are (it really, really feels like the Earth is flat), we have the ability to see past them and get closer to reality.

I will leave you with a quote ¹¹ Chapter 6 of The Fabric of Reality. by David Deutsch that summarizes the significance of the Turing principle better than I ever can:

This is the strongest form of the Turing principle. It not only tells us that various parts of reality can resemble one another. It tells us that a single physical object, buildable once and for all (apart from maintenance and a supply of additional memory when needed), can perform with unlimited accuracy the task of describing or mimicking any other part of the multiverse. The set of all behaviours and responses of that one object exactly mirrors the set of all behaviours and responses of all other physically possible objects and processes.

This is just the sort of self-similarity that is necessary if … the fabric of reality is to be truly unified and comprehensible. If the laws of physics as they apply to any physical object or process are to be comprehensible, they must be capable of being embodied in another physical object – the knower. It is also necessary that processes capable of creating such knowledge be physically possible. Such processes are called science. Science depends on experimental testing, which means physically rendering a law’s predictions and comparing it with (a rendering of) reality. It also depends on explanation, and that requires the abstract laws themselves, not merely their predictive content, to be capable of being rendered in virtual reality. This is a tall order, but reality does meet it. That is to say, the laws of physics meet it. The laws of physics, by conforming to the Turing principle, make it physically possible for those same laws to become known to physical objects. Thus, the laws of physics may be said to mandate their own comprehensibility.