Sipser: Section 3.3

From CSWiki

The Definition Of Algorithm

The concept of algorithm exists since ancient time as mathematicians wrote down steps for solving problems such as finding greatest common divisors, least common multiplier and finding prime numbers. However, not until 20th century had the formal notion of algorithm itself had been explicitly studied (see entries below)

The people behind the theory

Alan Turing was one of the founders of modern computer science. He also helped to break the enigma code during World War II. Besides the Turning machine, he is perhaps most famous for the Turing Test for computer intelligence.

Alonzo Church was a logician and mathematician. He invented the lambda calculus.

David Hilbert, a prominent mathematician of the 20th century, set out a research plan in 1900 that involved an assumption that the problems he posed could be solved algorithmically. Church and Turing's formal definition of an algorithm disrupted this assumption, dramatically shaking up the leading mathematical thought of the time.