Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 1 / 12G (Automata and Formal Languages)

Fix an effective enumeration ${\phi }_0,{\phi }_1,\dots$ of unary partial computable functions. The diagonal halting set isIt is a computably enumerable set: on input $e$, simulate ${\phi }_e(e)$ and accept if that computation halts.

Suppose $K$ were a computable set. A program could then halt on input $e$ exactly when the decider says $e\notin K$. Let $d$ be its own index. If $d\in K$, the program does not halt, while if $d\notin K$, it halts. Both alternatives contradict the definition of $K$. Thus $K$ is computably enumerable but not computable.

A many-one reduction $A{\le }_{m}B$ is a total computable function $f$ such thatIf $B$ is a computably enumerable set, compute $f(n)$ and run a semidecision procedure for $B$ on that value. It halts exactly when $f(n)\in B$, equivalently exactly when $n\in A$. Therefore $A$ is computably enumerable.

Let $S(n)=n+1$ be the successor function. Define $f$ by primitive recursionInduction gives $f(n)=2n$. Then defineby composition. Initial functions, composition, and primitive recursion produce primitive recursive functions, so $f$ and $g$ are partial recursive functions and are visibly defined for every $n$. Both functions are total.

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$.