A question about truth

Either mathematics is too big for the human mind, or the mind of man is something more than a mere machine.

The history of this work blends two fields of philosophy and mathematics: logic and computer science.

Logic is one of the oldest branches of philosophy, developed in China, India, Greece, and the Islamic world. The theories of Aristotle were influential for millennia, while Stoics like Chrysippus of Soli began developing propositional logic. In 17th- and 18th-century Europe, Leibniz and Lambert worked toward formalizing logical operations, although their work remained isolated and little known².

Computer science would not emerge until later. Although an approximation to the notion of an algorithm had been studied for millennia, it was not until the mid-19th century that the first forms of computing devices were designed, with the work of Charles Babbage and Ada Lovelace³.

In parallel, George Boole and Augustus De Morgan presented systematic treatises on logic, extending the Aristotelian logical doctrine to form a new field of mathematical study.

Shortly thereafter, flaws were discovered in the axioms of Euclidean geometry. In addition to the independence of the parallel postulate, established by Nikolai Lobachevsky in 1826⁴, it was discovered that some theorems previously considered proven by Euclid were in fact not provable from the axioms. Among these theorems were results such as that a line contains at least two points, or that two circles of equal radius whose centers are that radius apart must intersect. At the end of the century, Hilbert² published Grundlagen der Geometrie ("The Foundations of Geometry"), a complete set of axioms for geometry, based on the earlier work of Moritz Pasch.

It was at this time that Giuseppe Peano published a set of axioms for arithmetic (which we will discuss in Chapter 4).

Hilbert's success motivated him to seek complete axiomatizations of other areas of mathematics, such as number theory. This would be the seed of one of the most popular research areas of the early 20th century.

In 1900, this same mathematician published his famous list of 23 problems for the new century (known today as Hilbert's problems) at the Second International Congress of Mathematics in Paris. The second of these asked about the consistency of the axioms of arithmetic⁵.

In 1910, Bertrand Russell and Alfred Whitehead published the first volume of Principia Mathematica⁶, considered one of the most influential works of the 20th century.

In 1928, Hilbert reformulated his second problem at the International Congress in Bologna, posing three questions:

1. Is mathematics complete? That is, can every mathematical statement or its negation be proved?
2. Is mathematics consistent? That is, is it impossible to simultaneously prove a statement and its negation?
3. Is mathematics decidable? That is, is there an automatic method that can be applied to any mathematical statement and determine whether it is true? This problem is known as the Entscheidungsproblem.

We explore the concepts of completeness, consistency, and decidability in Chapter 4. Hilbert's goal was to find a complete and consistent mathematical system in which statements can be expressed precisely and can be proven automatically.

In 1931, Kurt Gödel shattered Hilbert's dreams by publishing Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I ("On Formally Undecidable Propositions of Principia Mathematica and Related Systems")⁷. In this paper, Gödel proves the incompleteness of certain systems. This result establishes severe limitations on the axiomatic foundations of mathematics. Hilbert, however, did not recognize the importance of this result for some time. Shortly thereafter, Gödel introduced one of the first notions of recursive definitions (today called $\mu$-recursive functions).

The first proof of the undecidability of the Entscheidungsproblem was given by Alonzo Church in 1936⁸, using the notion of $\lambda$-computable functions. In it, Church demonstrated the equivalence with Gödel's $\mu$-recursive functions, and ventured that these functions would be the only ones computable by an algorithm, a thesis that bears his name: the Church thesis.

One year later, Alan Turing attacked the same question from a different angle. In On Computable Numbers, with an Application to the Entscheidungsproblem⁹ he defined a Turing machine: an ideal device with finitely many internal states, a one-dimensional tape, and a head that reads and writes one symbol at a time. A computation is nothing more than following a finite table of instructions—exactly the kind of “automatic method” Hilbert's third question had asked for, made precise.

Turing used this model to show that several problems cannot be decided by any such machine. His argument is constructive: once computation is identified with machine runs, one can prove that no machine can settle certain questions about other machines—the Entscheidungsproblem among them. He also proposed what is now called Turing's thesis: that every function computable “by hand”, or by an algorithm in the intuitive sense, is computable by a Turing machine. Although the thesis cannot be proved, Turing gave many independent arguments for it in the same paper.

The abstract definition becomes much easier to grasp once one can watch a machine run. The simulator below is not taken from Turing's article—it is a modern encoding of a machine we analyze in Chapter 2—but it displays the same ingredients he had in mind: a finite graph of states and transitions, and a tape whose contents change step by step. Run it on abbaa to follow an accepting computation, or try another word over {a,b} to see how a single fixed program accepts some inputs and rejects others. That interplay between a finite program and an unbounded input is the heart of Turing's model.

Later, Church, Turing, and Stephen Kleene¹⁰ proved that the three models of computation introduced ($\mu$-recursive functions, $\lambda$-computable functions, and Turing machines) are equivalent, reinforcing the aforementioned theses and introducing the Church–Turing thesis.

The 20th century saw an exceptional development of computer science and the birth of informatics, leading to the revolution of personal computers and mobile devices today. All of this was made possible thanks to the work of, among others, the mathematicians mentioned in this brief overview.