 Computable predicate

A computable predicate is a yes-or-no relation for which an algorithm halts on every input and returns the correct truth value. Equivalently, its indicator function takes values in $\{0,1\}$ and is a total computable function. For predicates of several natural numbers, a fixed effective tuple encoding reduces the inputs to one number if needed.

For example, $R(a,b)$ defined by $a\mid b$ is computable: with a stated convention for $a=0$, integer division or finite arithmetic decides it. The predicate that program $e$ halts on input $x$ within at most $t$ steps is also computable, by bounded simulation.

In contrast, the existence of some halting time, $\exists tR(e,x,t)$, is not a computable predicate in general: it is the halting problem. It is computably enumerable because a successful simulation eventually witnesses it. Thus an unbounded existential quantifier can turn a decidable relation into one whose false instances cannot be recognized by a terminating procedure.