Why we owe it all to 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 “. 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.

Related research and analysis from GigaOM Pro:
Subscriber content. Sign up for a free trial.