= 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 t\,R(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.
Back to article page
