Definition
Decidable Predicate
A predicate
on is decidable if its indicator function is effectively computable. Here,
is an input tuple. The procedure must halt on every input , returning when holds and otherwise; thus is a total computable function.