Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 4F (Automata and Formal Languages)

A subset $E\subseteq \mathbb{N}$ is recursive when its indicator function is a total computable function. It is recursively enumerable when it is the domain of a partial computable function, equivalently when an algorithm can enumerate its members.

If $E$ is recursive, its indicator decides both $E$ and its complement, so both sets are recursively enumerable. Conversely, suppose programs enumerate $E$ and $\mathbb{N}\setminus E$. On input $n$, run the two enumerations in parallel by dovetailing. Exactly one must eventually print $n$; accept in the first case and reject in the second. This algorithm always halts and decides $E$. Hence

The setis the diagonal halting set. It is recursively enumerable by simulating the coded machine, but it is not recursive by the halting problem diagonal argument.

By contrast, ${\mathbb{K}}_{100}$ is recursive: decode $n$, reject it if it is not a program code, otherwise simulate the program on input $n$ for exactly $100$ steps and accept precisely if it has halted. This bounded computation always terminates. Thus