# Is the following fuction computable?

I'm trying to show that $$K_1 \le_1 K$$ where $$K$$ is the diagonal halting set $$\{x : \varphi_x(x) \downarrow\}$$ and $$K_1=\{x: \exists y \,\, \varphi_x(y) \downarrow\}$$, then I defined the function $$\psi(x, y)= \begin{cases} 0 \, \, if \, \, x \in K_1 \\ \uparrow \, if \, x \notin K_1\end{cases}$$ By the Parameter Theorem there is a one to one computable function $$f$$ such that $$\varphi_{f(x)}(y) = \psi(x, y)$$ and it's easy to show that $$x \in K_1 \leftrightarrow f(x) \in K$$. All above works if and only if $$\psi$$ is partial computable, I think that function is partial computable because $$K_1$$ is r.e. Is this true? I mean, Can I always define a function computable by $$\psi_A(x, y)= \begin{cases} 0 \, \, if \, \, x \in A \\ \uparrow \, if \, x \notin A\end{cases}$$ for each r.e. set $$A$$?

## 1 Answer

You're using the terminology of recursion theory. Let me rephrase the argument in terms of computer programs.

• $$K$$ is the set of all programs $$x$$ which halt when run on $$x$$ as input.
• $$K_1$$ is the set of all programs $$x$$ which halt on some input.

Given a program $$x$$, consider the following program $$f(x)$$:

• For $$n=1,2,3,\ldots$$: run program $$x$$ on inputs $$1,\ldots,n$$ for $$n$$ steps, and halt if $$x$$ halts of any of them halt.

The program $$f(x)$$ halts iff $$x \in K_1$$. In particular, $$x \in K_1$$ iff $$f(x) \in K$$. Since $$f$$ is computable, this gives a reduction from $$K_1$$ to $$K$$.

• It's not clear that $x \in K_1$ iff $f(x) \in K$, why $f(x)$ halts when run on $f(x)$? Moreover, I need that $f$ to be a one to one function which it's not nessesarily true in your argument. – Tom Ryddle Jan 30 '20 at 12:56
• Right, there was a typo. Hopefully it's correct now. – Yuval Filmus Jan 30 '20 at 13:33
• It's clear that the program $f(x)$ halts iff $x \in K_1$ then $x \in K_1$ iff $f(x) \in K_1$, but It is still unclear why the program $f(x)$ halts when it runs on $f(x)$ for every $x$ is in $K_1$. – Tom Ryddle Jan 30 '20 at 19:51
• The program $f(x)$ ignores its input. – Yuval Filmus Jan 30 '20 at 23:47