Set k is recursively enumerable non-recursive

Set $k$ in the computability theory is a “special” set, in the sense that it refers to a particular and well-defined set. Set $k$ is indeed defined as $k = \{ x | \varphi_x(x) \downarrow \}$ — that is, the set of all programs ( $x$) that halt when they’re passed themselves as input. (Note that this is possible because a program is really just a long binary string — namely, a binary number. That’s why a progam can be “passed” to itself as an input.)

Statement

Set $k = \{ x | \varphi_x(x) \downarrow \}$ is recursively enumerable (r.e.) but it is not recursive.

Proof

Let’s define the code that implements the mathematical function defined by $k$. We’ll call that program $\tilde{k}$:

Program $\text{INT}$ is nothing but an interpreter. Running an interpreter on program $x$ and feeding it inpux $x$ is equivalent to running program $x$ and passing it input $x$, that is: $\varphi_{\text{INT}}(x, x) = \varphi_x(x)$.

Now, the function computed by $\tilde{k}$ is:

$\tilde{k}$'s domain is denoted as $W_{\tilde{k}}$. $W_{\tilde{k}} = k$.

Now let’s suppose, for the sake of contradiction, that $\bar{k}$ ( $k$’s complement) is recursively enumerable (r.e.). Then $\exists P \text{ program (} P \in \text{GitHub)} : W_P = \bar{k}$.

Since $\bar{k}$ is $k$’s complement (that is, $\bar{k} = \N \setminus k$), $\bar{k} = \{ x | \varphi_x(x) \uparrow \}$.

Therefore, $P \in \bar{k} \iff P \in W_P$. However, $P in \bar{k} \iff \varphi_P(P) \uparrow$ and $P \in W_P \iff \varphi_P(P) \downarrow$. Putting these all together, we get: $\varphi_P(P) \uparrow \iff P \in \bar{k} \iff P \in W_P \iff \varphi_P(P) \downarrow$, which is, of course, a contraditcion. Hence it is the case that $K$ is r.e. non-recursive.