Mathematics in Crisis: Hilbert's Program

In the early 20th century, mathematics faced a crisis. The rapid development of new mathematical concepts and notations raised concerns about the foundations of mathematics. David Hilbert, a prominent mathematician, initiated a project known as Hilbert's Program to address these concerns. Hilbert's goal was to formalize all of mathematics, creating a system that was both consistent (free from contradictions) and complete (capable of proving or disproving any mathematical statement).

Reasons for Formalism:

• The emergence of algebraic methods as a powerful language for describing mathematical abstractions.
• The erosion of the authority of Euclidean geometry and challenges to long-held axioms.

Intentions of Formalism:

• To demonstrate that all of mathematics could be derived from a carefully chosen, finite set of axioms.
• To prove that such an axiomatic system was consistent, meaning that it was free from contradictions.

An axiom is a statement accepted as true without requiring proof. It serves as a starting point for deducing other truths within the system.

Hilbert & Ackermann's Entscheidungsproblem

Hilbert and Ackermann's Entscheidungsproblem, or"decision problem" posed two fundamental questions:

1. Is there an algorithm or computational method to determine if a mathematical statement is provable within a given axiomatic system? In other words, is there a way to determine if a statement is true in every possible interpretation of the axioms?
2. Can all true mathematical statements be proven from the axioms of a system?

These questions were later answered negatively by the work of Alonzo Church, Alan Turing, and Kurt Gödel.

Gödel's Incompleteness Theorem

Kurt Gödel's incompleteness theorems shook the foundations of mathematics. Gödel proved that any consistent formal system capable of expressing basic arithmetic is inherently incomplete. This means that there will always be true statements within the system that cannot be proven within the system itself. Gödel's work demonstrated that Hilbert's goal of a complete and consistent axiomatic system for all of mathematics was unattainable.

The Link to Computer Science

In the 1930s, Alan Turing and Alonzo Church independently developed formalisms for defining algorithms. Turing's work led to the Turing machine, a theoretical model of computation, while Church developed lambda calculus, a formal system for expressing computation. These formalisms led to the development of the Church-Turing thesis, which states that any problem that can be solved by an algorithm can be solved by a Turing machine. Conversely, problems that cannot be solved by a Turing machine are considered uncomputable.

The Halting Problem

Alan Turing's work on the Halting Problem further illustrated the limits of computation. The Halting Problem asks whether, given a program and an input, it is possible to determine if the program will eventually halt (stop running) or run forever. Turing proved that no general algorithm exists that can solve the Halting Problem for all possible programs and inputs. This means that the Halting Problem is undecidable.

Undecidability

Undecidability refers to the existence of problems for which no algorithm can provide a correct answer for all possible inputs. The Halting Problem is a classic example of an undecidable problem. It highlights a fundamental limitation in computational theory: not all questions about the behavior of programs can be answered algorithmically. Some problems are inherently beyond the reach of any general-purpose algorithm.

The discovery of undecidable problems like the Halting Problem has profound implications for computer science and our understanding of the limits of computation. It demonstrates that there are fundamental limits to what can be computed, even with arbitrarily powerful computers.