2013: Advent Computing: The Turing machine

by on December 1, 2013

If we’re going to have a series of posts about computer science, it’s probably helpful to define what a “computer” is. So let’s do that.

The standard academic definition of a computer is what’s called a “Turing machine”. It goes a little bit like this: Imagine you have a roll of paper such as a till roll, with lines drawn across it to make squares down the length of the roll. You have a pencil and an eraser, which you’ll use to write symbols in those squares.

You also have a book, which is rather like one of those game books that say “if you fight the monster, turn to page 83; if you run away and open a chain of all-night guitar shops, turn to page 12”. Except there are rules about what instructions can be in this book: they must be of the form “if the symbol on the bit of the role in front of you is {symbol}, do {task} and turn to page {page}”. Here, {task} must be “look at the symbol to the left/right of this one”, or “replace that symbol with {symbol}”. You can have an instruction that says “stop”, too.

There’s another subtle restriction: the roll of paper needs to be infinitely long,and the book of instructions needs to have a finite (but it can be very large) number of pages.

Here’s a video of a model Turing machine, which is probably a lot easier to understand than all the above. Depending on the “state” (i.e. the page of the book) it’s in, and whether it’s little camera sees a “1” or a “0” on the roll of paper, it’ll either roll the paper somewhere or erase the paper and put a new symbol down.

This is, of course, an utterly useless definition. Certainly my home computer is a bit fancier than that. But that useless definition gives computer scientists a very simple model of what a computer does, and we know how to do anything a modern computer can do with a Turing machine. A Turing machine will just take a hell of a long time about it.

Leave a Reply