Recursively Undecidable

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.

Given the equivalence of computability and recursiveness, this definition may be restated with reference to computable functions instead of recursive functions.

The halting problem was one of the first to be shown recursively undecidable. The formulation of recursive undecidability of the halting problem and many other recursively undecidable problems is based on Gödel numbers. For instance, the problem of deciding for any given x whether the Turing machine whose Gödel number is x is total is recursively undecidable. Hilbert's tenth problem is perhaps the most famous recursively undecidable problem.

Most proofs of recursive undecidability use reduction. They show that recursive decidability of the problem under study would imply recursive decidability of another problem known to be recursively undecidable. As far as direct proofs are concerned, they usually employ the idea of the Cantor diagonal method.

See also

Gödel's First Incompleteness Theorem, Gödel Number, Gödel's Second Incompleteness Theorem, Recursion, Recursive Function, Richardson's Theorem, Undecidable

This entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha


Davis, M. Computability and Unsolvability. New York: Dover 1982.Kleene, S. C. Mathematical Logic. New York: Dover, 2002.Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.

Referenced on Wolfram|Alpha

Recursively Undecidable

Cite this as:

Sakharov, Alex. "Recursively Undecidable." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein.

Subject classifications