1
$\begingroup$

I am currently working on the reduction method to demonstrate that a set is not recursively enumerable but I am struggling to find suitable functions for the reductions. In particular I have started working on the proving that the EXT set is not r.e.:

$$ EXT=\{x|\phi_x \text{ is extensible to a total recursive function}\} $$

My intuition leads me to try and find a reduction from $\overline{K}$to EXT by defining a function like this: $$ f(x)=\left\{\begin{matrix} \text{extensible function} \quad \text{if } x \epsilon \overline{K} \\ \text{non-extensible function} \quad \text{if } x\epsilon K \end{matrix}\right. $$

by using an already total function as the extensible function (it is already total so it should also be extensible to total) and, for the non-extensible function something like this:

$$ g(x)=\left\{\begin{matrix} x \quad \text{if } x \epsilon K \\ \uparrow \quad \text{if } x\epsilon \overline{K} \end{matrix}\right. $$

which cannot be extended to total as doing so would imply that K is recursive, which we know is not. However, I am not sure whether this would work within the reduction method or not, as I would apply g(x) only when x $\epsilon$ K.

As for the other two sets: $$ TOT=\{x|\phi_x \text{ is total}\} \\ INF=\{x|dom(\phi_x) \text{is infinite}\} $$

again, I was instructed to use a reduction from $\overline{K}$ to the set, but again I find myself struggling with finding a suitable function for the reduction. Any help with how to better understand the method will be appreciated!

EDIT: I thought about the fact that the literature out there might not be consistent. K is the Halting Problem set, meaning that: $$ K= \{ x | \phi_x(x) \downarrow \} $$

$\endgroup$
0
$\begingroup$

First, a quick comment on extendibility in general. The function $g$ you describe is extendible to a total recursive function, contrary to what you claim - namely, it's extended by the identity function $x\mapsto x$. When we extend a partial recursive function to a total recursive function, we don't need (a priori) to keep track of the original domain, so the fact that $dom(g)$ is complicated in no way directly prevents $g$ from being extendible.

You have to work a bit harder to get a non-extendible function. As a partial hint, note that (fixing some $x$) if we have some $s$ such that we know $$\varphi_x(x)\downarrow\iff\varphi_x(x)[s]\downarrow,$$ then we can tell whether $x\in K$ just by running $\varphi_x(x)$ for $s$-many steps; conversely, for $x\in K$ we can find the stage $s$ at which point $\varphi_x(x)\downarrow$.


But let's say we've resolved the problem above, and we have a non-extendible function $h$. Then how can we use this to reduce $\overline{K}$ to $EXT$?

Well, suppose you're given an $x$ and you want to tell whether $x\in \overline{K}$. To do this, you want to build a function $f_x$ which is in $EXT$ iff $x\in\overline{K}$ - that is, iff we never see $\varphi_x(x)$ converge.

The general strategy for doing this sort of thing is to think of $f_x$ in terms of "until" - namely, you want $f_x$ to sound like $$\mbox{"do [blah] until (if ever) $\varphi_x(x)$ converges, after which point do [foo]."}$$ Here [blah] should be some behavior which makes $f_x$ look extendible, and [foo] should be some behavior which makes $f_x$ look non-extendible.

Looking extendible is easy - for example, we can simply require $f_x(y)$ to not be defined until we see $\varphi_x(x)$ converge (the everywhere-undefined function is definitely extendible!). Looking non-extendible is harder, but here's where our $h$ - once we have it - comes in: the $f_x$ we want should be "Look like the always-undefined function until we see $\varphi_x(x)$ converge, at which point behave like $h$." Now you just need to make this precise.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. I am not sure I fully understand your suggestion on how to find a non-extensible function. Are you simply saying that we are able to decide whether x $ \epsilon$ K or $\overline{K}$ by simply considering a number of steps s which is fixed a priori? I don't understand how we can claim that $\phi_x(x) \downarrow$ in s steps without assuming that $\phi_x(x)$ converges at all. $\endgroup$ – BattiestFawn66 Dec 25 '18 at 9:46
  • $\begingroup$ What about this new function: $$ g(x)=\left\{\begin{matrix} \phi_x(x)+1 \quad \text{if } x \epsilon K \\ \text{undefined} \quad \text{if } x\epsilon \overline{K} \end{matrix}\right. $$ can this be extended too by using the identity function when $x \epsilon \overline{K}$ ? And if so, could you please be more specific in explaining why, as it's not that clear to me at this stage. $\endgroup$ – BattiestFawn66 Dec 25 '18 at 9:51

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.