Let be a predicate. We say that is decidable iff there is a procedure

That produces a proof of or for all .