Soare Exercise IV. 4.7

48 Views Asked by At

enter image description here

This is exercise IV. 4.7 from Soare's text. I'm having a bit of a trouble understanding his hint. I don't understand how the sequence $\{ A_{s} \}$ he defined is necessarily recursive, like if $x \not \in A$ then I don't see how there's a gurantee that $t_e$ is computable. Moreover, how is it necesarry that $A_{s} \subseteq A_{s+1}$? How is it necessary that for each $s$, there even is some $t_e$, since there might never be such an $e$?

I think the one of the (possible) problems can be fixed by letting $A_{s+1} = A_{s} \cup W_{i,t}$, which wouldn't change anything if $A_{s} \subseteq A_{s+1}$.