Look at the picture above. Believe it or not, that person is operating an extremely sophisticated mechanical calculator, capable of generating tables that evaluate functions called “polynomials.” Although a graphing calculator can do that, a pocket calculator certainly can’t. The device above is a mechanical purpose-built computer!

This article is the next installment of my series on computing. In the previous parts, we learned about Boolean logic, the language computers think in. We then learned how to implement this logic electronically and, using our newfound understanding of electronics, how to make computer memory so that computers can record results of calculations. Finally, last time, we discussed a theoretical computer called a Turing machine (named after, of  course, Alan Turing). It is believed that the answer to a problem can be computed if and only if one can build a Turing machine to compute it.

This time, we use our discussion of the Turing machine to try and nail down what a computer really is.

(If you haven’t read the article on the Turing machine, I recommend you do so now. I’ll be relying on it extensively. It’s here.)

The Universal Turing Machine

Recall from our discussion last time that a Turing machine has three parts:

1. A ticker tape consisting of cells that can be written in. We select an alphabet of symbols we’re allowed to write. For example, you could easily use the real alphabet or every character available in unicode—whatever you like.
2. A “head” that can read from the tape and write to it. The head also has a finite number of “states” or modes. You can think of these in the same way as the modes available to your printer at home: a “scan” mode, a “print” mode, mavbe a “fax” mode. These determine what the printer does with the input it’s given. Similarly, the state of the head determines what it does when it reads a symbol.
3. A rules table. The table tells the head what to do when it reads a symbol off of the tape, given the state it’s currently in.

Given a computable problem to solve, one can design a Turing machine to solve it by constructing an appropriate rules table. But what if we want to go the other way? What if we want to design a Turing machine that can solve any computable problem?

Turing realized that it’s possible to design a Turing machine that can mimic any other Turing machine. The simplest, most obvious way to do this is just add more modes to the head. For example, suppose we had two problems we wanted to solve, problem 1 and problem 2. And suppose we know how to construct a Turing machine to solve each problem respectively: machine 1 and machine 2. And, for simplicity, let’s say that both machines use the symbols “1” and “0” and have three modes, “red,” “green,” and “blue.”

Now let’s construct a new Turing machine, machine 3, with SIX modes: “red1,” “red2,” “green1,” “green2,” “blue1,” and “blue2.” We’ll give it the following symbols to use: “1,” “0,” “A,” and “B.”

Then we construct the rules table such that if the state is red1, green1, or blue1, and the symbol is either 0 or 1, then machine 3 behaves like machine 1. The rules for the state red1 correspond to the rules for machine 1 in the red state, and likewise for green1 and blue1.  Similarly, if the state is red2, green2, or blue2 and the symbol on the tape is either 0 or 1, then the machine behaves like machine 2.

The only thing we have to do is determine whether the machine uses the states for machine 1 or for machine 2. We do that with the special symbols A and B. If the machine reads symbol A on the tape, it knows to behave like machine 1. If the machine reads symbol B on the tape, it knows to behave like machine 2.

Now machine 3 can solve either problem 1 or problem 2! And we can keep going like this—if we add an arbitrary number of states, we can solve an arbitrary number of problems. A Turing machine that can mimic any other Turing machine (and thus solve any computable problem) is called a universal Turing machine. A universal Turing machine is the standard model of a fully programmable computer.

Can You Build One?

But if we needed an arbitrarily large number of modes to solve all problems and thus make a computer, that would be pretty useless. Since the number of problems we’d like a computer to solve is incredibly huge, it would be impossible to construct a computer with one mode for every single type of problem in existence (including those we haven’t even thought of yet).

So are modern computers only pale approximations of universal Turing machines? Fortunately, no. AI researcher Marvin Minsky showed in 1962 that you can construct a universal Turing machine with only seven modes and a four-symbol alphabet. Later, it was discovered that we only need a binary alphabet (1 and 0) if we use 15 modes. So yes, it’s possible to build a real-life universal Turing machine. That’s good to know, since you’re probably reading this post on one of them!

So What Is A Computer, Really?

We’re finally ready to answer our title question and tie all of this abstract computational theory back to practical electronics. A “computer” is any device that can be shown to be equivalent to a universal Turing machine. (This property is called Turing completeness.) For a device to be Turing complete, it needs the following three pieces, roughly speaking:

1. A set of logical rules dictating how it should behave given some input. On a Turing machine, this is the rules table. In an electronic computer, it’s the Boolean logic gates we constructed out of vacuum tubes or transistors.
2. A way to record the results of a calculation and read these results in as new input. On a Turing machine, this is the ticker tape. In an electronic computer, this is the computer memory constructed from electronic flip-flops.
3. A way to control the device’s logic so that the same input data can be manipulated in many different ways. On a Turing machine, this is enabled by having many modes for the head. I didn’t discuss how to achieve this in an electronic computer, but we’ll suffice to say that it exists.

With these three components, it is possible to construct a universal Turing machine, or at least something equivalent. But notice that these criteria don’t limit us to electronic devices! Any device that meets them can do anything a laptop can do (albeit probably much much slower)!

Next time we’ll take a break from hardcore theory to discuss some cool examples of non-electronic computers.

A Historical Note

Although electronic computers have been shown to be Turing complete, this may or may not have really been considered during their design. Computer pioneer John von Neumann and people the working on early digital computers were certainly inspired by Turing and von Neumann extended Turing’s work. However, modern architectures weren’t really known to be related to Turing machines. It was only later that mathematician Hao Wang demonstrated that electronic computers were Turing complete.

Other Approaches

Turing’s machines aren’t the only mathematical description of what it means to be a computer. Mathematician Alonzo Church developed a completely equivalent description based on the mathematical definition of a function, called Lambda calculus. I find it beautiful, but I’m not going to try to describe it here because it’s very abstract–check out the link if you’re a fellow math nerd.

Further Reading

There are many many resources on the Turing machine, but most skip what’s special about a universal Turing machine. Here’s what I could find.

• The article on Wolfram Mathworld has some nice diagrams from Stephen Wolfram‘s book.
• The Wikipedia article on the universal Turing machine is very good.
• Science Decoded has a nice article on universal Turing machines.
• Here‘s a free short biography of Alan Turing which discusses universal Turing machines a little.
• The academic among you may want to check out the article on Turing machines on Scholarpedia. Scholarpedia is a free collection of peer-reviewed articles on scientific topics. It’s very good.
• Adam Black on Google+ suggested this nice article on the Church-Turing thesis.

Related Reading

This is the sixth article in a multi-part series on computing. These are the other parts:

• In this article, I describe the basics of Boolean logic, starting with truth tables.
• In this article, I describe how to make composite logical statements using Boolean logic.
• In this article, I introduce the triode vacuum tube and describe how it works.
• In this article, I show how to use triodes to make logic gates.
• In this article, I explain how to build computer memory.
• In this article, I explain how a Turing machine works.

That’s all for now. Thanks for reading!