Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 1 / 12G / d

The total computable mapssatisfyHence $X{\le }_{m}X\oplus Y$ and $Y{\le }_{m}X\oplus Y$.

Let $K$ be the diagonal halting set and putIf $C$ were a computably enumerable set, then $n\mapsto 2n$ would many-one reduce $\mathbb{N}\setminus K$ to $C$, making the complement of $K$ computably enumerable. Together with the computable enumerability of $K$, that would make $K$ a computable set, a contradiction.

MoreoverIf this complement were computably enumerable, $n\mapsto 2n+1$ would again make $\mathbb{N}\setminus K$ computably enumerable. Thus neither $C$ nor its complement is computably enumerable.

Let total computable $f$ and $g$ witness $X{\le }_{m}Z$ and $Y{\le }_{m}Z$. DefineParity testing and integer division by two are computable, so $h$ is total computable. For every $m$,Therefore $X\oplus Y{\le }_{m}Z$.