The Turing Problem
Last Saturday was the centennial of Alan Turing’s birth, the famous mathematician who imagined Turing Machines. From the Stanford Encycolpedia of Philosophy:
Turing machines, first described by Alan Turing in (Turing 1937), are simple abstract computational devices intended to help investigate the extent and limitations of what can be computed.
Turing was interested in the question of what it means for a task to be computable, which is one of the foundational questions in the philosophy of computer science. Intuitively a task is computable if it is possible to specify a sequence of instructions which will result in the completion of the task when they are carried out by some machine. Such a set of instructions is called an effective procedure, or algorithm, for the task. The problem with this intuition is that what counts as an effective procedure may depend on the capabilities of the machine used to carry out the instructions. In principle, devices with different capabilities may be able to complete different instruction sets, and therefore may result in different classes of computable tasks (see the entry on computability and complexity).
Turing was one of the most brilliant minds of our time–he was an expert mathematician, a revolutionary thinker of computer science, and he helped the Allies win the second World War by breaking Nazi codes. Despite what he did for humanity, he was criminally tried for his homosexuality, chemically castrated and driven to suicide.
If you would like to learn more about this brilliant man and this brutal story, check out this incredible episode of RadioLab, the “Turing Problem:”
