Exercise 14:

K    {p,qy:  (Mp(y)Mq(y))}K\;\leq\;\{ \langle p,q\rangle \mid \exists y:\;(M_p(y){\downarrow} \,\wedge\, M_q(y){\downarrow}) \}
Reduce KK to the set of pairs of natural numbers codifying programs halting with a common input (roughly, the set of pairs of programs which stop with the same common input), in order to prove that such set is undecidable (not recursive).
Authors: Carles Creus, Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.