Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 4I (Automata & Formal Languages)

A subset $A\subseteq {\Sigma }^{\ast }$ is a computably enumerable set if there is a program, equivalently a register machine, that halts on input $w$ exactly when $w\in A$. It need not halt when $w\notin A$.

Statement (i) implies (ii) directly from the definition: if $A$ is computably enumerable, its semidecision program computes a partial computable function whose domain is exactly $A$; for example, return the empty word whenever the program halts.

Suppose $A=\mathrm{dom}f$ for a partial computable function $f$. Defineand leave $g(w)$ undefined otherwise. A program computes $g$ by running $f(w)$ and returning $w$ if that computation halts. Hence $g$ is partial computable andwhich proves (ii)$\Rightarrow$(iii).

Suppose $A=\mathrm{ran}f$ for a partial computable function $f$. Since $A\ne \varnothing$, fix $a_0\in A$. Decode each input $w$ as a pair $((w{)}_0,(w{)}_1)=(u,t)$. Using the truncated computation function, defineThis is a total computable function, and every output lies in $A$. Conversely, if $a=f(u)$, choosing $t$ at least the halting time gives an input $w$ with $h(w)=a$. Thus $\mathrm{ran}h=A$, proving (iii)$\Rightarrow$(iv).

Suppose $A=\mathrm{ran}h$ for a total computable function $h$. Effectively enumerate the words as $w_0,w_1,\dots$. On input $x$, computein order and halt as soon as one equals $x$. Every individual computation terminates because $h$ is total. The search halts exactly for $x\in \mathrm{ran}h=A$, so $A$ is computably enumerable. This proves (iv)$\Rightarrow$(i) and completes the equivalence recorded by the domain and range characterizations of a nonempty computably enumerable set.