Eldönthetability

Eldönthetability is a term used in logic and computer science to describe the property of a decision problem being decidable. A decision problem asks a yes/no question about inputs, and a problem is eldönthető if there exists an algorithm that terminates with a correct yes or no answer for every possible input instance.

In formal terms, a language is eldönthető if there is a Turing machine that halts on all inputs and accepts exactly the strings in the language. A related distinction is between decidable problems and semi-decidable (recursively enumerable) problems: decidable problems have a machine that halts on every input, while semi-decidable problems may halt only on yes-instances and run forever on no-instances.

Undecidability is shown by proving that no such halting algorithm exists for certain problems, often via reductions from known undecidable problems like the halting problem. Examples illustrate the boundary: the primality test (decidable) and the halting problem (undecidable). Within mathematics and logic, some theories are decidable, such as Presburger arithmetic (addition only), while others are not, such as Peano arithmetic (full arithmetic with addition and multiplication).

History and context: the formal notion of decidability emerged in the 1930s through the work of Alan Turing, Alonzo Church, and others, shaping the foundations of computability theory. Eldönthetability remains a central concept for understanding what can be computed in finite time and what lies beyond algorithmic reach. See also Church–Turing thesis, recursive functions, and decidable theories.