Undecidable problem: Difference between revisions

Browse history interactively

← Previous edit Next edit →

Content deleted Content added

VisualWikitext

Inline

Revision as of 07:43, 7 February 2008

A undecidable problem is a decision problem that is not decidable.

@@ Line 1: / Line 1: @@
-{{dated prod|concern = Original research|month = February|day = 7|year = 2008|time = 02:13|timestamp = 20080207021321}}
-<!-- Do not use the "dated prod" template directly; the above line is generated by "subst:prod|reason" -->
 A '''[[undecidable]]''' problem is a [[decision problem]] that is not [[decidable]].
-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 [[string (computer science)|string]]s of a [[formal language]]. Using some encoding, such as [[Gödel number]]s, the strings can be encoded as natural numbers.  Thus, a decision problem informally phrased in terms of a formal language is also equivalent to a set of [[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 [[recursive set]].  A problem is called '''partially decidable''', '''semidecidable''', '''solvable''', or '''provable''' if ''A'' is a [[recursively enumerable set]].  Partially decidable problems and any other problems that are not decidable are called '''undecidable'''.
-==The undecidable problem in Computability Theory==
-In [[computability theory (computer science)|computability theory]], the '''halting problem''' is a [[decision problem]] which can be stated as follows:
-:''Given a description of a [[computer program|program]] and a finite input, decide whether the program finishes running or will run forever, given that input.''
-[[Alan Turing]] proved in 1936 that a general [[algorithm]] to solve the halting problem for ''all'' possible program-input pairs cannot exist. We say that the halting problem is ''[[undecidability|undecidable]]'' over [[Turing machine]]s.
-==Relationship with Gödel's incompleteness theorem==
-The [[concept]]s raised by [[Gödel's incompleteness theorem]]s 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 a complete, [[Consistency proof|consistent]] and [[Soundness|sound]] [[axiomatization]] of all statements about natural numbers is unachievable. The "sound" part is the weakening: it means that we require the axiomatic system in question to prove only ''true'' statements about natural numbers (it's very important to observe that the statement of the standard form of Gödel's First Incompleteness Theorem is completely unconcerned with the question of truth, but only concerns the issue of whether it can be [[mathematical proof|proven]]).
-The weaker form of the theorem can be proved from the undecidability of the halting problem as follows. Assume that we have a consistent and complete [[axiomatization]] of all true [[first-order logic]] statements about [[natural number]]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 such that, for all the 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 ''n&#39;'' such that ''N''(''n&#39;'') = ¬ ''H''(''a'', ''i'').  So if we [[iterate]] over all ''n'' until we either find ''H''(''a'', ''i'') or its negation, we will always halt. 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.
-==List of undecidable problems==
-In [[computability theory]], an '''undecidable problem''' is a problem whose language is not a [[recursive set]]. More informally, such problems cannot be solved in general by computers; see [[Decidability (logic)|decidability]]. This is a list of undecidable problems. Note that there are [[uncountable set|uncountably]] many undecidable problems, so this list is necessarily incomplete. Though undecidable languages are not recursive languages, they may be a [[subset]] of [[Alan Turing|Turing]] recognizable languages.
-== Problems related to [[abstract machine]]s ==
-* The [[halting problem]] (determining whether a specified machine halts or runs forever).
-* The [[busy beaver]] problem (determining the length of the longest halting computation among machines of a specified size).
-* [[Rice's theorem]] states that for all non-trivial properties of partial functions, it is undecidable whether a machine computes a partial function with that property.
-== Other problems ==
-* The [[Post correspondence problem]].
-* The [[word problem for groups]].
-* The [[word problem (computability)|word problem]] for certain [[formal languages]].
-* The problem of determining if a given set of [[Wang tile]]s can tile the plane.
-* The problem whether a [[Tag system]] halts.
-* The problem of determining the [[Kolmogorov complexity]] of a string.
-* Determination of the solvability of a Diophantine equation, known as [[Hilbert's tenth problem]]
-* Determining whether two finite [[simplicial complex|simplicial complexes]] are homeomorphic
-* Determining whether the [[fundamental group]] of a finite simplicial complex is trivial
-* Determining if a [[context-free grammar]] generates all possible strings, or if it is ambiguous.
-* Given two context-free grammars, determining whether they generate the same set of strings, or whether one generates a subset of the strings generated by the other, or whether there is any string at all that both generate.
-* [http://en.wikipedia.org/wiki/Semantic_Web#From_Logic_to_Ontology:_The_limit_of_.22The_Semantic_Web.22 From Logic to Ontology: The limit of "The Semantic Web"]
-==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.  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. Some use it to 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 [[philosophy of mathematics|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 (mathematics)|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 [[Paul Cohen (mathematician)|Paul Cohen]] has given two concrete examples of undecidable statements (in the first sense of the term): The [[continuum hypothesis]] can neither be proved nor refuted in [[ZFC]] (the standard axiomatization of [[set theory]]), and the [[axiom of choice]] can neither be proved nor refuted in [[Zermelo-Fraenkel set theory|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, Soviet mathematician [[Yuri Matiyasevich]] showed that [[Hilbert's tenth problem|Hilbert's Tenth Problem]], 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 Equation]].  A [[Diophantine equation|Diophantine Equation]] is a more general case of [[Fermat's Last Theorem]]; we seek the rational roots of a polynomial in any number of variables with integer coefficients.  Since we have only one equation but n- variables, infinite solutions exist (and are easy to find) in the Complex Plane; the problem becomes difficult (impossible) by constraining solutions to rational values only.  [[Yuri Matiyasevich|Matiyasevich]] showed this problem to be unsolvable by mapping a [[Diophantine equation|Diophantine Equation]] to a [[recursively enumerable set]] and invoking Gödel's Incompleteness Theorem.<ref>Enumerable sets are Diophantine, {{cite book |date=1970 |title= Doklady Akademii Nauk SSSR|author=Yuri Matiyasevich|pages=279-82}}</ref>
-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 to [[Rice's theorem]].
-In 1973, the [[Whitehead problem]] in [[group theory]] was shown to be undecidable, in the first sense of the term, in standard set theory.
-In 1977, Paris and Harrington proved that the [[Paris-Harrington theorem|Paris-Harrington principle]], a version of 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.
-[[Gregory Chaitin]] 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]] greater than ''c''. While Gödel's theorem is related to the [[liar paradox]], Chaitin's result is related to [[Berry's paradox]].
-[[Douglas Hofstadter]] gives a notable alternative proof of incompleteness, inspired by Gödel, in his book [[Gödel, Escher, Bach]].