Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-1/12i/iii/solution

A set is a Sigma-1 set when it is the domain of a partial computable function: there is a partial computable such that
Equivalently, iff for some computable predicate ; one may take to say that the truncated computation function observes a halt within steps.

New to topics? Read the docs here!