Computable set

A set is computable if an algorithm always halts and correctly decides whether any given object belongs to it. Its characteristic function therefore takes only the values 0 and 1 and is computable.

Characteristic function: A function that maps members of a set to 1 and nonmembers to 0. Computability of this function is equivalent to deciding membership in the set.
Algorithm: A finite, precise procedure for solving a problem or carrying out a computation. A computable set has an algorithm that always returns a membership answer.
Halting set: The set of encoded program-input pairs on which the corresponding program eventually halts. It is recursively enumerable but not computable, despite having a direct membership definition.
Recursive language: A formal language whose membership problem is decidable by an algorithm that halts on every input. A language is a computable set of finite strings.
Turing machine: An abstract machine model that computes by manipulating symbols according to a finite set of rules. A halting Turing machine can decide membership for every input.
Halting problem: The problem of deciding whether an arbitrary program eventually stops on a given input. Its undecidability shows why a membership procedure must halt by design, not merely when it finds a witness.
Complement of a recursively enumerable set: The set of objects not in a recursively enumerable set. A set is computable exactly when both it and its complement are recursively enumerable.
Presburger arithmetic: The first-order theory of natural numbers with addition and order, but without multiplication. Its decidable sentences form a computable set, despite the theory's infinite domain.
Recursive function: A function defined through basic functions and operations such as composition, recursion, and minimization. Computable sets are exactly those whose characteristic functions are recursive.
Recursively enumerable set: A set whose members can be listed by an algorithm, though nonmembers may never be ruled out. Every computable set is recursively enumerable, but some such sets lack a total membership test.

Linked from 3 pages