I have a pair of exercises I can't solve (tomorrow I'll have a test). I need some kind of solution so I can apply it to other exercises...thanks to all!
In the following $W_n$ means the domain of the function with code $n$.
- Show that : given a recursively enumerable set $A$, there exists a $g$ total recursive such that: $$W_{g(x)} = \begin{cases} \Bbb N,& x\in A\\ \varnothing,& x\notin A. \end{cases}$$
- Given: $$f(0)=n_0 \text{ and } f(n+1) = \varphi_n(n)f(n)$$
Show that $\mathrm{cod}(f)$ is recursive (with explanation)
- Show that there does not exist a total recursive function $f$ such that: $$\text{for every }x, \text{ if } W_x \text{ is a recursive set then } W_{f(x)} = \overline{W_x} \text{ which is the complement of } W_x.$$
I'm a newbie of this community so I'm sorry if I wrote something bad... thanks to all!!
$g(x)$ outputs the program which takes $n$ as input, tests whether $x \in A$ and if so outputs $n$.
$\operatorname{cod}(f)$ is finite hence recursive. There is some $n$ for which $\phi_n(n)$ does not terminate, and hence for all subsequent $N > n$, $f(N)$ does not terminate.
Such an $f$ would allow you to solve the halting problem. To test whether program $n$ terminates on $i$, run $\phi_n(i)$ in parallel with $\phi_{f(n)}(i)$; whichever one terminates tells you whether $i \in W_n$.