Set k is recursively enumerable non-recursive
Published May 26, 2022 - By Marco Garosi
Set in the computability theory is a “special” set, in the sense that it refers to a particular and well-defined set. Set is indeed defined as — that is, the set of all programs ( ) 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.)
Set is recursively enumerable (r.e.) but it is not recursive.
Let’s define the code that implements the mathematical function defined by . We’ll call that program :
Program is nothing but an interpreter. Running an interpreter on program and feeding it inpux is equivalent to running program and passing it input , that is: .
Now, the function computed by is:
Now let’s suppose, for the sake of contradiction, that ( ’s complement) is recursively enumerable (r.e.). Then .
Since is ’s complement (that is, ), .
Therefore, . However, and . Putting these all together, we get: , which is, of course, a contraditcion. Hence it is the case that is r.e. non-recursive.