Exercise 22:

K    {p,qDom(φp)=Dom(φq)=Im(φp)=Im(φq)=1    Dom(φp)Dom(φq)Im(φp)Im(φq)=4}\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)|=4 \}
Reduce K\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 11 element, and the union of the domains and images of both programs has exactly 44 elements (roughly, the set of pairs of programs whose domains and images have exactly 11 element, and the union of all such domains and images have exactly 44 elements) 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.