How do you prove that $A = \{ x \in \mathbb{N} | W_{x} = [0..x]\}$ is a productive set through functional reduction?

Question

As the title states, how do you prove that $A$ is productive? With $W_{x}$ I mean the set of points in which the turing machine with index $x$ halts.

The standard approach that I follow is functional reduction: first I construct a partial recursive function $\psi(x,y)$. Then through the s-m-n theorem I build a partial recursive function $\varphi_{g(x)}(y) = \psi(x,y)$ with $g$ total recursive. Then I proceed to show that $\overline{K}$ reduces to the set I'm studying through $g$. The problem is that in this set the condition includes the index of the partial function ($x$) so I don't know how to construct a suitable $\psi$ function. As you can see from the appendix, I can't reach $g$ in $\psi$, so I can't build $g$ to behave like a member of the $A$ set.

How can I overcome this problem?

APPENDIX: example of proof with functional reduction

Let's show that $B = \{ x\in \mathbb{N} | W_x = \emptyset \}$ is productive.

We do this by proving that $\overline{K}$ reduces to $B$, so equivalently we can show that $K$ reduces to $\overline{B} = \{x\in \mathbb{N} | W_x \neq \emptyset \}$. Consider the function: $$ \psi(x,y) = \left\{\begin{array}{lr} 1, & \text{for } x \in K\\ \uparrow, & \text{otherwise} \\ \end{array}\right\} $$

(Notice that $\psi$ is computable since $K \in RE$). We can now build $\varphi_{g(x)}(y) = \psi(x,y)$ with $g$ total recursive (s-m-n theorem). At this point:

$x \in K \implies \forall y\in \mathbb{N}. \varphi_{g(x)}(y) \downarrow \implies W_{g(x)} = \mathbb{N} \implies W_{g(x)} \neq \emptyset\implies g(x) \in \overline{B}$.

$x \notin K \implies \forall y\in \mathbb{N}. \varphi_{g(x)}(y) \uparrow \implies W_{g(x)} = \emptyset\implies g(x) \notin \overline{B}$.

So $K$ reduces to $\overline{B}$ thorugh $g$: $B$ is productive. $\square$

Answer 1

You likely need to exploit the second recursion theorem, which states that for any total recursive function $f$ there is some $n$ such that $\varphi_n = \varphi_{f(n)}$.

Given any $k$, using s-m-n you can first construct $f_k$ as follows, where $\#(\ldots)$ stands for "some index of". $$ f_k(x) = \#\left(y \mapsto \begin{cases} 0 & \mbox{if } y \leq x \\ \varphi_k(k) & \mbox{otherwise} \end{cases} \right) $$

This is recursive total, since it always returns an index (the fact that the index is for a partial function is irrelevant). So, by the second recursion theorem, there must exist $n_k$ for which $\varphi_{n_k} = \varphi_{f(n_k)}$.

By examining the proof of the second recursion theorem, we can also note that $n_k$ is effectively computable from $k$, that is there is a total recursive function $g$ such that $\varphi_{g(k)} = \varphi_{f(g(k))}$.

Let's verify that $g$ m-reduces $\bar K$ to your set $A$.

Assume $k \in \bar K$, and let's prove $g(k) \in A$. The latter means $W_{g(k)} = [0..g(k)]$, which is true because $$ \varphi_{g(k)}(y) = \varphi_{f(g(k))}(y) = \begin{cases} 0 & \mbox{if } y \leq g(k) \\ \varphi_k(k) & \mbox{otherwise} \end{cases} = \begin{cases} 0 & \mbox{if } y \leq g(k) \\ \uparrow & \mbox{otherwise} \end{cases} $$

Now, assume $k \notin \bar K$, and let's prove $g(k) \notin A$. The latter means $W_{g(k)} \neq [0..g(k)]$, which is true because

$$ \varphi_{g(k)}(y) = \varphi_{f(g(k))}(y) = \begin{cases} 0 & \mbox{if } y \leq g(k) \\ \varphi_k(k) & \mbox{otherwise} \end{cases} $$ Since $\varphi_k(k)\downarrow$, we have that $W_{g(k)} = \mathbb N \neq [0..g(k)]$

---

As a thumb rule, when you are defining a recursive function $f=\varphi_i$ and you need to use its own index $i$ in the definition of the function itself, you need the second recursion theorem.

From a more practical point of view, the second recursion theorem allows one to program in a programming language featuring a function getMyOwnCode() : String which returns the whole source code (the index) of the program calling the function.