Exercise 3:

K    {py:  Mp(y)}\overline{K}\;\leq\;\{ p \mid \exists y:\;M_p(y){\uparrow} \}
Reduce K\overline{K} to the set of natural numbers such that the program codified by them does not halt with some input (roughly, the set of programs non-halting with some input), in order to prove that such set is not semi-decidable (not recursively enumerable).
Authors: Carles Creus, Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.