Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 12F (Automata & Formal Languages)

For $C,D\subseteq \mathbb{B}$, one writes $C{\le }_{m}D$ if there is a total computable function $f:\mathbb{B}\to \mathbb{B}$ such thatfor every $x$. This is a computable many-one reduction.

One writes $C{\equiv }_{m}D$ when both $C{\le }_{m}D$ and $D{\le }_{m}C$.

Fix an effective coding of machines and write $W_w$ for the computably enumerable language recognized by code $w$. A set $I$ of codes is an index set when membership depends only on the recognized language:It is nontrivial when it is neither empty nor all of $\mathbb{B}$.

Let $K=\{w:w\in W_w\}$ and let $e_{\varnothing }$ be any index for the empty language. The proof of Rice theorem givesIn either case choose a language on the opposite side of the nontrivial property and switch from the empty enumerator to its enumerator if the simulated diagonal computation halts.

The empty language belongs to $\mathbf{Emp}$, so the second case applies:It does not belong to $\mathbf{Inf}$, so the first case applies:

The set of codes of even length is not an index set because code length is syntactic rather than a property of $W_w$. By the padding lemma, every computably enumerable language has equivalent machine descriptions of arbitrarily many lengths, in particular descriptions of both parities. Hence equal recognized languages need not give equal membership.

Since the empty language does not lie inRice's construction gives $K{\le }_m\mathbf{Two}$. Conversely, $\mathbf{Two}$ is computably enumerable: dovetail the enumerator for $W_w$ until two distinct words appear, then accept. The diagonal halting set $K$ is many-one complete for computably enumerable sets, so $\mathbf{Two}{\le }_{m}K$. Therefore

For $K{\le }_m\mathbf{Cof}$, map $x$ to a machine that initially enumerates nothing and, if the simulation establishing $x\in K$ halts, enumerates every word. Its language is cofinite exactly when $x\in K$.

For $\mathbb{B}\setminus K{\le }_m\mathbf{Cof}$, map $x$ to a machine that enumerates successively longer finite initial segments of $\mathbb{B}$ while simulating $x$. If the simulation never halts, every word is eventually enumerated; if it halts, enumeration stops with a finite language and therefore an infinite complement. Thus the constructed language is cofinite exactly when $x\notin K$.

The parameter theorem makes both code transformations total and computable.