Determination of whether predicate 
is true or false for any given values of 
,
..., 
is called its decision problem. The decision
problem for predicate 
is called recursively decidable if there is a
total recursive
function 
such that
 |
(1)
|
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 
whether the Turing machine
whose Gödel number is 
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.
