11 Comments

Summary:

One hundred years after he was born, the pioneering work of brilliant British polymath Alan Turing is as important as ever — so important, in fact, that his thinking about how computers work is still visible in every single line of code that gets written.

Alan Turing

It’s 100 years since the birth of Alan Turing — the brilliant British polymath scientist whose work informs and pervades all of modern computing. Despite a criminally shortened life, he made significant contributions in many fields: helping to break the German ciphers in WWII, designing some of the first digital computers, defining the field of Artificial Intelligence and conducting research in mathematics, biology and physics.

In fact he, more than anyone, can be said to be the father of the computer. So what was his great insight? What is it he did that shaped our world so profoundly?

The Turing Machine

Turing’s breakthrough came in 1936 in a paper called “On computable numbers, with an application to the Entscheidungsproblem”. Despite its opaque title, the thinking it held and work that directly followed from it caused a deep change. As a computer programmer, I see the insights Turing described in this paper in every single line of code I write.

This is where he defined what became known as the Turing Machine.

It’s a theoretical computer running programs that operate on data. It has an infinitely long paper tape on which it stores information. The tape is divided up into cells: each cell can be empty or can have a symbol in it. The machine reads the symbol from the current cell and decides what to do next. It can change the symbol in the current cell, or move the tape left or right by one cell.

But although it is extremely simple, this machine is capable of running a surprisingly large number of programs. In fact, Turing showed that any and every result that could be computed at all could be computed by a Turing Machine. Of course, it might take a very long time for the Turing Machine to complete the program, what with all that paper tape to move… but it could still do it.

And the idea that a simple machine like this can run any possible program turns out to be remarkably powerful. In fact, when combined with the work of Alonzo Church, an American mathematician who independently developed an equivalent theory, it was unstoppable.

The Church-Turing Thesis

Turing’s claim ended up combined with the work of Alonzo Church, the American mathematician who independently developed an equivalent theory. And their thesis turns out to be key: before Turing, machines performed one or two very specific tasks: for example, a loom wove cloth, it could not calculate the national debt. Turing had conceived of a machine you could program to solve almost any problem.

The Church-Turing Thesis has two very important implications.

First, it recognized the fundamental limitations of the system — for example, that there are some programs that are not computable by any machine.

But it was the second implication that was most profound: within its limitations, a Turing Machine can be programmed to run any piece of software. In fact, one of the programs that can be run on a Turing Machine is a simulation of a Turing Machine. And the simulated Turing Machine can itself run any program that a Turing Machine can run.

This is the genius of Turing’s work, his key insight. He has defined a “Universal Machine” — one that can run simulations so powerful they are themselves universal machines.

All of modern computing is underpinned by this notion. Every piece of software you use is running on layers of simulated computers that are as powerful as the physical hardware they’re running on — and as powerful as each other. A program running on a simulated Turing Machine works exactly the same way as one running on a non-simulated one; simulation has no effect on the complexity of the programs that can be run. In fact, a program does not even need to know if it running on a simulation or not.

This makes the hardware you are running irrelevant — at least in terms of what programs are possible, even if not how fast they run.

Programmers do not write code that runs on the hardware of their computers: they write code for a simulated computer running a high-level programming language, so instead of having to tediously write incomprehensible (and error-prone) strings of 1s and 0s, you can write easily understood code in Erlang or JavaScript or Ruby, or any of the dozens of programming languages. Each language is a Turing-compatible computer running on the Turing-compatible simulation below it.

Turing defined computing — his work was the key influence on John von Neumann, who created the architecture of the modern computer. Without his insight, computers would be quaint toys; instead they are at the heart of our world. As a programmer, I truly stand on the shoulders of giants… and nobody is more fundamental or important than Alan Turing.

  1. Kerby Russell Saturday, June 23, 2012

    My favorite quote from the article:
    “…you can write easily understood code in Erlang or JavaScript or Ruby…”

    Yes, those are without a doubt the chosen languages of computer scientists everywhere when tasked with writing complex systems that need to be easily understood.

  2. thanks for sharing this little tidbit, it made for interesting weekend read.

  3. There is an outstanding 17-minute segment on Radiolab about Turing that really is a must-listen. Highly recommended: http://www.radiolab.org/blogs/radiolab-blog/2012/mar/19/turing-problem/

    1. I second this recommendation. It is a very interesting podcast.

      I just realized that it was just 50 years ago, when Turing would have been 50 had he lived, that I wrote and tested a Turing machine simulator on the IBM 1620. This was an ideal machine for this task as its memory model consisted of a long addressable sequence of digits, much like the tape on a Turing machine. We used this program to investigate Tibor Rado’s “Busy Beaver Game.”

      http://en.wikipedia.org/wiki/Busy_beaver

      Rado had come to my undergraduate institution, Wesleyan, and had given a course on computability and Turing machines.

  4. Re Turing’s death – this on the BBC this morning:
    http://www.bbc.co.uk/news/science-environment-18561092

  5. Thanks Dan for the wonderful article! It has been sometime since college, and thinking of Turing machines. And great to see you tying it effortlessly to the modern day tablet with the artwork. Enjoyed the read!

  6. The title of Turing’s seminal article got truncated in the above article. It should be “On Computable Numbers, with an Application to the Entscheidungsproblem”

    1. An editing error – now fixed, thanks.

  7. Reblogged this on projectzme and commented:
    Tragic story from a time not so far in the past.

  8. Nitin Borwankar Sunday, June 24, 2012

    The 1936 paper title seems to have been truncated ““On computable numbers, with an application to the Entscheidungsproblem”
    more on that – http://en.wikipedia.org/wiki/Entscheidungsproblem

  9. The UK Prime Minister Gordon Brown issued an official apology for the appalling way he was treated by the UK establishment. You can read the full text here: http://goo.gl/Vn8Ab It’s quite moving.

Comments have been disabled for this post