A Turing Machine Is the Hypothetical Device That Underpins All of Computation

Would you rather hear these stories in less than 10 minutes? Listen to our brand new daily podcast here.

You may have never heard of Alan Turing (although with Benedict Cumberbatch's depiction of him in The Imitation Game, that's becoming less likely) but you are definitely familiar with his work. You're using it right now, in fact. That's because he's the namesake behind the Turing machine, a theoretical device that's the basis for all modern computation.

A Philosophical Answer To A Practical Problem

At the turn of the 20th century, a "computer" referred not to an electronic device, but a person. From tax documents to scientific calculations, all the math performed up until that point happened with pencil and paper. Even when they were broken down into their smallest parts, some of these problems were too hard for the sharpest minds in math.

That led English mathematician Alan Turing to ponder the question of what it means for a task to be computable. On its face, a task is considered computable if you can lay out the instructions, or algorithm, someone or something should use to solve the problem. Of course, in the real world, what's computable for a machine might not be computable for a person. But what if you could create — at least, imagine — a perfect machine that never runs out of resources or time that can always compute the computable? You'd know beyond a shadow of a doubt what was non-computable. That was the inspiration for the Turing machine, which Turing first wrote about in 1937.

An Imaginary Model

A Turing machine, at its simplest, consists of read/write head with a paper "tape" of unlimited length that passes through it. That tape acts as the machine's data storage, just like your computer's hard drive. The head contains a sort of indicator that can be set to a particular position, or "state," which can change based on how you program it. The tape is divided into squares, and each square is either blank or bears one symbol: 0 or 1. For each square it lands on, the read/write head can do six things:

  1. Read the symbol.
  2. Write a new symbol, or edit the existing symbol
  3. Move the tape left by one square.
  4. Move the tape right by one square.
  5. Change state.
  6. Stop.

You can feed the read/write head instructions on what to do when it encounters a certain symbol. For example, if you want to turn every 0 into a 1 and every 1 to a 0, you could tell it that every time it encounters a 0, it writes a 1, then moves the tape to the right; and every time it encounters a 1, it writes a 0, then moves the tape to the right. This is what makes it a finite state machine: a machine that changes its state depending on the input (0, for example) in such a way that its next state depends on the current state and the input (it writes a 1 and moves the tape to the right).

A Turing machine's unlimited tape length is important because Turing wanted to show that even though his machines was unfettered by constraints on time and working memory, there were still tasks that they couldn't perform. For example, no person could ever write out every decimal place of pi because it's infinite. But a Turing machine can, so by definition, pi is Turing-computable. But there are plenty of numbers a Turing machine can't compute—any real number that's just a sequence of seemingly random digits that goes on for infinity counts as non-computable. In fact, non-computable numbers vastly exceed computable numbers. That's the brilliance of Alan Turing's hypothetical device. If something can be computed, it can be computed on a Turing machine.

A Primer on Turing Machines

Share the knowledge!
Written by Ashley Hamer March 17, 2017