Computability problem/exercice -- can't solve

44 Views Asked by At

I'm really blocked in the first part of the below exercise and can't solve it. It would be great if you could help!

Show that there exists a partial recursive function $g:\mathbb{N}\to \mathbb{N}$ such that : $$W_i \neq \emptyset \implies g(i) \in W_i$$ Moreover, show that there exists a total recursive function $\gamma$ such that : $$ W_{\gamma(i)}\subset W_i \text{ and } (W_i \neq \emptyset \implies card(W_{\gamma(i)}) = 1) $$ Then, show that given a partial recursive function $f:\mathbb{N}\to \mathbb{N}$ then there exists a total function $a$ such that : $$ f(x) \downarrow \implies W_{a(x)} = \bigcup_{i \leq f(x)} W_{\gamma(i)}$$

N.B. $f(x) \downarrow$ translates to $f$ is defined on $x$, and $W_i$ is the definitional domain of the universal function $\phi_i$.