This site uses cookies only for the purpose of identifying user sessions.
This is required to properly register actions.
$\overline{K}\;\leq\;\{ \langle p,q\rangle \mid \exists y_1,y_2:\;(M_p(y_1){\downarrow} \,\wedge\, M_q(y_1){\uparrow} \,\wedge\, M_p(y_2){\uparrow} \,\wedge\, M_q(y_2){\downarrow}) \}$
Reduce $\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, and there exists an input for which the first
program does not halt and the second program halts, (roughly, the set of pairs
of programs which stop and do not stop with some common input, and do not stop
and stop with some other common input), in order to prove that such set is not
semi-decidable (not recursively enumerable).
Authors: Carles Creus, Guillem Godoy
/
Documentation: