Set k is recursively enumerable non-recursive

Published May 26, 2022  -  By Marco Garosi

Set kk in the computability theory is a “special” set, in the sense that it refers to a particular and well-defined set. Set kk is indeed defined as k={xφx(x)}k = \{ x | \varphi_x(x) \downarrow \} — that is, the set of all programs ( xx) 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φx(x) }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 kk. We’ll call that program k~\tilde{k}:

input(x);if INT(x,x) then output(YES) \text{input}(x); \\ \text{if INT}(x, x) \downarrow \text{ then output}(\text{YES})

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

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

φk~(x)={1if xkotherwise \varphi_{\tilde{k}}(x) = \begin{cases} 1 &\text{if } x \in k \\ \uparrow &\text{otherwise} \end{cases}

k~\tilde{k}'s domain is denoted as Wk~W_{\tilde{k}}. Wk~=kW_{\tilde{k}} = k.

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

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

Therefore, Pkˉ    PWPP \in \bar{k} \iff P \in W_P. However, Pinkˉ    φP(P)P in \bar{k} \iff \varphi_P(P) \uparrow and PWP    φP(P)P \in W_P \iff \varphi_P(P) \downarrow. Putting these all together, we get: φP(P)    Pkˉ    PWP    φP(P)\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 KK is r.e. non-recursive.

Share on: