Ondecideerbaar

Ondecideerbaar, or undecidable, is a term in computability theory used to describe decision problems for which no general algorithm can determine the correct answer for every possible input. More formally, a problem is ondecideerbaar if there exists no Turing machine that halts on all inputs and outputs the correct yes/no answer. If such a machine exists, the problem is decideerbaar (decidable). This distinction highlights the intrinsic limits of algorithmic computation.

Undecidability arises in many core problems within computer science and mathematical logic. The most famous example is the halting problem: given a program and its input, decide whether the program will eventually halt. Turing proved this problem undecidable. Other classic undecidable problems include the Post correspondence problem and Hilbert’s tenth problem, which asks whether a Diophantine equation has an integer solution.

Relation to semi-decidability is an important nuance. Some undecidable problems are semi-decidable (recursively enumerable): there exists an algorithm that will halt and accept when the answer is yes, but may run indefinitely on no-instances. The halting problem is semi-decidable, whereas its complement is not.

In logic, undecidability also appears in theories where there is no algorithm that decides all valid statements. For first-order logic, validity is recursively enumerable (there is an effective procedure to enumerate all valid sentences) but not decidable. Gödel’s incompleteness theorems illustrate fundamental limits on what can be proven within formal systems.

See also: decidable, semi-decidable, Turing machine, reduction, Rice’s theorem.