Turing machines and the limits of computation
Alan Turing was a founding father of computer science. In popular culture, he is best known for his wartime code breaking, for proposing the “Turing test” to measure machine intelligence, and sadly for his mistreatment by the UK Government on the grounds of his sexuality. However, his most important contributions are much less known, yet are fundamental to our understanding of what computers can and can not do.
At the centre of these contributions lies the Turing machine. This is not the machine that Turing developed to break German codes at Bletchley Park; that one is called the Bombe. To look at, the Turing machine is a lot less interesting than the Bombe. It’s basically a tape, a read-write head, and some logic that determines what gets read from or written to the tape at any given time. Oh, and the tape is infinite in length. This might give a clue to the fact that the Turing machine is a theoretical construct, not meant to be made into a real machine1. Indeed, the purpose of a Turing machine is to strip away all the complexity that’s required to make a real-world computer, and get to the essence of what a computer is.
Turing’s important realisation was that, although a Turing machine may not look much like a computer, it can still compute exactly the same things that any real computer can compute2. In computer science lingo, this is known as Turing completeness, and it’s usually phrased the other way around — that is, any computer that can do the same things as a Turing machine is known to be Turing-complete. Currently this includes all computers.
Now, the good thing about the Turing machine being relatively simple is that this makes it easier for a theoretician like Alan Turing to reason about its behaviour, and — following from Turing completeness — the behaviour of all computers. Most importantly, it allowed him to show that computers have limits, i.e. that there are things that computers fundamentally can not do.
A simple, but powerful, example of this is something known as the Halting Problem. Simply stated, this is the problem of determining, for a given program with a given input, whether this program will ever stop running. This may sound rather abstract, but if we can solve this problem, then we know that there’s a way of telling whether a piece of software can get stuck in an infinite loop. An infinite loop is when a program keeps doing the same thing over again, with no way of stopping it, save from pulling the plug. If the control system of something safety-critical, like an aeroplane or a medical device, gets stuck in one of these, then it could have some unpleasant consequences. So, we’d like to be able to prove that a program can’t get stuck in one.
Unfortunately, Turing showed that the Halting Problem can not be solved. The proof is relatively simple, and goes something like this: First of all, assume that we can write a program that can solve the Halting Problem. Let’s call this program DoesItHalt. If you give DoesItHalt another program along with that program’s input, DoesItHalt can tell you whether it will ever halt. Then let’s make a program called TroubleMaker that takes a program P as its input, and then asks DoesItHalt whether P will halt when P’s input is P itself. TroubleMaker is so named because it does the opposite of whatever DoesItHalt says, i.e. it if says P will halt, TroubleMaker goes into an infinite loop; if it says P will get stuck in an infinite loop, TroubleMaker halts.
Things then get interesting when you consider what happens if TroubleMaker’s input is TroubleMaker itself. This causes TroubleMaker to ask DoesItHalt whether it will itself halt. If DoesItHalt says it will halt, TroubleMaker goes into an infinite loop, meaning that DoesItHalt was wrong. If DoesItHalt says TroubleMaker won’t halt, TroubleMaker halts, again meaning that DoesItHalt was wrong. In the mathematical proof trade, this is known as a contradiction, and the only logical resolution is to throw out the original assumption that we can write a program that can solve the Halting Problem.
Now, I used the term “program” quite loosely here. In Turing’s proof, programs are actually Turing machines, and this allowed him to get around the practical niggles of what constitutes a program and what constitutes its input. Having already shown that all computers are effectively equivalent to a Turing machine, this did not limit the generality of his proof, and allowed him to make some profound statements about what all computers can and can not do. That is, unless you are a believer in hypercomputation.
A hypercomputer is a computer that can solve problems that Turing Machines are unable to solve. For example, a computer that is able to solve the Halting Problem would be a hypercomputer. However, don’t rush down to the shop to buy one yet, because they haven’t been invented. Even if they can be invented (which is a matter of some debate), they’d probably have to rely on some pretty exotic physics — like the kind you get around black holes — so would be hard to install in a home office.
Beyond its role in understanding the limits of computation, the Turing machine has also been instrumental in helping to understand the nature of computation. This is largely a story for another day, but there are many examples of people taking quite unusual physical, chemical and biological systems and showing that they can be used to implement a Turing machine, thus proving that they can do anything that any other computer can do. A wacky example is the card game Magic: The Gathering. In principle, a bunch of people sitting around playing this card game can carry out any kind of computation. However, things are not that simple in practice. In addition to whether a problem can be solved, we also want it to be solved in a reasonable period of time whilst using reasonable resources. If it takes a million card players all year to do something that your computer could do in seconds, then solving a problem in this way is not going to be practical. However, this is also a topic for another day3.
So, in a nutshell, this is the story of Turing machines and the limits of computation. Turing’s work in this area is fundamental to our understanding of computers and their capabilities, and is a great example of how the more theoretical topics in computer science can have profound real world relevance.
Though, of course, people have attempted to do this. See this one by Mike Davey and this video of a Turing machine implemented in Minecraft.
Note that I’m being a bit loose with terminology here. A Turing machine that can compute anything is, strictly speaking, known as a universal Turing machine. A vanilla Turing Machine is one that solves a specific problem.
This is the story of computational complexity, and the ultimate question — does P = NP?