In
computability theory, an undecidable problem is a type of
computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is, any possible program would sometimes give the wrong answer or run forever without giving any answer. 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.
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.
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]
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 tiles can tile the plane.
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.[7]
Determining whether a
λ-calculus formula has a normal form.
Conway's Game of Life on whether given an initial pattern and another pattern, can the latter pattern 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.[8][9]
Finding the capacity of an information-stable finite state machine channel.[10]
The problem of planning
air travel from one destination to another, when
fares are taken into account.[14]
In the
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.[15]
Determining if a particle path of an ideal fluid on a three dimensional domain eventually reaches a certain region in space.[16][17]
^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.
CiteSeerX10.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.
MR0033784.
^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.
S2CID248986512.
^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.
CiteSeerX10.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.
In
computability theory, an undecidable problem is a type of
computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is, any possible program would sometimes give the wrong answer or run forever without giving any answer. 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.
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.
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]
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 tiles can tile the plane.
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.[7]
Determining whether a
λ-calculus formula has a normal form.
Conway's Game of Life on whether given an initial pattern and another pattern, can the latter pattern 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.[8][9]
Finding the capacity of an information-stable finite state machine channel.[10]
The problem of planning
air travel from one destination to another, when
fares are taken into account.[14]
In the
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.[15]
Determining if a particle path of an ideal fluid on a three dimensional domain eventually reaches a certain region in space.[16][17]
^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.
CiteSeerX10.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.
MR0033784.
^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.
S2CID248986512.
^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.
CiteSeerX10.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.