decidabel

Decidabel is an adjective used in some languages to describe problems, questions, or sets for which a decision procedure exists. In this sense, a problem is decidable if there is an algorithm that, for every possible input instance, halts with a correct yes or no answer.

In formal terms, a language is decidable if a Turing machine can be constructed that accepts exactly the strings belonging to the language and rejects all other strings, doing so after a finite number of steps for every input. Such a machine is called a decider. Decidable languages are also described as recursive. Decidability is a foundational concept in computability theory and formal logic.

Decidability is distinct from decidability in a broader sense, such as semi-decidability: a problem is recursively enumerable (r.e.) if a machine can list all yes-instances, but may not halt on no-instances. A problem is decidable if and only if it is both recursively enumerable and co-recursively enumerable (its complement is also r.e.). Classic undecidable problems include the Halting Problem and Hilbert’s tenth problem, while many common computational tasks are decidable, such as membership in regular languages, context-free languages, and arithmetic primality testing.

Relation to complexity: decidability concerns only whether an algorithm exists, not how efficient it is. Among decidable problems, complexity theory studies resource usage, leading to classes like P and NP. In practice, determining decidability guides the feasibility of automatic verification, program analysis, and formal reasoning.

Historical note: the concept emerged in the 1930s from the work of Turing, Church, and others, forming a core part of the theory of computation.