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$?
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
4 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$.
- $\begingroup$ 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. $\endgroup$Tom Ryddle– Tom Ryddle2020-01-30 12:56:07 +00:00Commented Jan 30, 2020 at 12:56
- $\begingroup$ Right, there was a typo. Hopefully it's correct now. $\endgroup$Yuval Filmus– Yuval Filmus2020-01-30 13:33:57 +00:00Commented Jan 30, 2020 at 13:33
- $\begingroup$ 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$. $\endgroup$Tom Ryddle– Tom Ryddle2020-01-30 19:51:46 +00:00Commented Jan 30, 2020 at 19:51
- $\begingroup$ The program $f(x)$ ignores its input. $\endgroup$Yuval Filmus– Yuval Filmus2020-01-30 23:47:19 +00:00Commented Jan 30, 2020 at 23:47