Exercise 23:

K    {p,qDom(φp)Dom(φq)}\overline{K}\;\leq\;\{ \langle p,q\rangle \mid \mathtt{Dom}(\varphi_p)\subseteq\mathtt{Dom}(\varphi_q) \}
Reduce K\overline{K} to the set of pairs of natural numbers codifying programs such that the domain of the function computed by the machine codified by the first one is included into the domain of the function computed by the machine codified by the second one (roughly, the set of pairs of programs such that the domain of the function computed by the first one is included into the domain of the function computed by the second one), 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.