ABSTRACT
The mathematical foundations of computer science predate the development of the first electronic computers by a few decades. The early 20th century saw pioneering work by Alonzo Church, Alan Turing and others towards the formulation of an abstract definition of computability. This effort was in the context of one of David Hilbert’s challenges, the Entscheidungsproblem, which asked whether all mathematical truths could be deduced “mechanically” from the underlying axioms. Church and Turing showed, independently, that it is impossible to decide algorithmically whether statements in arithmetic are true or false, and thus a general solution to the Entscheidungsproblem is impossible.
