[proofplan] All three parts reduce to concrete function compositions built from two simple computable functions: a *flip* that exchanges $\varepsilon$ with a fixed non-empty word $a$, and a *loop-on-empty* function that halts on non-empty inputs and diverges on $\varepsilon$. Part (i) uses the flip to relate the characteristic function of $X$ to that of its complement. Part (ii) uses the fact that the domain of a computable partial function is the set of inputs on which its register machine halts — so a set is the domain of some machine iff it is the domain of a computable partial function, which matches the standard definition of computable enumerability. Part (iii) uses the loop-on-empty function: composed with $\mathbb{1}_X$, it diverges on $X^c$ and outputs $a$ on $X$, realising the semi-characteristic function $\psi_X$. We prove each part for $k = 1$; the argument for general $k$ is identical after interpreting each register variable as a $k$-tuple of registers, a reduction that preserves computability because the standard register-machine model supports arbitrary finite register counts. [/proofplan] [step:Fix the computability definitions and the auxiliary functions $f_1, f_2, f_3$] Let $\mathbb{W} = \Sigma^*$ be the word monoid over a fixed finite alphabet $\Sigma$ with at least one letter $a \in \Sigma$. For $X \subseteq \mathbb{W}^k$: - $X$ is [computable](/pages/???) iff its *characteristic function* \begin{align*} \mathbb{1}_X : \mathbb{W}^k &\to \mathbb{W}, \\ w &\mapsto \begin{cases} a & w \in X, \\ \varepsilon & w \notin X, \end{cases} \end{align*} is a computable total function, where $a$ and $\varepsilon$ are treated as fixed representative words for "true" and "false". - $X$ is [computably enumerable](/pages/???) (c.e.) iff its *semi-characteristic function* \begin{align*} \psi_X : \mathbb{W}^k &\rightharpoonup \mathbb{W}, \\ w &\mapsto \begin{cases} a & w \in X, \\ \text{undefined} & w \notin X, \end{cases} \end{align*} is a computable partial function. For a register machine $M$ and register count $k$, write $f_{M, k} : \mathbb{W}^k \rightharpoonup \mathbb{W}$ for the partial function it computes on inputs in $\mathbb{W}^k$; then $\operatorname{dom} f_{M, k}$ is the set of inputs on which $M$ halts. We work with $k = 1$ for clarity; the case of general $k$ follows the same argument since register machines are defined for arbitrary finite register counts and each reference to "input $w$" becomes "input tuple $w = (w_1, \ldots, w_k)$" without further modification. Define three total or partial functions, all computable by explicit register machines: - The *flip* \begin{align*} f_1 : \mathbb{W} &\to \mathbb{W}, \\ w &\mapsto \begin{cases} \varepsilon & w \ne \varepsilon, \\ a & w = \varepsilon. \end{cases} \end{align*} - The *return-$a$-on-nonempty* total function \begin{align*} f_2 : \mathbb{W} &\to \mathbb{W}, \\ w &\mapsto \begin{cases} a & w \ne \varepsilon, \\ \varepsilon & w = \varepsilon. \end{cases} \end{align*} - The *loop-on-empty* partial function \begin{align*} f_3 : \mathbb{W} &\rightharpoonup \mathbb{W}, \\ w &\mapsto \begin{cases} a & w \ne \varepsilon, \\ \text{undefined} & w = \varepsilon. \end{cases} \end{align*} [claim:$f_1, f_2, f_3$ are computable] We construct a register machine for each. - *Machine for $f_1$*: test whether register $0$ is empty. This test is a single read instruction which branches on the first letter of register $0$ (or on the letter $\varepsilon$, which by convention signals an empty register). If empty, write $a$ to register $0$ and halt; if non-empty, erase register $0$ and halt. This is a [case distinction](/theorems/1812) on the question "is register $0$ empty?", whose answers are the two cases; each arm is a finite program performing a fixed register operation. - *Machine for $f_2$*: same structure with the outputs swapped. If register $0$ is empty, leave it alone; if non-empty, erase register $0$, then write $a$ to it; in both cases halt. - *Machine for $f_3$*: test whether register $0$ is empty. If non-empty, erase and write $a$, then halt; if empty, enter a self-loop (e.g., an instruction that increments an unused register and loops back). The self-loop forms an infinite computation on input $\varepsilon$, so $f_3$ is undefined at $\varepsilon$ and defined with value $a$ elsewhere. Each machine is finite and realises the claimed function by direct inspection of its branching structure. [/claim] [/step] [step:Prove (i) — $X$ is computable iff $X^c$ is computable] [claim:$\mathbb{1}_{X^c} = f_1 \circ \mathbb{1}_X$] Let $w \in \mathbb{W}^k$. If $w \in X$, then $\mathbb{1}_X(w) = a \ne \varepsilon$, so $f_1(\mathbb{1}_X(w)) = f_1(a) = \varepsilon$; and $w \notin X^c$, so $\mathbb{1}_{X^c}(w) = \varepsilon$. Agreement. If $w \notin X$, then $\mathbb{1}_X(w) = \varepsilon$, so $f_1(\mathbb{1}_X(w)) = f_1(\varepsilon) = a$; and $w \in X^c$, so $\mathbb{1}_{X^c}(w) = a$. Agreement. [/claim] Assume $X$ is computable, so $\mathbb{1}_X$ is a computable total function. Compose with the computable total $f_1$: the composition $f_1 \circ \mathbb{1}_X$ is computable (run a machine for $\mathbb{1}_X$, then feed its output into a machine for $f_1$ — this is realised by [sequential composition of register machines](/theorems/???), which yields a register machine for the composite total function). By the identity $\mathbb{1}_{X^c} = f_1 \circ \mathbb{1}_X$, the function $\mathbb{1}_{X^c}$ is computable, so $X^c$ is computable. Conversely, if $X^c$ is computable, applying the same argument with $X^c$ in place of $X$ (and noting $(X^c)^c = X$) gives $\mathbb{1}_X = f_1 \circ \mathbb{1}_{X^c}$, hence $X$ is computable. [/step] [step:Prove (ii) — $X$ is c.e. iff $X = \operatorname{dom} f_{M, k}$ for some register machine $M$] *Forward direction.* Suppose $X$ is c.e., so $\psi_X : \mathbb{W}^k \rightharpoonup \mathbb{W}$ is a computable partial function. By the definition of computable partial function, there is a register machine $M_\psi$ such that $f_{M_\psi, k} = \psi_X$. Then \begin{align*} \operatorname{dom} f_{M_\psi, k} &= \operatorname{dom} \psi_X = \{w \in \mathbb{W}^k : \psi_X(w) \text{ is defined}\} = X. \end{align*} *Reverse direction.* Suppose $X = \operatorname{dom} f_{M, k}$ for some register machine $M$. We must show $\psi_X$ is computable. Define the computable partial function $f := f_{M, k}$. Then $\operatorname{dom} f = X$. [claim:$\psi_X = f_2 \circ f$] The composition $f_2 \circ f$ is a partial function defined on $\operatorname{dom} f = X$. For $w \in X$, $(f_2 \circ f)(w) = f_2(f(w))$; since $f_2$ is total with range $\{\varepsilon, a\}$, this is defined. Whether the output is $a$ or $\varepsilon$ depends on whether $f(w)$ is non-empty or empty. Observe that $f_2$ sends any non-empty input to $a$ and $\varepsilon$ to $\varepsilon$. The value $f(w)$ can in principle be either, so $f_2 \circ f$ alone does not always output $a$. To force the output to $a$ regardless of the value of $f(w)$, we must first erase $f(w)$'s value and then write $a$ if the computation halted. But the composition $f_2 \circ f$ does not yet guarantee this; let us correct the construction. Replace $f_2$ by the total function \begin{align*} \tilde{f}_2 : \mathbb{W} &\to \mathbb{W}, \\ w &\mapsto a, \end{align*} the constant $a$ function, which is computable (the machine that erases register $0$ and writes $a$, then halts). Then $\tilde{f}_2 \circ f$ is a partial function with domain $\operatorname{dom} f = X$ and constant value $a$ on that domain; this is exactly $\psi_X$. Composition of a computable partial function with a computable total function is computable (by sequential composition of register machines), so $\psi_X$ is computable, proving $X$ is c.e. (The course-notes construction using $f_2$ works correctly when one knows that the output of $f$ on $X$ is always non-empty, or when one is content to set up $f$ so that it halts with a designated non-empty "true" value; in either case the composition with $f_2$ gives $a$ on $X$ and is undefined off $X$. Our replacement $\tilde{f}_2$ avoids this assumption.) [/claim] [/step] [step:Prove (iii) — $X$ computable implies $X$ c.e.] Suppose $X$ is computable, so $\mathbb{1}_X$ is a computable total function. [claim:$\psi_X = f_3 \circ \mathbb{1}_X$] The composition $f_3 \circ \mathbb{1}_X$ is a partial function. For $w \in X$, $\mathbb{1}_X(w) = a \ne \varepsilon$, so $f_3(\mathbb{1}_X(w)) = f_3(a) = a$. For $w \notin X$, $\mathbb{1}_X(w) = \varepsilon$, and $f_3(\varepsilon)$ is undefined, so $(f_3 \circ \mathbb{1}_X)(w)$ is undefined. This matches $\psi_X$. [/claim] The composition of a computable partial function $f_3$ with a computable total function $\mathbb{1}_X$ is computable: one runs a register machine for $\mathbb{1}_X$ to completion (which always halts because $\mathbb{1}_X$ is total), then feeds its output to a register machine for $f_3$, which halts iff its input is non-empty. The resulting composite register machine halts precisely on $X$ with output $a$, realising $\psi_X$. Hence $\psi_X$ is a computable partial function, so $X$ is c.e. [guided] We want to show that computability implies computable enumerability. The semantic contrast is: computability requires the machine to always halt and give a correct yes/no answer, while computable enumerability only requires it to halt on "yes" inputs, with no requirement on "no" inputs. So going from computable to c.e. is a matter of *introducing divergence* on the complement $X^c$: we must suppress the "no" output and replace it with a non-halting computation. The trick is to chain $\mathbb{1}_X$ (which distinguishes $X$ from $X^c$ by outputting $a$ vs $\varepsilon$) with $f_3$ (which halts on non-empty words and loops on $\varepsilon$). This chaining converts the distinction "output $a$ vs output $\varepsilon$" into "halt vs loop forever": \begin{align*} (f_3 \circ \mathbb{1}_X)(w) &= f_3(\mathbb{1}_X(w)) = \begin{cases} f_3(a) = a & w \in X, \\ f_3(\varepsilon) = \text{undefined} & w \notin X. \end{cases} \end{align*} This is precisely $\psi_X$. Why does composition preserve computability? In the register-machine model, a composite machine for $f_3 \circ \mathbb{1}_X$ is constructed by running a machine for $\mathbb{1}_X$ to completion (valid because $\mathbb{1}_X$ is total), identifying its halt state with the start state of a machine for $f_3$ (after appropriate disjointness renaming of states, as in the [Case Distinction Lemma](/theorems/1812)), and adopting the halt state of the $f_3$ machine as the halt state of the composite. The composite's domain is exactly the set of $w$ on which the $f_3$-phase halts, i.e., the set of $w$ on which $\mathbb{1}_X(w) \ne \varepsilon$, which is $X$. The output on $X$ is the output of $f_3$ on $a$, which is $a$. Hence the composite realises $\psi_X$, proving $X$ is c.e. [/guided] [/step]