(BONUS) The Ultimate Computer
Disclaimer
This if the first (BONUS) chapter, which means that you can skip it without worrying too much that you’re missing something essential. This chapter is a little bit mind-bending, but it also reveals one of the coolest facts about computers.
Total Recall
Now that we’ve learned a good deal about computers, let’s recall why they were created in the first place. Humans can compute things by hand, but that’s error-prone and slow. Machines can be built to perform specific computations, but those are hard to design and have limited uses. Computers nicely solve these problems by being fast and accurate, but also easily reconfigurable to perform different computations. But is it possible that computers still aren’t good enough? Is there yet another even more generalized machine that can do everything a computer can and more?
Spoiler alert: there isn’t. Now don’t be too disappointed, because this simple fact is actually amazing and we are now going to see why. Let’s recall what a computer does: it evaluates functions using algorithms. We saw the Turing machine as a perfect example of this. You give it input, tell it the algorithm to perform, it cranks away and out comes your answer. Let’s write that down like this:
input + algorithm → Turing machine → answerEarlier I described computers as machines that compute computing machines. Now let’s try to apply that principle once more to get one level of abstraction higher: a machine that computes computers, a sort of meta-computer. We’d want it to be able to act like any kind of computer, just like a computer can act like any kind of computing machine—something like this:
input + algorithm + computer → meta-computer → answerBut here’s the kicker. Recall how a Turing machine operates—how its various components interact. Predicting what a Turing machine will do given certain input is a simple matter of following the steps as it reads its instructions and manipulates the tape. Hm… “following the steps,” that sounds like an algorithm… Come to think of it, if you give a Turing machine input and an algorithm, it produces the same output every time. That sounds like a function! And what do you get when you combine a function with an algorithm? A computable function!
Did you catch that? Turing machines are computable functions, which means they can be described with algorithms. That means we can rewrite our meta-computer diagram. The “computer” that we were providing is really just another algorithm.
input + algorithm + computer algorithm → meta-computer → answerThere’s another trick too: we can group the old input and algorithm together and call it our new input. “new input = input + algorithm” so the diagram now looks like this:
new input + computer algorithm → meta-computer → answerBut wait, why do we need a meta-computer for this stuff? It’s the same old “input + algorithm → computer → answer” as before, just rebranded. Our fancy metacomputer is just a computer. Did I just blow your mind?
So What?
This is one of the most powerful properties of computation: any computer can simulate any other computer. You can simulate the operation of a Turing machine using a Turing machine. And even better, by the law of mathematical induction you can repeat this process of abstraction arbitrarily many times. You can simulate a Turing machine inside a Turing machine being simulated by a Turing machine and so on. The possibilities are literally endless.
Modern computers take advantage of this endless abstraction to make computers easier to use for humans. We start by building a computer that works sort of like a Turing machine: relatively simple to build but kind of confusing to use. Then we come up with more complicated computers that are a little easier to use, but rather than needing to build them out of physical materials, we can simply simulate them using the Turing machine. Rinse and repeat until you have an incredibly advanced and complicated computer all working inside your simple Turing machine.
When a machine is abstract enough that it can simulate a Turing machine, we call it Turing complete.
If a machine can simulate a Turing machine, then it can also perform any computation. Thus it is a computer. Thus it can simulate any other type of computer. So “complete” is a good word to use here because once a machine is Turing complete it’s basically done; we don’t need to make it any more complex. Any further complexity can be added by making the computer simulate more complex computers.