Saturday, June 23, 2012

Why we owe it all to Alan Turing

by Dan Crow on Gigaom.

…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 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.