In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
and
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, an undecidable problem is a
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
for which it is proved to be impossible to construct an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
that always leads to a correct yes-or-no answer. The
halting problem
In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...
is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.
Background
A decision problem is a question which, for every input in some infinite set of inputs, requires a "yes" or "no" answer. Those inputs can be numbers (for example, the decision problem "is the input a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
?") or values of some other kind, such as
string
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
s of a
formal language
In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet".
The alphabet of a formal language consists of symbols that concatenate into strings (also c ...
.
The formal representation of a decision problem is a subset of the
natural numbers
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...
. For decision problems on natural numbers, the set consists of those numbers that the decision problem answers "yes" to. For example, the decision problem "is the input even?" is formalized as the set of even numbers. A decision problem whose input consists of strings or more complex values is formalized as the set of numbers that, via a specific
Gödel numbering
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. Kurt Gödel developed the concept for the proof of his incom ...
, correspond to inputs that satisfy the decision problem's criteria.
A decision problem ''A'' is called decidable or effectively solvable if the formalized set of ''A'' is a
recursive set
In computability theory, a set of natural numbers is computable (or decidable or recursive) if there is an algorithm that computes the membership of every natural number in a finite number of steps. A set is noncomputable (or undecidable) if it is ...
. Otherwise, ''A'' is called undecidable. A problem is called partially decidable, semi-decidable, solvable, or provable if ''A'' is a
recursively enumerable set
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
.
[This means that there exists an algorithm that halts eventually when the answer is ''yes'' but may run forever if the answer is ''no''.]
Example: the halting problem in computability theory
In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
, the
halting problem
In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...
is a
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
which can be stated as follows:
:Given the description of an arbitrary
program and a finite input, decide whether the program finishes running or will run forever.
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher and theoretical biologist. He was highly influential in the development of theoretical computer ...
proved in 1936 that a general
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
running on a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
that solves the halting problem for ''all'' possible program-input pairs necessarily cannot exist. Hence, the halting problem is ''undecidable'' for Turing machines.
Relationship with Gödel's incompleteness theorem
The concepts raised by
Gödel's incompleteness theorems are very similar to those raised by the halting problem, and the proofs are quite similar. In fact, a weaker form of the First Incompleteness Theorem is an easy consequence of the undecidability of the halting problem. This weaker form differs from the standard statement of the incompleteness theorem by asserting that an effective
axiomatization
In mathematics and logic, an axiomatic system is a set of formal statements (i.e. axioms) used to logically derive other statements such as lemmas or theorems. A proof within an axiom system is a sequence of deductive steps that establishes ...
of the natural numbers that is both complete and
sound
In physics, sound is a vibration that propagates as an acoustic wave through a transmission medium such as a gas, liquid or solid.
In human physiology and psychology, sound is the ''reception'' of such waves and their ''perception'' by the br ...
is impossible. The "sound" part is the weakening: it means that we require the axiomatic system in question to prove only ''true'' statements about natural numbers. Since soundness implies
consistency
In deductive logic, a consistent theory is one that does not lead to a logical contradiction. A theory T is consistent if there is no formula \varphi such that both \varphi and its negation \lnot\varphi are elements of the set of consequences ...
, this weaker form can be seen as a
corollary
In mathematics and logic, a corollary ( , ) is a theorem of less importance which can be readily deduced from a previous, more notable statement. A corollary could, for instance, be a proposition which is incidentally proved while proving another ...
of the strong form. It is important to observe that the statement of the standard form of Gödel's First Incompleteness Theorem is completely unconcerned with the truth value of a statement, but only concerns the issue of whether it is possible to find it through a
mathematical proof
A mathematical proof is a deductive reasoning, deductive Argument-deduction-proof distinctions, argument for a Proposition, mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use othe ...
.
The weaker form of the theorem can be proved from the undecidability of the halting problem as follows. Assume that we have a sound (and hence consistent) and complete effective
axiomatization
In mathematics and logic, an axiomatic system is a set of formal statements (i.e. axioms) used to logically derive other statements such as lemmas or theorems. A proof within an axiom system is a sequence of deductive steps that establishes ...
of all true
first-order logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...
statements about
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s. Then we can build an algorithm that enumerates all these statements. This means that there is an algorithm ''N''(''n'') that, given a natural number ''n'', computes a true first-order logic statement about natural numbers, and that for all true statements, there is at least one ''n'' such that ''N''(''n'') yields that statement. Now suppose we want to decide if the algorithm with representation ''a'' halts on input ''i''. We know that this statement can be expressed with a first-order logic statement, say ''H''(''a'', ''i''). Since the axiomatization is complete it follows that either there is an ''n'' such that ''N''(''n'') = ''H''(''a'', ''i'') or there is an ' such that ''N''(') = ¬ ''H''(''a'', ''i''). So if we
iterate
Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration.
...
over all ''n'' until we either find ''H''(''a'', ''i'') or its negation, we will always halt, and furthermore, the answer it gives us will be true (by soundness). This means that this gives us an algorithm to decide the halting problem. Since we know that there cannot be such an algorithm, it follows that the assumption that there is a sound and complete effective axiomatization of all true first-order logic statements about natural numbers must be false.
Examples of undecidable problems
Undecidable problems can be related to different topics, such as
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
,
abstract machine
In computer science, an abstract machine is a theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is similar to a mathematical function in that it receives inputs and produces outputs based on p ...
s or
topology
Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
. Since there are
uncountably
In mathematics, an uncountable set, informally, is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger tha ...
many undecidable problems,
[There are uncountably many subsets of , only countably many of which can be decided by algorithms. However, also only countably many decision problems can be stated in any language.] any list, even one of
infinite length, is necessarily incomplete.
Examples of undecidable statements
There are two distinct senses of the word "undecidable" in contemporary use. The first of these is the sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified
deductive system
A formal system is an abstract structure and formalization of an axiomatic system used for deducing, using rules of inference, theorems from axioms.
In 1921, David Hilbert proposed to use formal systems as the foundation of knowledge in math ...
. The second sense is used in relation to
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
and applies not to statements but to
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
s, which are countably infinite sets of questions each requiring a yes or no answer. Such a problem is said to be undecidable if there is no
computable function
Computable functions are the basic objects of study in computability theory. Informally, a function is ''computable'' if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precis ...
that correctly answers every question in the problem set. The connection between these two is that if a decision problem is undecidable (in the recursion theoretical sense) then there is no consistent, effective
formal system
A formal system is an abstract structure and formalization of an axiomatic system used for deducing, using rules of inference, theorems from axioms.
In 1921, David Hilbert proposed to use formal systems as the foundation of knowledge in ma ...
which proves for every question ''A'' in the problem either "the answer to ''A'' is yes" or "the answer to ''A'' is no".
Because of the two meanings of the word undecidable, the term
independent
Independent or Independents may refer to:
Arts, entertainment, and media Artist groups
* Independents (artist group), a group of modernist painters based in Pennsylvania, United States
* Independentes (English: Independents), a Portuguese artist ...
is sometimes used instead of undecidable for the "neither provable nor refutable" sense. The usage of "independent" is also ambiguous, however. It can mean just "not provable", leaving open whether an independent statement might be refuted.
Undecidability of a statement in a particular deductive system does not, in and of itself, address the question of whether the
truth value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false''). Truth values are used in ...
of the statement is well-defined, or whether it can be determined by other means. Undecidability only implies that the particular deductive system being considered does not prove the truth or falsity of the statement. Whether there exist so-called "absolutely undecidable" statements, whose truth value can never be known or is ill-specified, is a controversial point among various
philosophical schools.
One of the first problems suspected to be undecidable, in the second sense of the term, was the
word problem for groups
A word is a basic element of language that carries meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consensus among linguists on its ...
, first posed by
Max Dehn
Max Wilhelm Dehn (November 13, 1878 – June 27, 1952) was a German mathematician most famous for his work in geometry, topology and geometric group theory. Dehn's early life and career took place in Germany. However, he was forced to retire in 1 ...
in 1911, which asks if there is a finitely presented
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
for which no algorithm exists to determine whether two words are equivalent. This was shown to be the case in 1955.
The combined work of Gödel and
Paul Cohen
Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an American mathematician, best known for his proofs that the continuum hypothesis and the axiom of choice are independent from Zermelo–Fraenkel set theory, for which he was awarded a F ...
has given two concrete examples of undecidable statements (in the first sense of the term): The
continuum hypothesis
In mathematics, specifically set theory, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states:
Or equivalently:
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this ...
can neither be proved nor refuted in
ZFC (the standard axiomatization of
set theory
Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...
), and the
axiom of choice
In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
can neither be proved nor refuted in
ZF (which is all the ZFC axioms ''except'' the axiom of choice). These results do not require the incompleteness theorem. Gödel proved in 1940 that neither of these statements could be disproved in ZF or ZFC set theory. In the 1960s, Cohen proved that neither is provable from ZF, and the continuum hypothesis cannot be proven from ZFC.
In 1970, Russian mathematician
Yuri Matiyasevich
Yuri Vladimirovich Matiyasevich (; born 2 March 1947 in Leningrad
Saint Petersburg, formerly known as Petrograd and later Leningrad, is the List of cities and towns in Russia by population, second-largest city in Russia after Moscow. It is ...
showed that
Hilbert's Tenth Problem
Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm that, for any given Diophantine equation (a polynomial equatio ...
, posed in 1900 as a challenge to the next century of mathematicians, cannot be solved. Hilbert's challenge sought an algorithm which finds all solutions of a
Diophantine equation ''Diophantine'' means pertaining to the ancient Greek mathematician Diophantus. A number of concepts bear this name:
*Diophantine approximation
In number theory, the study of Diophantine approximation deals with the approximation of real n ...
. A Diophantine equation is a more general case of
Fermat's Last Theorem
In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive number, positive integers , , and satisfy the equation for any integer value of greater than . The cases ...
; we seek the
integer roots of a
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
in any number of variables with integer coefficients. Since we have only one equation but ''n'' variables, infinitely many solutions exist (and are easy to find) in the
complex plane
In mathematics, the complex plane is the plane (geometry), plane formed by the complex numbers, with a Cartesian coordinate system such that the horizontal -axis, called the real axis, is formed by the real numbers, and the vertical -axis, call ...
; however, the problem becomes impossible if solutions are constrained to integer values only. Matiyasevich showed this problem to be unsolvable by mapping a Diophantine equation to a
recursively enumerable set
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
and invoking Gödel's Incompleteness Theorem.
In 1936,
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher and theoretical biologist. He was highly influential in the development of theoretical computer ...
proved that the
halting problem
In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...
—the question of whether or not a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
halts on a given program—is undecidable, in the second sense of the term. This result was later generalized by
Rice's theorem
In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable problem, undecidable. A ''semantic'' property is one about the program's behavior (for instance, "does the program halting problem, ...
.
In 1973,
Saharon Shelah
Saharon Shelah (; , ; born July 3, 1945) is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey.
Biography
Shelah was born in Jerusalem on July 3, 1945. He is th ...
showed the
Whitehead problem
In group theory, a branch of abstract algebra, the Whitehead problem is the following question:
Saharon Shelah proved that Whitehead's problem is independent of ZFC, the standard axioms of set theory.
Refinement
Assume that ''A'' is an a ...
in
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ( ...
is undecidable, in the first sense of the term, in standard set theory.
In 1977, Paris and Harrington proved that the
Paris-Harrington principle, a version of the
Ramsey theorem, is undecidable in the axiomatization of arithmetic given by the
Peano axioms
In mathematical logic, the Peano axioms (, ), also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nea ...
but can be proven to be true in the larger system of
second-order arithmetic
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation of mathematics, foundation for much, but not all, ...
.
Kruskal's tree theorem, which has applications in computer science, is also undecidable from the Peano axioms but provable in set theory. In fact Kruskal's tree theorem (or its finite form) is undecidable in a much stronger system codifying the principles acceptable on basis of a philosophy of mathematics called predicativism.
Goodstein's theorem
In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence (as defined below) eventually terminates at 0. Laurence Kirby and Jeff Paris showed ...
is a statement about the
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in R ...
of the natural numbers that Kirby and Paris showed is undecidable in Peano arithmetic.
Gregory Chaitin
Gregory John Chaitin ( ; born 25 June 1947) is an Argentina, Argentine-United States, American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, ...
produced undecidable statements in
algorithmic information theory and proved another incompleteness theorem in that setting. Chaitin's theorem states that for any theory that can represent enough arithmetic, there is an upper bound ''c'' such that no specific number can be proven in that theory to have
Kolmogorov complexity
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that prod ...
greater than ''c''. While Gödel's theorem is related to the
liar paradox
In philosophy and logic, the classical liar paradox or liar's paradox or antinomy of the liar is the statement of a liar that they are lying: for instance, declaring that "I am lying". If the liar is indeed lying, then the liar is telling the trut ...
, Chaitin's result is related to
Berry's paradox
The Berry paradox is a self-referential paradox arising from an expression like "The smallest positive integer not definable in under sixty letters" (a phrase with fifty-seven letters).
Bertrand Russell, the first to discuss the paradox in print, ...
.
In 2007, researchers Kurtz and Simon, building on earlier work by
J.H. Conway in the 1970s, proved that a natural generalization of the
Collatz problem is undecidable.
In 2019, Ben-David and colleagues constructed an example of a learning model (named EMX), and showed a family of functions whose learnability in EMX is undecidable in standard set theory.
See also
*
Decidability (logic)
In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Zeroth-order logic (propositional logic) is decidable, whereas first-order and higher-order logic are not. Logical systems ...
*
Entscheidungsproblem
In mathematics and computer science, the ; ) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. It asks for an algorithm that considers an inputted statement and answers "yes" or "no" according to whether it is universally valid ...
*
Proof of impossibility
In mathematics, an impossibility theorem is a theorem that demonstrates a problem or general set of problems cannot be solved. These are also known as proofs of impossibility, negative proofs, or negative results. Impossibility theorems often reso ...
*
Unknowability
In philosophy, unknowability is the possibility of inherently unaccessible knowledge. It addresses the epistemology of that which cannot be known. Some related concepts include the limits of knowledge, ''ignorabimus'', unknown unknowns, the hal ...
*
Wicked problem
In planning and policy, a wicked problem is a problem that is difficult or impossible to solve because of incomplete, contradictory, and changing requirements that are often difficult to recognize. It refers to an idea or problem that cannot be fix ...
Notes
References
{{Mathematical logic
Computability theory
Logic in computer science