# Set k is recursively enumerable non-recursive

Published May 26, 2022 - By Marco Garosi

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:

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.