Exercise ‹3›:

K‾  ≤  {p∣∃y:  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 log in, register, or become a guest.