## Exercise ‹20›:

$\overline{K}\;\leq\;\{ \langle p,q\rangle \mid |\mathtt{Dom}(\varphi_p)|=|\mathtt{Dom}(\varphi_q)|=|\mathtt{Im}(\varphi_p)|=|\mathtt{Im}(\varphi_q)|=1\;\wedge\;|\mathtt{Dom}(\varphi_p)\cup\mathtt{Dom}(\varphi_q)\cup\mathtt{Im}(\varphi_p)\cup\mathtt{Im}(\varphi_q)|=2 \}$
Reduce $\overline{K}$ to the set of pairs of natural numbers codifying programs such that each domain and image of the function computed by each of such programs has exactly $1$ element, and the union of the domains and images of both programs has exactly $2$ elements (roughly, the set of pairs of programs whose domains and images have exactly $1$ element, and the union of all such domains and images have exactly $2$ elements) in order to prove that such set is not semi-decidable (not recursively enumerable).
Authors: Carles Creus, Guillem Godoy / Documentation:
 input y { // Write the code for program 'p' here... } input y { // Write the code for program 'q' here... } To be able to submit you need to either log in, register, or become a guest.