Exercise 15:

K    {p,qy:  (Mp(y)Mq(y))}\overline{K}\;\leq\;\{ \langle p,q\rangle \mid \exists y:\;(M_p(y){\downarrow} \,\wedge\, M_q(y){\uparrow}) \}
Reduce K\overline{K} to the set of pairs of natural numbers codifying programs such that there exists an input for which the first program halts and the second program does not halt (roughly, the set of pairs of programs which stop and do not stop with some common 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.