[proofplan]
For each closure operation we construct a total computable indicator of the result from the total computable indicators of $A$ and $B$. Intersection uses a case split that outputs $a$ only when both indicators return $a$; complement flips the two output values; union reduces to intersection and complement via de Morgan; difference reduces to $A \cap B^c$. Concatenation (for $A, B \subseteq \mathbb{W}$) exploits that a word $w \in \mathbb{W}$ admits only finitely many split points $w = uv$ — exactly $|w| + 1$ of them — so we loop through all splits and accept if any witnesses $u \in A$, $v \in B$. Each construction is a bounded register-machine composition of total computable sub-routines, hence total and computable.
[/proofplan]
[step:Fix the setting and recall the indicator characterisation of computability]
Fix the course alphabet $\Sigma$ with distinguished accept letter $a \in \Sigma$, and write $\mathbb{W} = \Sigma^*$. A set $A \subseteq \mathbb{W}^k$ is *computable* iff its indicator
\begin{align*}
\mathbb{1}_A : \mathbb{W}^k &\to \mathbb{W}, \\
w &\mapsto \begin{cases} a & \text{if } w \in A, \\ \varepsilon & \text{if } w \notin A, \end{cases}
\end{align*}
is total computable. We use this characterisation throughout.
Let $A, B \subseteq \mathbb{W}^k$ be computable, with witnesses $\mathbb{1}_A, \mathbb{1}_B$ total computable. We treat $k \ge 1$ generic for intersection, union, complement, and difference, and specialise to $k = 1$ for concatenation.
Throughout the proof we use two closure properties of total computable functions (both proved in Step 4 of the proof of [Recursive Implies Computable](/theorems/1817)):
(L1) Total computable functions are closed under composition.
(L2) Total computable functions are closed under case distinction on computable predicates: given total computable $g_1, g_2 : \mathbb{W}^k \to \mathbb{W}$ and a total computable predicate $P : \mathbb{W}^k \to \{a, \varepsilon\}$, the map $w \mapsto g_1(w)$ if $P(w) = a$ else $g_2(w)$ is total computable.
[/step]
[step:Intersection: build $\mathbb{1}_{A \cap B}$ from $\mathbb{1}_A$ and $\mathbb{1}_B$ by case distinction]
Define
\begin{align*}
\mathbb{1}_{A \cap B} : \mathbb{W}^k &\to \mathbb{W}, \\
w &\mapsto \begin{cases} a & \text{if } \mathbb{1}_A(w) = a \text{ and } \mathbb{1}_B(w) = a, \\ \varepsilon & \text{otherwise}. \end{cases}
\end{align*}
[claim:$\mathbb{1}_{A \cap B}$ is total computable]
A register machine $M_\cap$ witnessing $\mathbb{1}_{A \cap B}$ works as follows. On input $w$ in input registers, first save a master copy of $w$ into scratch registers; then run the machine $M_A$ witnessing $\mathbb{1}_A$; read the output from register $0$. If the output is $\varepsilon$, halt with output $\varepsilon$. If the output is $a$, restore $w$ from the master copy, run $M_B$ witnessing $\mathbb{1}_B$, and output whatever $M_B$ outputs ($a$ or $\varepsilon$).
Since $\mathbb{1}_A$ and $\mathbb{1}_B$ are total computable, $M_A$ and $M_B$ halt on every input. The save/restore of registers and the conditional halt on register $0$'s value are bounded primitive operations. Hence $M_\cap$ halts on every input, so $\mathbb{1}_{A \cap B}$ is total; and by inspection its output matches the definition, so it computes $\mathbb{1}_{A \cap B}$. Formally this is an instance of L2 with $P = \mathbb{1}_A$, $g_1 = \mathbb{1}_B$, $g_2 =$ constant $\varepsilon$.
[/claim]
Hence $A \cap B$ is computable.
[/step]
[step:Complement: flip the output letter of $\mathbb{1}_A$]
Define
\begin{align*}
\operatorname{flip} : \mathbb{W} &\to \mathbb{W}, \\
x &\mapsto \begin{cases} \varepsilon & \text{if } x = a, \\ a & \text{if } x = \varepsilon, \\ x & \text{otherwise}. \end{cases}
\end{align*}
The function $\operatorname{flip}$ is total computable (a finite case distinction on the content of register $0$). Then
\begin{align*}
\mathbb{1}_{A^c} &= \operatorname{flip} \circ \mathbb{1}_A,
\end{align*}
where $A^c := \mathbb{W}^k \setminus A$. To verify the equality: if $w \in A^c$ then $\mathbb{1}_A(w) = \varepsilon$, so $\operatorname{flip}(\mathbb{1}_A(w)) = a$; if $w \in A$ then $\mathbb{1}_A(w) = a$, so $\operatorname{flip}(\mathbb{1}_A(w)) = \varepsilon$. Both cases match the definition of $\mathbb{1}_{A^c}$.
By L1 (closure under composition), $\mathbb{1}_{A^c}$ is total computable. Hence $A^c$ is computable.
[/step]
[step:Union: reduce to intersection and complement via de Morgan]
By de Morgan's law,
\begin{align*}
A \cup B &= (A^c \cap B^c)^c.
\end{align*}
By Step 3, $A^c$ and $B^c$ are computable. By Step 2, their intersection $A^c \cap B^c$ is computable. By Step 3 again, its complement $(A^c \cap B^c)^c$ is computable. Hence $A \cup B$ is computable.
Alternatively, one may construct $\mathbb{1}_{A \cup B}$ directly by case distinction: output $a$ if $\mathbb{1}_A(w) = a$ else $\mathbb{1}_B(w)$. This is total computable by the same L2-argument as in Step 2 (with $P = \mathbb{1}_A$, $g_1 =$ constant $a$, $g_2 = \mathbb{1}_B$).
[/step]
[step:Difference: reduce to intersection and complement]
By definition of set difference,
\begin{align*}
A \setminus B &= A \cap B^c.
\end{align*}
By Step 3, $B^c$ is computable. By Step 2, $A \cap B^c$ is computable. Hence $A \setminus B$ is computable.
[/step]
[step:Concatenation: specialise to $k = 1$ and fix the definition of $AB$]
Now take $k = 1$, so $A, B \subseteq \mathbb{W}$. The concatenation is
\begin{align*}
A B &= \{uv : u \in A, v \in B\} \subseteq \mathbb{W},
\end{align*}
where $uv$ denotes word concatenation in $\mathbb{W} = \Sigma^*$.
For $w \in \mathbb{W}$, a *split* of $w$ is a pair $(u, v) \in \mathbb{W} \times \mathbb{W}$ with $u v = w$. The splits of a word of length $n := |w|$ are in bijection with positions $j \in \{0, 1, \ldots, n\}$ via $u = w[1 \ldots j]$ (the first $j$ letters) and $v = w[j + 1 \ldots n]$ (the remaining $n - j$ letters). There are exactly $n + 1$ splits, and $w \in AB$ iff at least one split $(u, v)$ has $u \in A$ and $v \in B$.
[/step]
[step:Build $\mathbb{1}_{AB}$ by bounded iteration over splits]
Define
\begin{align*}
\mathbb{1}_{AB} : \mathbb{W} &\to \mathbb{W}, \\
w &\mapsto \begin{cases} a & \text{if there exists } j \in \{0, 1, \ldots, |w|\} \text{ with } w[1 \ldots j] \in A \text{ and } w[j + 1 \ldots |w|] \in B, \\ \varepsilon & \text{otherwise}. \end{cases}
\end{align*}
[claim:$\mathbb{1}_{AB}$ is total computable]
A register machine $M_{AB}$ witnessing $\mathbb{1}_{AB}$ proceeds as follows. On input $w$ in register $0$:
(a) Compute $n := |w|$ by a primitive register-machine length routine.
(b) Initialise an index register $j := 0$ and a flag register $\texttt{found} := \varepsilon$.
(c) Loop while $j \le n$:
- Copy $w$ from a master register into a scratch register and extract the prefix $u := w[1 \ldots j]$ (remove the last $n - j$ letters by a bounded truncation loop) and the suffix $v := w[j + 1 \ldots n]$ (similarly). Prefix and suffix extraction of a word by a given index is a register-machine primitive, cf. the word-manipulation constructions in the proof of [Recursive Implies Computable](/theorems/1817).
- Run $M_A$ on $u$ to obtain $\mathbb{1}_A(u)$. If $\mathbb{1}_A(u) = a$, run $M_B$ on $v$ to obtain $\mathbb{1}_B(v)$; if $\mathbb{1}_B(v) = a$, set $\texttt{found} := a$ and break out of the loop.
- Otherwise increment $j$.
(d) Output $\texttt{found}$.
Termination: the outer loop runs at most $n + 1$ iterations, each containing calls to $M_A$ and $M_B$ (both total since $\mathbb{1}_A, \mathbb{1}_B$ are total computable) plus bounded register manipulations. Hence $M_{AB}$ halts on every input — and in fact in time $O(n)$ measured against the cost of $M_A$ and $M_B$.
Correctness: the loop enumerates all $n + 1$ splits of $w$. The flag $\texttt{found}$ ends at $a$ iff some split witnesses $u \in A$ and $v \in B$, which is the defining condition for $w \in AB$; otherwise it stays at $\varepsilon$. Hence the output matches $\mathbb{1}_{AB}(w)$.
The closure properties L1 (composition) and L2 (case distinction) from Step 1, combined with the bounded-iteration construction above (a finite composition of case distinctions, one per loop iteration), confirm that $\mathbb{1}_{AB}$ is total computable.
[/claim]
[guided]
The concatenation case is the only one that requires a substantive idea beyond Boolean combination, so we elaborate.
*Why do all $n + 1$ splits suffice?* By definition, $w \in AB$ means there exist $u \in A$ and $v \in B$ with $w = uv$. The concatenation $uv$ has length $|u| + |v| = |w|$, so $|u| \in \{0, 1, \ldots, |w|\}$. Once $|u| = j$ is fixed, the decomposition $w = uv$ determines $u$ uniquely (the first $j$ letters of $w$) and $v$ uniquely (the last $|w| - j$ letters of $w$). So the finite set of splits — one for each $j \in \{0, 1, \ldots, |w|\}$ — is exhaustive.
*Why does this give a* total *algorithm?* The key point is that the search is over a *finite* set whose size ($|w| + 1$) is a computable function of the input. This is what distinguishes the computable case from the computably-enumerable case (where the search would be over an unbounded candidate space and we would need to dovetail). Here, the indicator $\mathbb{1}_{AB}$ is constructed as a bounded loop; a bounded loop over total sub-routines always halts.
*What if $A$ or $B$ contains $\varepsilon$?* If $\varepsilon \in A$, the split $(j = 0)$ has $u = \varepsilon \in A$ and $v = w$, so $w \in AB$ whenever $w \in B$. This is consistent: $AB \supseteq \{\varepsilon\} B = B$. If $\varepsilon \in B$, the split $(j = n)$ has $v = \varepsilon \in B$ and $u = w$, so $AB \supseteq A \{\varepsilon\} = A$.
The register-machine pseudocode in the claim uses bounded iteration (for $j = 0, 1, \ldots, n$). While the course's formal model sometimes prefers primitive recursion or explicit register transitions, bounded iteration is expressible in both, because one can maintain a countdown register that is decremented from $n$ to $0$ and test for $\varepsilon$ at each step. Each loop body is a finite composition of: prefix/suffix extraction (a word-surgery primitive, implementable by bounded letter-by-letter copying), calls to the given machines $M_A, M_B$ (total by hypothesis), and constant-time tests of register contents against the single letters $a$ and $\varepsilon$. The resulting register machine is total.
*Running total computable functions in sequence.* One subtle point: $M_A$ may clobber scratch registers during its computation. Before calling $M_A$, we save the full input $w$ (and the index $j$ if needed) to fresh scratch registers not used by $M_A$; after $M_A$ halts, we restore them. This is the same save/restore discipline used in Step 2's proof for intersection, and it is needed whenever a computation is composed of multiple sub-computations sharing register space.
[/guided]
Hence $AB$ is computable.
[/step]
[step:Conclude]
Steps 2, 3, 4, 5, and 7 exhibit total computable indicators for $A \cap B$, $A^c$, $A \cup B$, $A \setminus B$, and $AB$ respectively, given total computable indicators for $A$ and $B$. Therefore the class of computable sets is closed under intersection, complement, union, set difference, and (for $k = 1$) concatenation.
[/step]
