CS for Oblivious Turing Machines (and you)

The answer to the question, What is a Computer?

Or rather, it is a model created by Alan Turing to capture the idea of computing something. (The original paper is here, if you want to read it.)

If I gave you an multiplication problem, you would probably grab a pencil and paper and work it out. If I gave you a quadratic equation to solve, or a list of numbers to sort, or a long word to check if it is a palindrome... you would do the same. You’d take a paper, work it out and give me the answer. Some problems would take more time or more paper than others.

Turing wanted to formalize this idea. So the Turing Machine consists of a head (that’s you!) that can read and write, and a tape (that’s your paper!) that it can read from and write on. The tape is infinitely long and divided into squares. The head moves up and down the tape. 

So the input of the problem (like the list of numbers to be sorted) is already written on the tape. The machine reads it, writes something (like rough work) and then writes the answer (the output) somewhere on the tape. 

How does the machine know what to do? Well, when we describe a machine, it also comes with a set of states, which abstractly say what the machine is thinking. Depending on what state it is in, it decides what to do with whichever square on the tape it is looking at. Then it can move to another state, or remain in the same state. The states are related by transition rules, which tell it what to write, how to move the head and which state to go to next. 

That’s a bit of a confusing idea, so imagine yourself multiplying two five-digit numbers. First, you multiply the first number by each digit in the second number, writing the answers slightly to the left each time, then you add all of them. How do you know to stop multiplying and start adding? Well, you changed your state!

The cool thing about Turing Machines is that they are so powerful that making some changes does not add to their power. If you added more tapes or more heads, you can show that it can’t do anything more than a Turing Machine with just one tape and one head! So since they are equivalent, some people like to think of Turing Machines as having three tapes: one where the input is written, one for it to work out stuff, and one to write the answer.

So Turing Machines can do most math problems we can think of, and many many others. But there are some things it can’t do - look for the next article!