I am working through "A Friendly Introduction to Mathematical Logic" by Christopher Leary and Lars Kristiansen, and am currently stuck on this exercise:
Show that A ⊆ N is semi-calculable if and only if there is a Σ-formula φ(x) such that φ defines A.
Here, semi-calculable is defined informally as "there is a computer program P such that if a ∈ A, program P returns 0 on input $a$, and if $a \not \in A$, program P does not halt when given input $a$."
I tried two things so far: first I tried to use the fact that a set is semi-calculable iff it is weakly representable. But having a formula $\psi$ that weakly-represents $A$ doesn't seem to be helpful as we know nothing about it.
I also tried the fact that $A$ is listable, but again, it did not lead anywhere.
Any hint will be highly appreciated!