Undecidable problem: Difference between revisions

Content deleted Content added

Inline

Revision as of 17:47, 23 February 2021

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 arbitrary programs eventually halt when run.

Background

A decision problem is any arbitrary yes-or-no question on an infinite set of inputs. Because of this, it is traditional to define the decision problem equivalently as the set of inputs for which the problem returns yes. These inputs can be natural numbers, but also other values of some other kind, such as

natural numbers

. To keep the formal definition simple, it is phrased in terms of subsets of the natural numbers.

Formally, a decision problem is a subset of the natural numbers. The corresponding informal problem is that of deciding whether a given number is in the set. A decision problem A is called decidable or effectively solvable if A is a

recursively enumerable set.^[1]

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.^[2]

Relationship with Gödel's incompleteness theorem

The concepts raised by

consistency, this weaker form can be seen as a corollary 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

.

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

iterate

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 consistent and complete 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

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.^[4] The second sense is used in relation to computability theory and applies not to statements but to decision problems, 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 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

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 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

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

recursively enumerable set and invoking Gödel's Incompleteness Theorem.^[5]

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.

In 1977, Paris and Harrington proved that the

Ramsey theorem, is undecidable in the axiomatization of arithmetic given by the Peano axioms but can be proven to be true in the larger system of second-order arithmetic

.

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.

Berry's paradox

.

In 2007, researchers Kurtz and Simon, building on earlier work by

Collatz problem is undecidable.^[6]

References

^ This means that there exists an algorithm that halts eventually when the answer is yes but may run forever if the answer is no.
ISBN 1-57955-008-8
.

^ There are uncountably many subsets of $\{0,1\}^{*}$ , only countably many of which can be decided by algorithms. However, also only countably many decision problems can be stated in any language.

ISBN 1-57955-008-8
.

Doklady Akademii Nauk SSSR
(in Russian). 191: 279–282.
doi:10.1007/978-3-540-72504-6_49

Retrieved from "https://en.wikipedia.org/w/index.php?title=Undecidable_problem&oldid=1008511559"

[1] This means that there exists an algorithm that halts eventually when the answer is yes but may run forever if the answer is no.

[2] ISBN 1-57955-008-8
.

[3] There are uncountably many subsets of $\{0,1\}^{*}$ , only countably many of which can be decided by algorithms. However, also only countably many decision problems can be stated in any language.

[4] ISBN 1-57955-008-8
.

[5] Doklady Akademii Nauk SSSR
(in Russian). 191: 279–282.

[6] doi:10.1007/978-3-540-72504-6_49

[1]

[2]

[4]

[5]

[6]

@@ Line 27: / Line 27: @@
 {{See also|List of statements independent of ZFC|Independence (mathematical logic)}}
-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]]. The second sense is used in relation to [[computability theory]] and applies not to statements but to [[decision problem]]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]] 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]] which proves for every question ''A'' in the problem either "the answer to ''A'' is yes" or "the answer to ''A'' is no".
+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]].<ref>{{cite book|last=Wolfram|first=Stephen|authorlink=Stephen Wolfram|title=A New Kind of Science|url=https://www.wolframscience.com/nks/|publisher=Wolfram Media, Inc.|year=2002|pages=[https://www.wolframscience.com/nks/notes-12-9--examples-of-unprovable-statements/ 1163]|isbn=1-57955-008-8}}</ref> The second sense is used in relation to [[computability theory]] and applies not to statements but to [[decision problem]]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]] 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]] 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 [[independence (mathematical logic)|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.