This site uses cookies only for the purpose of identifying user sessions.
This is required to properly register actions.
$\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 $\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 $4$ 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 $4$ elements) in order to prove that such set
is not semi-decidable (not recursively enumerable).
Authors: Carles Creus, Guillem Godoy
/
Documentation: