3
$\begingroup$

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$?

$\endgroup$
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\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 Jan 30 at 12:56
  • $\begingroup$ Right, there was a typo. Hopefully it's correct now. $\endgroup$ – Yuval Filmus Jan 30 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 Jan 30 at 19:51
  • $\begingroup$ The program $f(x)$ ignores its input. $\endgroup$ – Yuval Filmus Jan 30 at 23:47

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.