Determination of whether predicate P(x_1, ..., x_n) is true or false for any given values of x_1, ..., x_n is called its decision problem. The decision problem for predicate P(x_1, ..., x_n) is called recursively decidable if there is a total recursive function f(x_1, ..., x_n) such that f(x_1, ..., x_n) = {1 | if P(x_1, ..., x_n) is true 0 | if P(x_1, ..., x_n) is false. auto right match Given the equivalence of computability and recursiveness, this definition may be restated with reference to computable functions instead of recursive functions.

Gödel number | Gödel's first incompleteness theorem | Gödel's second incompleteness theorem | recursion | recursive function | Richardson's theorem | undecidable