PROFILPELAJAR.COM

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 uncountably many undecidable problems, so the list below is necessarily incomplete. Though undecidable languages are not recursive languages, they may be subsets of 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 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).^[1]
Determining whether a first-order sentence in the logic of graphs can be realized by a finite undirected graph.^[2]
Trakhtenbrot's theorem - Finite satisfiability is undecidable.
Satisfiability of first order Horn clauses.

Problems about abstract machines

The halting problem (determining whether a Turing machine halts on a given input) and the mortality problem (determining whether it halts for every starting configuration).
Determining whether a Turing machine is a 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]}
Determining whether two finitely generated subsemigroups of integer matrices have a common element.^{[citation needed]}

Problems in combinatorial group theory

Problems in topology

Determining whether two finite simplicial complexes 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-manifolds are homeomorphic, or if a 5-manifold is homeomorphic to S⁵.^[3]

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);^[4] the zeroes of a function; whether the indefinite integral of a function is also in the class.^[5] 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 MRDP theorem resolving Hilbert's tenth problem.^[5]
Determining the domain of a solution to an ordinary differential equation of the form

{\frac {dx}{dt}}=p(t,x),~x(t_{0})=x_{0},

where x is a vector in Rⁿ, p(t, x) is a vector of polynomials in t and x, and (t₀, x₀) belongs to Rⁿ⁺¹.^[6]

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

Notes

^ Wells, J. B. (1993). "Typability and type checking in the second-order lambda-calculus are equivalent and undecidable". Tech. Rep. 93-011. Comput. Sci. Dept., Boston Univ.: 176–185. CiteSeerX 10.1.1.31.3590.
^ Trahtenbrot, B. A. (1950). "The impossibility of an algorithm for the decision problem for finite domains". Doklady Akademii Nauk SSSR. New Series. 70: 569–572. MR 0033784.
^ Stillwell, John (1993), Classical Topology and Combinatorial Group Theory, Graduate Texts in Mathematics, vol. 72, Springer, p. 247, ISBN 9780387979700.
^ Keith O. Geddes, Stephen R. Czapor, George Labahn, Algorithms for Computer Algebra, ISBN 0585332479, 2007, p. 81ff
^ ^a ^b Stallworth, Daniel T.; Roush, Fred W. (July 1997). "An Undecidable Property of Definite Integrals". Proceedings of the American Mathematical Society. 125 (7): 2147–2148. doi:10.1090/S0002-9939-97-03822-7.
^ Graça, Daniel S.; Buescu, Jorge; Campagnolo, Manuel L. (21 March 2008). "Boundedness of the Domain of Definition is Undecidable for Polynomial ODEs". Electronic Notes in Theoretical Computer Science. 202: 49–57. doi:10.1016/j.entcs.2008.03.007. hdl:10400.1/1016.
^ Moore, Cristopher (1990), "Unpredictability and undecidability in dynamical systems" (PDF), Physical Review Letters, 64 (20): 2354–2357, Bibcode:1990PhRvL..64.2354M, doi:10.1103/PhysRevLett.64.2354, PMID 10041691.
^ Cubitt, Toby S.; Perez-Garcia, David; Wolf, Michael M. (2015). "Undecidability of the spectral gap". Nature. 528 (7581): 207–211. arXiv:1502.04135. Bibcode:2015Natur.528..207C. doi:10.1038/nature16059. PMID 26659181. S2CID 4451987.
^ Bausch, Johannes; Cubitt, Toby S.; Lucia, Angelo; Perez-Garcia, David (17 August 2020). "Undecidability of the Spectral Gap in One Dimension". Physical Review X. 10 (3): 031038. arXiv:1810.01858. Bibcode:2020PhRvX..10c1038B. doi:10.1103/PhysRevX.10.031038.
^ Elkouss, D.; Pérez-García, D. (2018). "Memory effects can make the transmission capability of a communication channel uncomputable". Nature Communications. 9 (1): 1149. Bibcode:2018NatCo...9.1149E. doi:10.1038/s41467-018-03428-0. PMC 5861076. PMID 29559615.
^ Li, C. T. (2023). "Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication". IEEE Transactions on Information Theory. 69 (6): 1. arXiv:2205.11461. doi:10.1109/TIT.2023.3247570. S2CID 248986512.
^ Kühne, L.; Yashfe, G. (2022). "Representability of Matroids by c-Arrangements is Undecidable". Israel Journal of Mathematics. 252: 1-53. arXiv:1912.06123. doi:10.1007/s11856-022-2345-z. S2CID 209324252.
^ Herrick, Austin; Biderman, Stella; Churchill, Alex (2019-03-24). "Magic: The Gathering is Turing Complete". arXiv:1904.09828v2 [cs.AI].
^ de Marcken, Carl. "Computational Complexity of Air Travel Planning" (PDF). ITA Software. Retrieved 4 January 2021.
^ "Computability and Complexity of Ray Tracing" (PDF). CS.Duke.edu.
^ Cardona, R.; Miranda, E.; Peralta-Salas, D.; Presas, F. (2021). "Constructing Turing complete Euler flows in dimension 3". Proceedings of the National Academy of Sciences. 118 (19): 19. arXiv:2012.12828. Bibcode:2021PNAS..11826818C. doi:10.1073/pnas.2026818118. PMC 8126859. PMID 33947820.
^ Cardona, R.; Miranda, E.; Peralta-Salas, D. (2023). "Computability and Beltrami fields in Euclidean space". Journal de Mathématiques Pures et Appliquées. 169: 50-81. arXiv:2111.03559. doi:10.1016/j.matpur.2022.11.007.

Bibliography

Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. 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.
Halava, Vesa (1997). Decidable and undecidable problems in matrix theory (TUCS technical report). Vol. 127. Turku Centre for Computer Science. CiteSeerX 10.1.1.31.5792.
Moret, B. M. E.; H. D. Shapiro (1991). Algorithms from P to NP, volume 1 - Design and Efficiency. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms."
Weinberger, Shmuel (2005). Computers, rigidity, and moduli. Princeton, NJ: Princeton University Press. Discusses undecidability of the word problem for groups, and of various problems in topology.