Exercise 13:

K    {pDom(φp)=    Im(φp)=    Dom(φp)Im(φp)=}\overline{K}\;\leq\;\{ p \mid |\mathtt{Dom}(\varphi_p)|=\infty\;\wedge\;|\mathtt{Im}(\varphi_p)|=\infty\;\wedge\;\mathtt{Dom}(\varphi_p)\cap\mathtt{Im}(\varphi_p)=\emptyset \}
Reduce K\overline{K} to the set of natural numbers codifying programs such that the domain and the image of the function computed by the program have infinite cardinal and are disjoint (roughly, the set of programs implementing functions whose domain and image are infinite and disjoint) 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.