Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 12I / iii / Solution

A set $A\subseteq \mathbb{W}$ is a Sigma-1 set when it is the domain of a partial computable function: there is a partial computable $f$ such thatEquivalently, $w\in A$ iff $\exists tR(w,t)$ for some computable predicate $R$; one may take $R(w,t)$ to say that the truncated computation function observes a halt within $t$ steps.