##  [Decidability](/decidability-0) 

 Definition

Property of a decision problem meaning there exists an effective (algorithmic) procedure, in the chosen model of computation, that always halts and correctly answers whether an input belongs to the language.

 

 

 

 

 

 





## Principle

Principle

A problem is decidable if and only if there is a terminating mechanical method that yields a yes/no answer for every instance; decidability is closed under boolean operations when procedures for the components are available.

 

 

 

 

 





## Demonstration

Demonstration

The set of strings accepted by a deterministic finite automaton is decidable because the automaton's transition procedure halts after reading the input and yields acceptance or rejection.

 

 

 

 

## Misapplication

Misapplication

Treating a semi-decision procedure (one that halts only on positive instances) as a full decision procedure, or assuming that because many practical instances are solvable there exists a uniform halting algorithm for all instances.

 

 

 

 

 





## Consequence

Consequence

When a problem is decidable one can build a general-purpose algorithm to classify instances; complements, intersections and unions of decidable languages remain decidable given effective constructions.

 

 

 

 

## Reversal

Reversal

Undecidability: no algorithm exists that always halts and correctly decides membership for every input in the problem's domain.

 

 

 

 

 





## Boundary

Boundary

Applies to decision problems encoded in a precise formal model of computation (typically Turing machines); does not address resource bounds, probabilistic approximations, or semantic independence from axiomatic systems.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Often confused with tractability (polynomial-time decidability) or with syntactic completeness of a theory; decidability refers only to existence of a terminating correct procedure, not its efficiency or proof-theoretic status.

 

 

 

 

 





## Synthesis

Synthesis

Decidability identifies problems for which an effective, halting algorithm exists to decide membership; it separates exact algorithmic solvability from weaker notions like semi-decidability or complexity constraints.