Following Entscheidungsproblem, many other mathematical problems, posed as questions about the construction of this or that algorithm, were analyzed from the standpoint of algorithm theory. Some of these difficult problems, which had remained open for decades, turned out to be algorithmically unsolvable problems.
Among these kinds of problems, the most famous is Hilbert’s 10th problem about recognizing the solvability of dioffant equations. A Diophant equation is an equation of the form , where is a polynomial with integer coefficients on the variables , …, . It is required to find out from a given polynomial , whether there are integers , …, , satisfying this equation.
Hilbert’s question of constructing a general algorithm that works for all Diophantine equations looked hopeless from the very beginning. With the advent of algorithm theory, researchers began to make efforts to prove the unsolvability of this problem. The American logicians J. Robinson, M. Davis, and H. Putnam obtained intermediate results in this direction, and the final solution of the problem was obtained only in 1970 by the Leningrad mathematician Yu.
Nowadays algorithmic problems occupy an important place in mathematics. Mathematical logic has taught us that not every such question is solvable. Moreover, even if an algorithm for solving this or that problem exists in principle, it is not always possible to talk about its applicability in practice. For example, the execution of the algorithm may require too much time or too much computer memory. This kind of issues is dealt with in a separate area of algorithm theory – the theory of computational complexity, which is discussed in detail in another article of this collection.
Gödel’s Theorems and Unprovable Assertions. Another discovery made by the brilliant Austrian logician Kurt Gödel in 1931 was the phenomenon of incompleteness of axiomatic systems. Gödel’s famous incompleteness theorems not only had a great influence on the development of mathematical logic and gave rise to the theory of algorithms, but also became a cultural phenomenon, affecting even the work of writers and artists. Gödel was named one of the 100 most influential personalities of the 20th century by Time magazine. However, the prominence of Gödel’s theorems also leads to the fact that they are often interpreted in an overly expansive, metaphorical sense.
Gödel’s theorems belong to the class of axiomatic systems that satisfy two natural and broad requirements. First, the concept of a natural number and the operations of addition and multiplication must be at least expressible in the formal language in question. At first sight, this requirement seems very special, but natural numbers are one of the basic mathematical objects, and languages that pretend to formalize a large part of mathematics must allow one to talk about them.
Second, there must be an algorithm that recognizes whether a given text is an axiom of the theory in question or not. (If the axioms of the theory are unrecognizable, it is not clear how one can build a proof in such a system.)
Gödel showed that if these requirements are met, any system of axioms is either contradictory or incomplete. Moreover, for any non-contradictory system one can explicitly specify a proposition concerning the arithmetic of natural numbers that cannot be either proved or disproved in a given system (such statements are usually called independent of a given system of axioms). In particular, this means that the system of axioms of formal arithmetic cannot be “extended” in any consistent way: there will always be arithmetic statements independent of it. This is the content of the so-called first Gödel theorem.
Gödel’s second theorem says that a statement expressing the consistency of a given axiomatic system is not provable in the system itself, if that system is indeed consistent. If one assumes that standard mathematical methods fit within an axiomatic set theory, then it follows, for example, from this theorem that standard mathematical methods cannot establish the consistency of set theory (and thus their own consistency).
Gödel’s theorems made it possible to construct the first examples of independent assertions for strong systems of axioms, such as arithmetic or even set theory. Since Gödel’s work, such examples have been found among open problems in various fields of mathematics. One of the most famous discovered problems in mathematics was the Cantor continuum hypothesis, according to which every infinite subset of a set of real numbers is either countable (equal to the set of natural numbers) or continuum-like (equal to the set of real numbers). In 1938 Gödel managed to prove that this hypothesis cannot be disproved in set theory, and in 1961 the American mathematician Paul Cohen established its unprovability.