The origins of computer science are deeply connected to a crisis in the foundations of mathematics in the early twentieth century.
In the late 19th and early 20th century, mathematicians sought to place all of mathematics on a rigorous logical foundation.
Kurt Gödel shattered Hilbert’s program:
KEY TAKEAWAY: Gödel proved that mathematics cannot be fully axiomatised. There are always true but unprovable statements. This set the stage for deeper questions about what is computationally decidable.
Posed by David Hilbert and Wilhelm Ackermann in 1928:
Is there an algorithm that takes as input a statement of first-order logic and decides (Yes/No) whether the statement is universally valid?
Entscheidungsproblem means the Decision Problem in German. Hilbert believed the answer was yes. Two mathematicians independently proved it was no in 1936.
Church developed the lambda calculus ($\lambda$-calculus), a formal system for computation via function abstraction and application. He proved the Entscheidungsproblem was unsolvable (Church’s Theorem, 1936).
Turing independently developed the Turing machine model of computation and proved that no Turing machine can solve the Halting Problem for all inputs, thereby resolving the Entscheidungsproblem negatively.
Both models capture the same class of computable functions. The Church-Turing Thesis states:
Any function that can be effectively computed can be computed by a Turing machine.
| Year | Event |
|---|---|
| 1900 | Hilbert poses 23 problems at the International Congress of Mathematicians |
| 1901 | Russell’s Paradox undermines naive set theory |
| 1928 | Hilbert and Ackermann pose the Entscheidungsproblem |
| 1931 | Gödel’s Incompleteness Theorems |
| 1936 | Church proves unsolvability via $\lambda$-calculus |
| 1936 | Turing introduces the Turing machine; resolves Entscheidungsproblem negatively |
The work of Church and Turing:
- Established the theoretical foundations of computation
- Defined the limits of what algorithms can achieve
- Led to the design of modern computers (von Neumann architecture inspired by Turing’s theoretical model)
- Gave birth to computer science as a formal discipline
EXAM TIP: Key names: Hilbert and Ackermann (posed the Entscheidungsproblem), Church (lambda calculus) and Turing (Turing machine) (resolved it). Key year: 1936.
VCAA FOCUS: Understand the progression from the foundational crisis to Gödel’s incompleteness to the Entscheidungsproblem and its negative resolution by Church and Turing. This narrative explains why computer science emerged as a discipline.
