HOME

TheInfoList



OR:

In computability theory, an
undecidable problem In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...
is a type of
computational problem In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computational probl ...
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 In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly ...
; see the article
Decidable language In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the ...
. There are
uncountably In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many Element (mathematics), elements to be countable set, countable. The uncountability of a set is closely related to its cardinal number: a se ...
many undecidable problems, so the list below is necessarily incomplete. Though undecidable languages are not recursive languages, they may be subsets of
Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical co ...
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 The mathematical statements discussed below are independent of ZFC (the canonical axiomatic set theory of contemporary mathematics, consisting of the Zermelo–Fraenkel axioms plus the axiom of choice), assuming that ZFC is consistent. A stateme ...
.


Problems in logic

* Hilbert's
Entscheidungsproblem In mathematics and computer science, the ' (, ) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers "Yes" or "No" according to whether the state ...
. * Type inference and
type checking In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progra ...
for the second-order lambda calculus (or equivalent). * Determining whether a first-order sentence in the logic of graphs can be realized by a finite undirected graph. * Trakhtenbrot's theorem - Finite satisfiability is undecidable. * Satisfiability of first order Horn clauses.


Problems about abstract machines

* The
halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...
(determining whether a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
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 In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a synta ...
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 Minsky 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 In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack. Pushdown automata are used in theories about what can be computed by machines. They are more capab ...
: determining whether all words are accepted. * The problem whether a
tag system A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of a Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine (not to be confused with Post–T ...
halts.


Problems about matrices

* The mortal matrix problem: determining, given a finite set of ''n'' × ''n'' matrices with integer entries, whether they can be multiplied in some order, possibly with repetition, to yield the
zero matrix In mathematics, particularly linear algebra, a zero matrix or null matrix is a matrix all of whose entries are zero. It also serves as the additive identity of the additive group of m \times n matrices, and is denoted by the symbol O or 0 followed ...
. This is known to be undecidable for a set of six or more 3 × 3 matrices, or a set of two 15 × 15 matrices. * Determining whether a finite set of upper triangular 3 × 3 matrices with nonnegative integer entries generates a free
semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
. * Determining whether two finitely generated subsemigroups of integer matrices have a common element.


Problems in combinatorial group theory

* The
word problem for groups In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group ''G'' is the algorithmic problem of deciding whether two words in the generators represent the same el ...
. * The conjugacy problem. * The
group isomorphism problem In abstract algebra, the group isomorphism problem is the decision problem of determining whether two given finite group presentations refer to isomorphic groups. The isomorphism problem was formulated by Max Dehn, and together with the word pr ...
.


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


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 In mathematics, Richardson's theorem establishes the undecidability of the equality of real numbers defined by expressions involving integers, , \ln 2, and exponential and sine functions. It was proved in 1968 by mathematician and computer scient ...
); the zeroes of a function; whether the indefinite integral of a function is also in the class. 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 In mathematics, a Diophantine equation is an equation of the form ''P''(''x''1, ..., ''x'j'', ''y''1, ..., ''y'k'') = 0 (usually abbreviated ''P''(', ') = 0) where ''P''(', ') is a polynomial with integer coefficients, where ''x''1, ..., '' ...
resolving Hilbert's tenth problem.Stallworth, Daniel T. and Fred W. Rous
An Undecidable Property of Definite Integrals
''Proceedings of the American Mathematical Society'' Volume 125, Number 7, July 1997, Pages 2147-2148
* Determining the domain of a solution to an
ordinary differential equation In mathematics, an ordinary differential equation (ODE) is a differential equation whose unknown(s) consists of one (or more) function(s) of one variable and involves the derivatives of those functions. The term ''ordinary'' is used in contrast ...
of the form ::\frac = p(t, x),~x(t_0)=x_0, :where ''x'' is a
vector Vector most often refers to: *Euclidean vector, a quantity with a magnitude and a direction *Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism Vector may also refer to: Mathematic ...
in Rn, ''p''(''t'', ''x'') is a vector of
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
s in ''t'' and ''x'', and ''(t0, x0)'' belongs to Rn+1.


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.


Other problems

* The problem of determining if a given set of
Wang tile Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected, an ...
s can tile the plane. * The problem of determining the
Kolmogorov complexity In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produ ...
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. * Determining whether a
λ-calculus Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation tha ...
formula has a normal form. *
Conway's Game of Life The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no furthe ...
on whether given an initial pattern and another pattern, can the latter pattern ever appear from the initial one. *
Rule 110 The Rule 110 cellular automaton (often called simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to Conway's Game of Life. Like Life, Rule 1 ...
- most questions involving can property "X" appear later is undecidable. * The problem of determining whether a quantum mechanical system has a
spectral gap In mathematics, the spectral gap is the difference between the moduli of the two largest eigenvalues of a matrix or operator; alternately, it is sometimes taken as the smallest non-zero eigenvalue. Various theorems relate this difference to othe ...
. * Determining whether a player has a winning strategy in a game of ''
Magic: The Gathering ''Magic: The Gathering'' (colloquially known as ''Magic'' or ''MTG'') is a Tabletop game, tabletop and Digital collectible card game, digital Collectible card game, collectable card game created by Richard Garfield. Released in 1993 by Wizards ...
''. * Planning in a
partially observable Markov decision process A partially observable Markov decision process (POMDP) is a generalization of a Markov decision process (MDP). A POMDP models an agent decision process in which it is assumed that the system dynamics are determined by an MDP, but the agent cannot ...
. * The problem of planning
air travel Air travel is a form of travel in vehicles such as airplanes, jet aircraft, helicopters, hot air balloons, blimps, gliders, hang gliders, parachutes, or anything else that can sustain flight.
from one destination to another, when
fare A fare is the fee paid by a passenger for use of a public transport system: rail, bus, taxi, etc. In the case of air transport, the term airfare is often used. Fare structure is the system set up to determine how much is to be paid by various pa ...
s are taken into account.


See also

* Lists of problems *
List of unsolved problems List of unsolved problems may refer to several notable conjectures or open problems in various academic fields: Natural sciences, engineering and medicine * Unsolved problems in astronomy * Unsolved problems in biology * Unsolved problems in che ...
*
Reduction (complexity) In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A sufficiently efficient reduction from one problem to another may be used to show that the second problem ...


Notes


Bibliography

* 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. * * Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms." * Discusses undecidability of the word problem for groups, and of various problems in topology.


Further reading

*


External links


Discussion
at
MathOverflow MathOverflow is a mathematics question-and-answer (Q&A) website, which serves as an online community of mathematicians. It allows users to ask questions, submit answers, and rate both, all while getting merit points for their activities. It is a ...
{{DEFAULTSORT:Undecidable Problems Mathematics-related lists * * Lists of problems