# Tag Info

As cody observed, the problem with that strategy is that definable relations need not be computable. For example, the Halting Problem is definable in $(\mathbb{N}; +,\times)$ (see Kleene's $T$-predicate). That said, a relativized form of the incomputability of the Halting Problem, applied to iterates of the Turing jump, does do the job: First, we show that ...