Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
List of undecidable problems
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==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>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)