Decidability

Decidability is the property of a decision problem having an algorithm that halts with the correct yes-or-no answer on every input.

Decision problem: A problem whose answer for each input is yes or no. Decidability classifies decision problems by whether one algorithm always answers correctly.
Undecidable problem: A decision problem for which no algorithm halts with the correct answer on every input. It is the direct opposite of decidability.
Algorithm: A finite, precisely specified procedure for solving a class of problems. Decidability asks whether an algorithm solves every instance of a decision problem.
Presburger arithmetic: The first-order theory of natural numbers with addition, equality, and order, but without multiplication. Its decidability is a landmark example of a nontrivial logical theory with an algorithmic solution.
Turing machine: An abstract computational model that follows finite instructions over discrete steps. A Turing machine that halts on every input witnesses decidability.
Recognizable language: A formal language whose members can be accepted by a machine that may run forever on nonmembers. Recognition permits nontermination on some inputs, unlike decidability.
Formal language: A set of finite strings over a specified alphabet. Many decision problems are represented as questions about membership in a formal language.
Peano arithmetic: A formal theory describing natural numbers through axioms for arithmetic and induction. Unlike Presburger arithmetic, the set of its theorems is not decidable.
Halting problem: The problem of determining whether a program eventually stops on a given input. Its undecidability shows that no general algorithm decides every computation's termination.
Semi-decidability: The property of a problem having an algorithm that halts with a positive answer on yes-instances but may not halt otherwise. It captures partial algorithmic solvability without guaranteeing an answer on every instance.

Linked from 14 pages