Editing List of undecidable problems

{{Short description|Computational problems no algorithm can solve}}
In [[computability theory]], an '''[[undecidable problem]]''' is a [[decision problem]] for which an [[effective method]] (algorithm) to derive the correct answer does not exist. More formally, an undecidable problem is a problem whose language is not a [[recursive set]]; see the article [[Decidable language]]. There are [[uncountable set|uncountably]] many undecidable problems, so the list below is necessarily incomplete. Though undecidable languages are not recursive languages, they may be [[subset]]s of [[Alan Turing|Turing]] recognizable languages: i.e., such undecidable languages may be recursively enumerable.

Many, if not most, undecidable problems in mathematics can be posed as [[word problem (mathematics)|word problems]]: determining when two distinct strings of symbols (encoding some mathematical concept or object) represent the same object or not.

For undecidability in axiomatic mathematics, see [[List of statements undecidable in ZFC]].

==Problems in logic==
* Hilbert's [[Entscheidungsproblem]].
* [[Type inference]] and [[type checking]] for the [[second-order lambda calculus]] (or equivalent).<ref>{{cite journal | first = J. B. | last = Wells | title = Typability and type checking in the second-order lambda-calculus are equivalent and undecidable | citeseerx = 10.1.1.31.3590 | journal = Tech. Rep. 93-011 | publisher = Comput. Sci. Dept., Boston Univ. | year = 1993 | pages = 176–185 }}</ref>
* Determining whether a first-order sentence in the [[logic of graphs]] can be realized by a finite undirected graph.<ref>{{cite journal | last = Trahtenbrot | first = B. A. | author-link = Boris Trakhtenbrot | journal = Doklady Akademii Nauk SSSR |series=New Series | mr = 0033784 | pages = 569–572 | title = The impossibility of an algorithm for the decision problem for finite domains | volume = 70 | year = 1950}}</ref>
* [[Trakhtenbrot's theorem]] - Finite satisfiability is undecidable.
* Satisfiability of first order [[Horn clause]]s.

==Problems about abstract machines==
* The [[halting problem]] (determining whether a [[Turing machine]] halts on a given input) and the [[mortality (computability theory)|mortality problem]] (determining whether it halts for every starting configuration).
* Determining whether a Turing machine is a [[Busy beaver#Non-computability|busy beaver champion]] (i.e., is the longest-running among halting Turing machines with the same number of states and symbols).
* [[Rice's theorem]] states that for all nontrivial properties of partial functions, it is undecidable whether a given machine computes a partial function with that property.
* The halting problem for a [[register machine]]: a finite-state automaton with no inputs and two counters that can be incremented, decremented, and tested for zero.
* Universality of a nondeterministic [[pushdown automaton]]: determining whether all words are accepted.
* The problem whether a [[tag system]] halts.

==Problems about matrices==
* The [[mortal matrix problem]].
* Determining whether a finite set of upper triangular 3 × 3 matrices with nonnegative integer entries generates a free [[semigroup]].{{citation needed|date=April 2024}}
* Determining whether two finitely generated subsemigroups of [[integer matrices]] have a common element.<ref>{{cite journal |last1=Halava |first1= Vesa |last2=Harju|first2=Tero|title=On Markov's Undecidability Theorem for Integer Matrices |journal=Semigroup Forum |volume=75 |issue=1 |date=September 2007 |pages= 173–180 |doi=10.1007/s00233-007-0714-x |url=https://link.springer.com/content/pdf/10.1007/s00233-007-0714-x.pdf}}</ref>

==Problems in combinatorial group theory==
* The [[word problem for groups]].
* The [[conjugacy problem]].
* The [[group isomorphism problem]].

==Problems in topology==
{{Main|Simplicial complex recognition problem}}
* Determining whether two finite [[simplicial complex]]es are [[homeomorphic]].
* Determining whether a finite [[simplicial complex]] is (homeomorphic to) a [[manifold]].
* Determining whether the [[fundamental group]] of a finite simplicial complex is trivial.
* Determining whether two non-[[simply connected]] [[5-manifold]]s are homeomorphic, or if a 5-manifold is homeomorphic to '''S'''<sup>5</sup>.<ref>{{citation|title=Classical Topology and Combinatorial Group Theory|volume=72|series=Graduate Texts in Mathematics|first=John|last=Stillwell|authorlink=John Stillwell|publisher=Springer|year=1993|isbn=9780387979700|page=247|url=https://books.google.com/books?id=265lbM42REMC&pg=PA247}}.</ref>

==Problems in analysis==
* For functions in certain classes, the problem of determining: whether two functions are equal, known as the zero-equivalence problem (see [[Richardson's theorem]]);<ref>Keith O. Geddes, Stephen R. Czapor, George Labahn, ''Algorithms for Computer Algebra'', {{isbn|0585332479}}, 2007, p. 81ff</ref> the zeroes of a function; whether the indefinite integral of a function is also in the class.<ref name="stall"/> Of course, some subclasses of these problems are decidable. For example, there is an effective decision procedure for the elementary integration of any function which belongs to a field of transcendental elementary functions, the [[Risch algorithm]].
* "The problem of deciding whether the definite contour multiple integral of an elementary meromorphic function is zero over an everywhere real analytic manifold on which it is analytic", a consequence of the [[Matiyasevich's theorem|MRDP theorem]] resolving [[Hilbert's tenth problem]].<ref name="stall">{{cite journal
| last1=Stallworth | first1=Daniel T.
| last2=Roush | first2=Fred W.
| title=An Undecidable Property of Definite Integrals
| journal=[[Proceedings of the American Mathematical Society]]
| volume=125
| issue=7
| date=July 1997
| pages=2147–2148
| doi=10.1090/S0002-9939-97-03822-7 | doi-access=free}}</ref>
* Determining the domain of a solution to an [[ordinary differential equation]] of the form
::<math>\frac{dx}{dt} = p(t, x),~x(t_0)=x_0,</math>
:where ''x'' is a [[vector (mathematics and physics)|vector]] in '''R'''<sup>n</sup>, ''p''(''t'', ''x'') is a vector of [[polynomial]]s in ''t'' and ''x'', and ''(t<sub>0</sub>, x<sub>0</sub>)'' belongs to '''R'''<sup>n+1</sup>.<ref>{{cite journal|last1=Graça|first1=Daniel S.|last2=Buescu|first2=Jorge|last3=Campagnolo|first3=Manuel L.|date=21 March 2008|title=Boundedness of the Domain of Definition is Undecidable for Polynomial ODEs|journal=Electronic Notes in Theoretical Computer Science|volume=202|pages=49–57|doi=10.1016/j.entcs.2008.03.007|doi-access=free|hdl=10400.1/1016|hdl-access=free}}</ref>

==Problems about formal languages and grammars==
* The [[Post correspondence problem]].
* Determining if a [[context-free grammar]] generates all possible strings, or if it is [[ambiguous grammar|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.

==Other problems==
* The problem of determining if a given set of [[Wang tile]]s can tile the plane.
* The problem of determining the [[Kolmogorov complexity]] of a string.
* [[Hilbert's tenth problem]]: the problem of deciding whether a Diophantine equation (multivariable polynomial equation) has a solution in integers.
* Determining whether a given initial point with rational coordinates is periodic, or whether it lies in the basin of attraction of a given open set, in a piecewise-linear iterated map in two dimensions, or in a piecewise-linear flow in three dimensions.<ref>{{citation|title=Unpredictability and undecidability in dynamical systems|url=http://www.seas.gwu.edu/~simhaweb/iisc/Moore.pdf|first=Cristopher|last=Moore|author-link=Cristopher Moore|journal=[[Physical Review Letters]]|volume=64|issue=20|year=1990|pages=2354–2357|doi=10.1103/PhysRevLett.64.2354|pmid=10041691|bibcode=1990PhRvL..64.2354M}}.</ref>
* Determining whether a [[Lambda calculus#Undecidability of equivalence|λ-calculus]] formula has a normal form.
* [[Conway's Game of Life#Undecidability|Conway's Game of Life]] on whether, given an initial pattern and another pattern, the latter pattern can ever appear from the initial one.
* [[Rule 110]] - most questions involving "can property X appear later" are undecidable.
* The problem of determining whether a quantum mechanical system has a [[spectral gap (physics)|spectral gap]].<ref>{{Cite journal | doi=10.1038/nature16059|pmid = 26659181| title=Undecidability of the spectral gap| journal=Nature| volume=528| issue=7581| pages=207–211| year=2015| last1=Cubitt| first1=Toby S.| last2=Perez-Garcia| first2=David| last3=Wolf| first3=Michael M.|bibcode = 2015Natur.528..207C|arxiv = 1502.04135|s2cid = 4451987}}</ref><ref>{{cite journal |last1=Bausch |first1=Johannes |last2=Cubitt |first2=Toby S. |last3=Lucia |first3=Angelo |last4=Perez-Garcia |first4=David |title=Undecidability of the Spectral Gap in One Dimension |journal=[[Physical Review X]] |date=17 August 2020 |volume=10 |issue=3 |pages=031038 |doi=10.1103/PhysRevX.10.031038 |bibcode=2020PhRvX..10c1038B |doi-access=free |arxiv=1810.01858 }}</ref>
* Finding the capacity of an information-stable finite state machine channel.<ref name="elkouss_fsmc">{{cite journal|last1=Elkouss|first1=D.|title=Memory effects can make the transmission capability of a communication channel uncomputable|last2=Pérez-García|first2=D.|journal=Nature Communications|date=2018|volume=9|issue=1|page=1149|doi=10.1038/s41467-018-03428-0|pmid=29559615 |pmc=5861076 |bibcode=2018NatCo...9.1149E }}</ref>
* In [[network coding]], determining whether a network is solvable.<ref name="li_nc">{{cite journal|last1=Li|first1=C. T.|title=Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication|journal=IEEE Transactions on Information Theory|date=2023|volume=69 |issue=6 |page=1 |doi=10.1109/TIT.2023.3247570|arxiv=2205.11461 |s2cid=248986512 }}</ref><ref name="kuhne_matroid">{{cite journal|last1=Kühne|first1=L.|title=Representability of Matroids by c-Arrangements is Undecidable|last2=Yashfe|first2=G.|journal=[[Israel Journal of Mathematics]]|date=2022|volume=252 |page=1-53|doi=10.1007/s11856-022-2345-z|arxiv=1912.06123 |s2cid=209324252 }}</ref>
* Determining whether a player has a winning strategy in a game of ''[[Magic: The Gathering]]''.<ref>{{Cite arXiv|last1=Herrick|first1=Austin|last2=Biderman|first2=Stella|last3=Churchill|first3=Alex|date=2019-03-24|title=Magic: The Gathering is Turing Complete|class=cs.AI |eprint=1904.09828v2|language=en}}</ref>
* Planning in a [[partially observable Markov decision process]].
* The problem of planning [[air travel]] from one destination to another, when [[fare]]s are taken into account.<ref>{{cite web |last1=de Marcken |first1=Carl |title=Computational Complexity of Air Travel Planning |url=http://www.demarcken.org/carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf |publisher=[[ITA Software]] |access-date=4 January 2021}}</ref>
* In the [[ray tracing (graphics)|ray tracing]] problem for a 3-dimensional system of reflective or refractive objects, determining if a ray beginning at a given position and direction eventually reaches a certain point.<ref>{{cite web |title=Computability and Complexity of Ray Tracing |url=https://www.cs.duke.edu/~reif/paper/tygar/raytracing.pdf |website=CS.Duke.edu }}</ref>
* Determining if a particle path of an ideal fluid on a three dimensional domain eventually reaches a certain region in space.<ref>{{cite journal|last1=Cardona|first1=R.|title=Constructing Turing complete Euler flows in dimension 3|last2=Miranda|first2=E.|last3=Peralta-Salas|first3=D.|last4=Presas|first4=F.|journal=Proceedings of the National Academy of Sciences|date=2021|volume=118 |issue=19 |page=19|doi=10.1073/pnas.2026818118|doi-access=free |pmid=33947820 |pmc=8126859|arxiv=2012.12828 |bibcode=2021PNAS..11826818C }}</ref><ref>{{cite journal|last1=Cardona|first1=R.|title=Computability and Beltrami fields in Euclidean space|last2=Miranda|first2=E.|last3=Peralta-Salas|first3=D.|journal=Journal de Mathématiques Pures et Appliquées|date=2023|volume=169 |page=50-81|doi=10.1016/j.matpur.2022.11.007|arxiv=2111.03559}}</ref>

==See also==
* [[Lists of problems]]
* [[List of unsolved problems]]
* [[Reduction (complexity)]]
* [[Unknowability]]

==Notes==
{{reflist}}

==Bibliography==
* {{cite book | last = Brookshear | first = J. Glenn | title = Theory of Computation: Formal Languages, Automata, and Complexity | year = 1989 | publisher = Benjamin/Cummings Publishing Company, Inc. | location = Redwood City, California}} Appendix C includes impossibility of algorithms deciding if a grammar contains ambiguities, and impossibility of verifying program correctness by an algorithm as example of Halting Problem.
* {{cite report | last = Halava | first = Vesa | title = Decidable and undecidable problems in matrix theory | year = 1997 | type = TUCS technical report | volume = 127 | publisher = Turku Centre for Computer Science | citeseerx = 10.1.1.31.5792 }}
* {{cite book | last = Moret | first = B. M. E. | title = Algorithms from P to NP, volume 1 - Design and Efficiency | year = 1991 | publisher = Benjamin/Cummings Publishing Company, Inc. | location = Redwood City, California |author2=H. D. Shapiro }} Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms."
* {{cite book | last = Weinberger | first = Shmuel | title = Computers, rigidity, and moduli | year = 2005 | publisher = Princeton University Press | location = Princeton, NJ}} Discusses undecidability of the word problem for groups, and of various problems in topology.

==Further reading==
*{{cite arXiv |last=Poonen |first=Bjorn |author-link=Bjorn Poonen |date=2 April 2012 |title=Undecidable problems: a sampler |class=math.LO |eprint=1204.0299 }}

{{DEFAULTSORT:Undecidable Problems}}
[[Category:Mathematics-related lists]]
[[Category:Theory of computation|*]]
[[Category:Computability theory|*]]
[[Category:Undecidable problems| ]]
[[Category:Lists of problems]]