Undecidable problem
This article needs additional citations for verification. (July 2019) |
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.[1]
Background
A decision problem is a question which, for every input in some infinite set of inputs, answers "yes" or "no".[2]. Those inputs can be numbers (for example, the decision problem "is the input a prime number?") or other values of some other kind, such as strings of a formal language.
The formal representation of a decision problem is a subset of the
A decision problem A is called decidable or effectively solvable if the formalized set of A is a
Example: the halting problem in computability theory
In computability theory, the halting problem is a decision problem 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 proved in 1936 that a general algorithm running on a Turing machine 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
This section needs additional citations for verification. (August 2019) |
The concepts raised by
The weaker form of the theorem can be proved from the undecidability of the halting problem as follows.
Examples of undecidable problems
Undecidable problems can be related to different topics, such as
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
Because of the two meanings of the word undecidable, the term independent 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 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, first posed by Max Dehn in 1911, which asks if there is a finitely presented group for which no algorithm exists to determine whether two words are equivalent. This was shown to be the case in 1952.
The combined work of Gödel and
In 1970, Russian mathematician
In 1936, Alan Turing proved that the halting problem—the question of whether or not a Turing machine halts on a given program—is undecidable, in the second sense of the term. This result was later generalized by Rice's theorem.
In 1973, Saharon Shelah showed the Whitehead problem in group theory is undecidable, in the first sense of the term, in standard set theory.[5]
In 1977, Paris and Harrington proved that the
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 is a statement about the Ramsey theory of the natural numbers that Kirby and Paris showed is undecidable in Peano arithmetic.
In 2007, researchers Kurtz and Simon, building on earlier work by
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.[7][8]
See also
Notes
- ^ This means that there exists an algorithm that halts eventually when the answer is yes but may run forever if the answer is no.
- ^ 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.
References
- ^ "Formal Computational Models and Computability". www.cs.rochester.edu. Retrieved 2022-06-12.
- ^ "decision problem". Oxford Reference. Retrieved 2022-06-12.
- ^ Aaronson, Scott (21 July 2011). "Rosser's Theorem via Turing machines". Shtetl-Optimized. Retrieved 2 November 2022.
- Doklady Akademii Nauk SSSR(in Russian). 191: 279–282.
- S2CID 123351674.
- S2CID 257109887.
- PMID 30617250.