Exercise 7:

K    {pφp total and non-injective}\overline{K}\;\leq\;\{ p \mid \varphi_p\text{ total and non-injective} \}
Reduce K\overline{K} to the set of natural numbers such that the program codified by them computes some total and non-injective function (roughly, the set of programs that compute some total and non-injective function), 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.