2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks!!! I figured I needed to use that theorem but I couldn't work it. $\endgroup$ – NetHacker Feb 24 at 9:35
  • $\begingroup$ Sorry, I am not really good with this proofs so I've tried to rewrite it in my own terms. If you happen to have time, could you check wether it makes sense? Thank you very much in any case. drive.google.com/open?id=16IDR8rN0yvZNfRZf23mrnczuVjplIxv3 $\endgroup$ – NetHacker Feb 24 at 12:58
  • 1
    $\begingroup$ @NetHacker I gave it only a quick look. I think your $\psi$ definition implicitly uses s-m-n before you mention it, since $e$ is not a constant index, but depends on $x,y$. I also was a bit lost in following the $g$ vs $g'$ vs $s$ discussion in the last part, but again, I only read it quickly. $\endgroup$ – chi Feb 26 at 13:34
  • $\begingroup$ thanks for the tips! I'll discuss this with my professor asap, then! $\endgroup$ – NetHacker Feb 27 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.