Introduction to Turing Machines

Historical background

In this lesson, we'll study a type of machine called the Turing machine (TM), named after the mathematician Alan Turing, who proposed the idea in 1936. At the time, he was trying to show that no universal algorithm could decide all logical mathematical questions, as the celebrated mathematician David Hilbert had proposed. It naturally followed that Turing needed to precisely define what an algorithm is. Others were also working on solving the same problem (notably Kurt Gödel, Alonzo Church, and Stephen Kleene), but it was Turing’s formulation of the nature of computations that proved to be the simplest and most effective, and also provided a sound theoretical foundation for the computer revolution.