# Prove that EXT,TOT and INF are not recursively enumerable

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 \}$$

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.

• 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. – BattiestFawn66 Dec 25 '18 at 9:46
• 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. – BattiestFawn66 Dec 25 '18 at 9:51