In computability theory

Computability theory

Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...

, an undecidable problem

Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....

consists of a family of instances for which a particular yes/no answer is required, such that there is no computer program that, given any problem instance as input, terminates and outputs the required answer after a finite number of steps. More formally, an undecidable problem
is a problem whose language is not a recursive set

Recursive set

In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....

; see decidability

Decidability (logic)

In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...

. There are uncountably

Uncountable set

In mathematics, an uncountable set is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers.-Characterizations:There...

 many undecidable problems, so the list below is necessarily incomplete. Though undecidable languages are not recursive languages, they may be subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of Turing

Alan Turing

Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...

 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

Word problem (mathematics)

In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements is the algorithmic problem of deciding whether two given representatives represent the same element of the set...

: determining when two distinct strings of symbols (encoding some mathematical concept or object) represent the same object or not.

Problems in logic

Logic

In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

• Hilbert's Entscheidungsproblem
  Entscheidungsproblem
  In mathematics, the is a challenge posed by David Hilbert in 1928. The asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either "True" or "False" according to whether the statement is true or false...
  
  .
• Type inference
  Type inference
  Type inference refers to the automatic deduction of the type of an expression in a programming language. If some, but not all, type annotations are already present it is referred to as type reconstruction....
  
   and type checking for the second-order lambda calculus
  Lambda calculus
  In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
  
   (or equivalent).

Problems about abstract machine

Abstract machine

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...

s

• The halting problem
  Halting problem
  In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
  
   (determining whether a Turing machine
  Turing machine
  A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
  
   halts).
• 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).
• The mortality problem
  Mortality (computability theory)
  In computability theory, the mortality problem is a decision problem which can be stated as follows:In the statement above, the configuration is a pair , where q is one of the machine's states and w is an infinite sequence of symbols representing the initial content of the tape...
  
  .
• Rice's theorem
  Rice's theorem
  In computability theory, Rice's theorem states that, for any non-trivial property of partial functions, there is no general and effective method to decide whether an algorithm computes a partial function with that property...
  
   states that for all nontrivial properties of partial functions, it is undecidable whether a machine computes a partial function with that property.

Problems about matrices

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

• 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. (This is known undecidable for a set of 7 or more 3 × 3 matrices, or a set of two 21 × 21 matrices.)
• Determining whether a finite set of upper triangular 3 × 3 matrices with nonnegative integer entries generates a free semigroup
  Semigroup
  In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
  
  .
• Determining whether two finitely generated subsemigroups of M_n(Z) have a common element.

Problems in combinatorial group theory

Combinatorial group theory

In mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group by generators and relations...

• The word problem for groups
  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 element...
  
  .
• The conjugacy problem
  Conjugacy problem
  In abstract algebra, the conjugacy problem for a group G with a given presentation is the decision problem of determining, given two words x and y in G, whether or not they represent conjugate elements of G...
  
  .
• The group isomorphism problem
  Group isomorphism problem
  In abstract algebra, the group isomorphism problem is the decision problem of determining whether two group presentations present isomorphic groups....
  
  .

Problems in topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

• Determining whether two finite simplicial complex
  Simplicial complex
  In mathematics, a simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts...
  
  es are homeomorphic.
• Determining whether a finite simplicial complex
  Simplicial complex
  In mathematics, a simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts...
  
   is (homeomorphic to) a manifold
  Manifold
  In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....
  
  .
• Determining whether the fundamental group
  Fundamental group
  In mathematics, more specifically algebraic topology, the fundamental group is a group associated to any given pointed topological space that provides a way of determining when two paths, starting and ending at a fixed base point, can be continuously deformed into each other...
  
   of a finite simplicial complex is trivial.

Problems in analysis

• For functions in certain classes, the problem of determining: whether two functions are equal; the zeroes of a function; whether the indefinite integral of a function is also in the class. For examples, see references in Stallworth and Roush, below. (These problems are not always undecidable. It depends on the class. 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
  Risch algorithm
  The Risch algorithm, named after Robert Henry Risch, is an algorithm for the calculus operation of indefinite integration . The algorithm transforms the problem of integration into a problem in algebra. It is based on the form of the function being integrated and on methods for integrating rational...
  
  .)

• "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." Its decidability would contradict the solution to Hilbert's tenth problem
  Hilbert's tenth problem
  Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows:Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite...
  
  .

Other problems

• The Post correspondence problem
  Post correspondence problem
  The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability....
  
  .
• The word problem
  Word problem (mathematics)
  In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements is the algorithmic problem of deciding whether two given representatives represent the same element of the set...
  
   in algebra and computer science.
• The word problem for certain formal languages.
• The problem of determining if a given set of Wang tile
  Wang tile
  Wang tiles , first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems...
  
  s can tile the plane.
• The problem whether a Tag system
  Tag system
  A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine —briefly, a finite state machine whose only tape is a FIFO queue of unbounded length,...
  
   halts.
• The problem of determining the Kolmogorov complexity
  Kolmogorov complexity
  In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...
  
   of a string.
• Hilbert's tenth problem
  Hilbert's tenth problem
  Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows:Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite...
  
  : the problem of deciding whether a Diophantine equation (multivariable polynomial equation) has a solution in integers.
• Determining if a context-free grammar
  Context-free grammar
  In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
  
   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.
• 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 formula has a normal form

External links

• Discussion at MathOverflow