I'm trying to show that if $A$ is c.e., then $A\leq_m K$, where $K$ is the set of all programs that halt on themselves.
I'm trying to use essentially the same strategy as I described here.
$A$ is c.e., so it's the domain of a computable function that is computed by a program $p$. Consider the function $$V:N\times N\to N\\(n,x)\mapsto 1 \text{ if $p$ halts on argument $n$ in $\le x$ steps} $$ otherwise $V$ is undefined. Now from the existence of the Godel universal function $U$ (defined here) it follows that there is a total computable $s:N\to N$ such that for all $x,n\in N$ $$V(n,x)=U(s(n),x).$$
- if $n\notin A$, then $V$ is always undefined, and so $s(n)$ doesn't lie in $K$ (otherwise $U(s(n),s(n))$ would have been defined).
- if $n\in A$, then $V$ is defined for large $x$. I want to conclude that $V(s(n),s(n))$ is defined (so that $s(n)\in K$, which would conclude the proof), but maybe $V$ is defined for $x$s such that $s(n)< x$. How to resolve this problem?
After seeing HallaSurvivor's answer, I think I can define $V$ as follows:
$$V:N\times N\to N\\ (n,x)=\chi_A(n)$$ where $\chi_A$ is the semi-characteristic function of $A$. This is a computable function because $\chi_A$ is computable. Now if $n\in A$, then in particular $U(s(n),x)$ is defined for all $x$ (including $x=s(n)$), and from this we can conclude that $s(n)\in K$.
Let me know if my reasoning isn't correct.
Let $A \subseteq \mathbb{N}$ be c.e.
To show $A \leq_m K$ we want to find a computable function $f : n \mapsto \ulcorner M_n \urcorner$ so that $n \in A \iff M_n(\ulcorner M_n \urcorner) \downarrow$. Here I am writing $M_n(x) \downarrow$ if the computation halts, and $\ulcorner M \urcorner$ for some encoding of $M$.
Let $\chi_A$ be a semidecider for $A$. That is
$$\chi_A(n) = \begin{cases} 1 & n \in A \\ \text{undefined} & \text{otherwise} \end{cases}$$
Consider the program $M_n(x)$ which ignores its input and computes $\chi_A(n)$. Then
$$n \in A \iff \chi_A(n) \downarrow \iff M_n(\ulcorner M_n \urcorner) \downarrow \iff \ulcorner M_n \urcorner \in K$$
You can argue by the church-turing thesis that $n \mapsto \ulcorner M_n \urcorner$ is computable, but with enough persistence you might be able to do it directly.
I hope this helps ^_^