6 articles
Chaitin's constant
Chaitin's constant, also called the halting probability or Chaitin's Omega, is a real number introduced by Gregory Chaitin in 1975 whose first n bits solve the halting problem for programs of length n.
Decision problem
Decision problem: yes/no computational task over inputs (Entscheidungsproblem, German for decision problem). Central to computability and complexity theory; halting problem and first-order validity are undecidable (Church, Turing 1936).
Hilbert's tenth problem
Hilbert's tenth problem is the 1900 challenge of finding an algorithm that decides whether any Diophantine equation has integer solutions; Matiyasevich proved in 1970 that none exists.
P versus NP problem
The P versus NP problem asks whether every problem whose solutions can be checked quickly can also be solved quickly, one of the Clay Mathematics Institute's $1 million Millennium Prize Problems.
Undecidable problem
An undecidable problem, also known as an unsolvable or recursively undecidable problem, is a decision problem for which no algorithm always halts with a correct yes-or-no answer, a limit proven by Turing's halting problem.
Word problem (mathematics)
In mathematics, a word problem is either a story-like verbal problem solved by applying operations to given numbers, or a decision problem in algebra and computability theory.