Undecidable

Undecidable is a term used in logic and theoretical computer science to describe a decision problem for which no algorithm can determine, for all possible inputs, whether the answer is yes or no. In formal terms, a problem is undecidable if no Turing machine can decide it in a finite amount of time on every input.

Decidable vs undecidable: A problem is decidable if there exists a computable procedure that halts and gives correct answers for all inputs. If such a procedure cannot exist, the problem is undecidable. Some undecidable problems are semi-decidable (recursively enumerable), meaning there is an algorithm that halts with yes on inputs that are true, but may run forever on false inputs. Others may be non-enumerable in both directions.

Classic examples include the Halting problem: given a program and input, determine whether the program halts. The Halting problem is undecidable, and its undecidability established by Alan Turing. The Entscheidungsproblem, the question of whether first-order logic is universally valid, is undecidable by Church and Turing. In mathematics and algebra, problems such as the word problem for general groups or the Post correspondence problem are undecidable.

Foundationally, undecidability arises from reductions from known undecidable problems, and is linked to the Church-Turing thesis. Rice's theorem states that every nontrivial semantic property of partial computable functions is undecidable. Gödel's incompleteness theorem shows limits of formal systems: in any sufficiently strong system, there exist true statements that are unprovable within the system, reflecting a related notion of mathematical undecidability.

In practice, undecidability delimits what algorithms can achieve. Researchers study decidable fragments of problems, use approximations, or rely on heuristics for typical cases. The distinction between decidable and undecidable remains a central concern in theoretical computer science and mathematical logic.