Exercise 26:

K    {p,qDom(φp)=    Dom(φq)=    Dom(φp)Dom(φq)=}\overline{K}\;\leq\;\{ \langle p,q\rangle \mid |\mathtt{Dom}(\varphi_p)|=\infty\;\wedge\;|\mathtt{Dom}(\varphi_q)|=\infty\;\wedge\;\mathtt{Dom}(\varphi_p)\cap\mathtt{Dom}(\varphi_q)=\emptyset \}
Reduce K\overline{K} to the set of pairs of natural numbers codifying programs such that the domains of the functions implemented by them are infinite and share no element (roughly, the set of pairs of programs implementing functions whose domains are infinite and share no element), 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.