List of undecidable problems

Last updated

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.

Contents

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 about abstract machines

Problems in formal logic and grammars

Problems about matrices

Problems in combinatorial group theory

Problems in topology

Problems in number theory

Problems in analysis

where x is a vector in Rn, p(t, x) is a vector of polynomials in t and x, and (t0, x0) belongs to Rn+1. [9]

Problems in physics

Other problems

See also

Notes

  1. 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 .
  2. 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.
  3. Cassaigne, Julien; Harju, Tero; Karhumäki, Juhani (June 1999). "On the undecidability of freeness of matrix semigroups" . International Journal of Algebra and Computation. 09 (3n04): 295–305. doi:10.1142/S0218196799000199. ISSN   0218-1967.
  4. Halava, Vesa; Harju, Tero (September 2007). "On Markov's Undecidability Theorem for Integer Matrices" (PDF). Semigroup Forum. 75 (1): 173–180. doi:10.1007/s00233-007-0714-x.
  5. Blondel, Vincent D.; Tsitsiklis, John N. (2000-10-09). "The boundedness of all products of a pair of matrices is undecidable" . Systems & Control Letters. 41 (2): 135–140. doi:10.1016/S0167-6911(00)00049-9. ISSN   0167-6911.
  6. Stillwell, John (1993), Classical Topology and Combinatorial Group Theory, Graduate Texts in Mathematics, vol. 72, Springer, p. 247, ISBN   9780387979700 .
  7. Keith O. Geddes, Stephen R. Czapor, George Labahn, Algorithms for Computer Algebra, ISBN   0585332479, 2007, p. 81ff
  8. 1 2 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 .
  9. 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 .
  10. 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.
  11. 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 .
  12. "Computability and Complexity of Ray Tracing" (PDF). CS.Duke.edu.
  13. 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.
  14. 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.
  15. 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 .
  16. 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.
  17. 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.
  18. 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.
  19. Herrick, Austin; Biderman, Stella; Churchill, Alex (2019-03-24). "Magic: The Gathering is Turing Complete". arXiv: 1904.09828v2 [cs.AI].
  20. de Marcken, Carl. "Computational Complexity of Air Travel Planning" (PDF). ITA Software . Retrieved 4 January 2021.

Bibliography

Further reading