Undecidable problem
This articleneeds additional citations forverification.(July 2019) |
Incomputability theoryandcomputational complexity theory,anundecidable problemis adecision problemfor which it is proved to be impossible to construct analgorithmthat always leads to a correct yes-or-no answer. Thehalting problemis an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.[1]
Background
[edit]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 asstringsof aformal language.
The formal representation of a decision problem is a subset of thenatural numbers.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 specificGödel numbering,correspond to inputs that satisfy the decision problem's criteria.
A decision problemAis called decidable or effectively solvable if the formalized set ofAis arecursive set.Otherwise,Ais called undecidable. A problem is called partially decidable, semi-decidable, solvable, or provable ifAis arecursively enumerable set.[nb 1]
Example: the halting problem in computability theory
[edit]Incomputability theory,thehalting problemis adecision problemwhich can be stated as follows:
- Given the description of an arbitraryprogramand a finite input, decide whether the program finishes running or will run forever.
Alan Turingproved in 1936 that a generalalgorithmrunning on aTuring machinethat solves the halting problem forallpossible program-input pairs necessarily cannot exist. Hence, the halting problem isundecidablefor Turing machines.
Relationship with Gödel's incompleteness theorem
[edit]This sectionneeds additional citations forverification.(August 2019) |
The concepts raised byGödel's incompleteness theoremsare 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 anaxiomatizationof the natural numbers that is both complete andsoundis impossible. The "sound" part is the weakening: it means that we require the axiomatic system in question to prove onlytruestatements about natural numbers. Since soundness impliesconsistency,this weaker form can be seen as acorollaryof 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 amathematical proof.
The weaker form of the theorem can be proved from the undecidability of the halting problem as follows.[3]Assume that we have a sound (and hence consistent) and completeaxiomatizationof all truefirst-order logicstatements aboutnatural numbers.Then we can build an algorithm that enumerates all these statements. This means that there is an algorithmN(n) that, given a natural numbern,computes a true first-order logic statement about natural numbers, and that for all true statements, there is at least onensuch thatN(n) yields that statement. Now suppose we want to decide if the algorithm with representationahalts on inputi.We know that this statement can be expressed with a first-order logic statement, sayH(a,i). Since the axiomatization is complete it follows that either there is annsuch thatN(n) =H(a,i) or there is ann′such thatN(n′) = ¬H(a,i). So if weiterateover allnuntil we either findH(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
[edit]Undecidable problems can be related to different topics, such aslogic,abstract machinesortopology.Since there areuncountablymany undecidable problems,[nb 2]any list, even one ofinfinite length,is necessarily incomplete.
Examples of undecidable statements
[edit]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 specifieddeductive system.The second sense is used in relation tocomputability theoryand applies not to statements but todecision 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 nocomputable functionthat 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, effectiveformal systemwhich proves for every questionAin the problem either "the answer toAis yes "or" the answer toAis no ".
Because of the two meanings of the word undecidable, the termindependentis 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 thetruth valueof 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 variousphilosophical schools.
One of the first problems suspected to be undecidable, in the second sense of the term, was theword problem for groups,first posed byMax Dehnin 1911, which asks if there is a finitely presentedgroupfor which no algorithm exists to determine whether two words are equivalent. This was shown to be the case in 1955.[4]
The combined work of Gödel andPaul Cohenhas given two concrete examples of undecidable statements (in the first sense of the term): Thecontinuum hypothesiscan neither be proved nor refuted inZFC(the standard axiomatization ofset theory), and theaxiom of choicecan neither be proved nor refuted inZF(which is all the ZFC axiomsexceptthe 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 mathematicianYuri Matiyasevichshowed thatHilbert'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 aDiophantine equation.A Diophantine equation is a more general case ofFermat's Last Theorem;we seek theinteger rootsof apolynomialin any number of variables with integer coefficients. Since we have only one equation butnvariables, infinitely many solutions exist (and are easy to find) in thecomplex plane;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 arecursively enumerable setand invoking Gödel's Incompleteness Theorem.[5]
In 1936,Alan Turingproved that thehalting problem—the question of whether or not aTuring machinehalts on a given program—is undecidable, in the second sense of the term. This result was later generalized byRice's theorem.
In 1973,Saharon Shelahshowed theWhitehead problemingroup theoryis undecidable, in the first sense of the term, in standard set theory.[6]
In 1977, Paris and Harrington proved that theParis-Harrington principle,a version of theRamsey theorem,is undecidable in the axiomatization of arithmetic given by thePeano axiomsbut can be proven to be true in the larger system ofsecond-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 theoremis a statement about theRamsey theoryof the natural numbers that Kirby and Paris showed is undecidable in Peano arithmetic.
Gregory Chaitinproduced undecidable statements inalgorithmic information theoryand proved another incompleteness theorem in that setting. Chaitin's theorem states that for any theory that can represent enough arithmetic, there is an upper boundcsuch that no specific number can be proven in that theory to haveKolmogorov complexitygreater thanc.While Gödel's theorem is related to theliar paradox,Chaitin's result is related toBerry's paradox.
In 2007, researchers Kurtz and Simon, building on earlier work byJ.H. Conwayin the 1970s, proved that a natural generalization of theCollatz problemis undecidable.[7]
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.[8][9]
See also
[edit]Notes
[edit]- ^This means that there exists an algorithm that halts eventually when the answer isyesbut may run forever if the answer isno.
- ^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
[edit]- ^"Formal Computational Models and Computability".cs.rochester.edu.Retrieved2022-06-12.
- ^"decision problem".Oxford Reference.Retrieved2022-06-12.
- ^Aaronson, Scott (21 July 2011)."Rosser's Theorem via Turing machines".Shtetl-Optimized.Retrieved2 November2022.
- ^Novikov, Pyotr S.(1955), "On the algorithmic unsolvability of the word problem in group theory",Proceedings of the Steklov Institute of Mathematics(in Russian),44:1–143,Zbl0068.01301
- ^Matiyasevich, Yuri(1970).Диофантовость перечислимых множеств[Enumerable sets are Diophantine].Doklady Akademii Nauk SSSR(in Russian).191:279–282.
- ^Shelah, Saharon (1974). "Infinite Abelian groups, Whitehead problem and some constructions".Israel Journal of Mathematics.18(3): 243–256.doi:10.1007/BF02757281.MR0357114.S2CID123351674.
- ^Kurtz, Stuart A.; Simon, Janos,"The Undecidability of the Generalized Collatz Problem",in Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007.ISBN3-540-72503-2.doi:10.1007/978-3-540-72504-6_49
- ^Ben-David, Shai; Hrubeš, Pavel; Moran, Shay; Shpilka, Amir; Yehudayoff, Amir (2019-01-07)."Learnability can be undecidable".Nature Machine Intelligence.1(1): 44–48.doi:10.1038/s42256-018-0002-3.ISSN2522-5839.S2CID257109887.
- ^Reyzin, Lev (2019)."Unprovability comes to machine learning".Nature.565(7738): 166–167.Bibcode:2019Natur.565..166R.doi:10.1038/d41586-019-00012-4.ISSN0028-0836.PMID30617250.