Decidable, Recognizable, and Enumerable Languages

Assume first that $L$ is c.e. If $L=\mathrm{\varnothing }$, then the machine that immediately rejects every input recognizes $L$. Otherwise choose a total computable enumerator $e:\mathbb{N}\to \{0,1{\}}^{\ast }$ with range $L$ as in [L2]. On input $x$, search through $n=0,1,2,\dots$ and compute $e(n)$ until $e(n)=x$; if this occurs, accept. For $x\in L$ the search eventually finds a witness $n$, and for $x\mathrm{\notin }L$ it never accepts. Thus $L$ is recognizable by [L1].

Assume conversely that $L$ is recognizable. If $L=\mathrm{\varnothing }$, then [L2] already says that $L$ is c.e. So assume $L\mathrm{\ne }\mathrm{\varnothing }$, and let $M$ be a recognizer for $L$. By dovetailing the simulations of $M$ over binary words in shortlex order, fix one accepted word $a_0\in L$.

Fix a standard total computable bijection $n\mapsto (i,t)$ from $\mathbb{N}$ onto $\mathbb{N}\times \mathbb{N}$, and let $w_i$ be the $i$th binary word in shortlex order. Define $e(n):=\{\begin{array}{ll}{w}_i,& \text{if }M\text{ accepts }{w}_i\text{ within }t\text{ steps},\\ a_0,& \text{otherwise.}\end{array}$ This is a total computable function $\mathbb{N}\to \{0,1{\}}^{\ast }$. Every output of $e$ lies in $L$, and if $w\in L$ then $w=w_i$ for some $i$ and $M$ accepts $w_i$ in some finite number of steps $t$, so $e(n)=w$ for the paired input with coordinates $(i,t)$. Hence the range of $e$ is exactly $L$, so [L2] shows that $L$ is c.e.

Steps 1.1 and 2.1 prove the equivalence.

If $L$ is decidable, then a decider for $L$ is already a recognizer for $L$, and swapping its accepting and rejecting halting states gives a recognizer for $L^c$. Thus item 1 implies item 2 by [L1] and [L2].

Assume $M$ recognizes $L$ and $N$ recognizes $L^c$. On input $w$, simulate one step of $M$, then one step of $N$, then two steps of each, and so on. If $M$ accepts at some stage, accept; if $N$ accepts at some stage, reject. Because every word lies in exactly one of $L$ and $L^c$, exactly one machine must eventually accept, so this interleaving always halts with the correct answer. Therefore $L$ is decidable by [L1].

Steps 1.1 and 1.2 prove both directions.

Let $M_L$ recognize $L$ and $M_K$ recognize $K$. To recognize $L\cup K$, interleave their computations on an input $w$ and accept as soon as either machine accepts. If $w\in L\cup K$, one of the recognizers eventually accepts; if $w\mathrm{\notin }L\cup K$, neither does. Hence $L\cup K$ is recognizable by [L1] and [L2].

To recognize $L\cap K$, again interleave the two computations on $w$, but now record whether each machine has accepted and halt only once both accept. If $w\in L\cap K$, both accepting events occur after finitely many stages; if $w\mathrm{\notin }L\cap K$, at least one machine never accepts, which is allowed for a recognizer. Thus $L\cap K$ is recognizable.

Therefore recognizable languages are closed under union and intersection.

If $M_L$ decides $L$, then flipping its final yes-or-no answer gives a halting decider for $L^c$. If $M_L$ and $M_K$ decide $L$ and $K$, run both and combine their two halting answers by the ordinary Boolean truth tables to decide $L\cup K$ and $L\cap K$.

By [A1], the same deciders decide $L\setminus K$ as $L\cap K^c$ and decide $L\mathrm{△}K$ as $(L\setminus K)\cup (K\setminus L)$. Because each constituent operation from step 1.1 preserves halting, these languages are decidable as well.

Therefore decidable languages are closed under all five stated Boolean operations.

Fix $(i,t)\in {\mathbb{N}}^2$ and set $s:=i+t$. Then the defining condition for $S_s$ is satisfied, so [L1] gives $(i,t)\in S_s$.

Therefore the task with index $i$ is run through its local time $t$ by the finite global stage $s=i+t$. This is exactly the claimed fairness property.

Let $E_D:=\{e_X(x):x\in D\}\subseteq \{0,1{\}}^{\ast }$. On an input word $z\in \{0,1{\}}^{\ast }$, run the computable decoder from the given data for the input encoding of $X$. If $z$ is malformed, diverge forever. If $z=e_X(x)$ is valid, simulate the machine from [L1] on the same word $z$ and accept exactly when that simulation halts. This recognizes exactly the binary language $E_D$, so [L2] makes $E_D$ computably enumerable. Since $E_D$ consists exactly of the codes of elements of $D$, the same enumeration viewed through the fixed encoding $e_X$ witnesses that $D$ is computably enumerable as a subset of $X$.

Let $E_R:=\{e_Y(y):y\in f[D]\}\subseteq \{0,1{\}}^{\ast }$. On an input word $z\in \{0,1{\}}^{\ast }$, dovetail the following branches over all binary words $w$ in shortlex order: first run the computable decoder for the input encoding of $X$ on $w$, and discard the branch if $w$ is malformed; otherwise simulate the machine from [L1] on $w$. Accept as soon as some valid input code halts with output $z$. If $z=e_Y(f(x))$ for some $x\in D$, then [L3] ensures that the halting computation on the valid code $e_X(x)$ is eventually reached, so the recognizer accepts. If $z\mathrm{\notin }{E}_R$, no valid branch can witness acceptance. Thus $E_R$ is recognizable, [L2] makes it computably enumerable as a binary language, and therefore $f[D]$ is computably enumerable as a subset of $Y$.

Therefore both the domain and the range of a partial computable function are computably enumerable.

If $A=\mathrm{\varnothing }$, take the nowhere-defined partial function from $X$ to the one-point set $\{0\}$. Its machine diverges on every input, so [L2] shows that its domain is exactly $\mathrm{\varnothing }=A$.

Suppose now that $A\mathrm{\ne }\mathrm{\varnothing }$, and let $e:\mathbb{N}\to X$ be the total computable enumerator from [L1]. Define a machine on an input code $z\in \{0,1{\}}^{\ast }$ that computes the outputs $e(0),e(1),e(2),\dots$ one after another until it first sees the codeword $z$, at which point it halts and outputs $0$. If $z=e_X(x)$ with $x\in A$, some index $n$ satisfies $e(n)=x$, so the machine eventually halts on $z$. If $x\mathrm{\notin }A$, no enumerated value has code $z$, so the machine never halts on $z$. Thus [L2] gives a partial computable function whose domain is exactly $A$.

In either case, $A$ is the domain of a partial computable function.

By [L1], choose a total computable enumerator $e:\mathbb{N}\to X$ with range exactly $A$, and let $E$ be a machine as in [L2] that computes it. On input $n$, simulate the computations of $E$ on $0,1,2,\dots$ one after another, keep the list of distinct output codewords already seen, and halt when the $(n+1)$st new codeword appears, outputting that codeword.

The resulting function $g:\mathbb{N}\to X$ is injective by construction, because each output is the next codeword not seen before. Every value of $g$ lies in $A$ because every output of $E$ lies in the range of $e$. Conversely, if $x\in A$, then some stage of the sequential scan in step 1.1 encounters the codeword $e_X(x)$ among the outputs of $E$, so that codeword is eventually appended to the distinct-output list. Hence the range of $g$ is exactly $A$.

Because $A$ is infinite, for each $n$ there are at least $n+1$ distinct elements of $A$. Step 2.1 shows that each of their codewords appears somewhere in the scan from step 1.1, so the $(n+1)$st new codeword is found after finitely many outputs of $E$. Therefore the machine of step 1.1 halts on every input $n$, and it computes a total injective function $g:\mathbb{N}\to X$ with range $A$.

Thus every infinite c.e. set has a computable injective enumeration.

On input a binary word $w$, run the total decoder from [L1]. If it reports malformed input, reject; if it returns a coded machine, accept. Because the decoder is total, this procedure halts on every input.

The procedure accepts exactly those binary words that decode to well-formed deterministic one-tape Turing machine descriptions. Therefore [L2] shows that the description language is decidable.

Let $M$ be the machine that accepts immediately on input 0 and otherwise moves right forever without entering any halting state. Then $M$ accepts exactly the one-word language $\{0\}$.

On every nonmember of $\{0\}$, the machine from step 1.1 diverges. So $M$ recognizes $\{0\}$ but does not halt on every input.

Therefore recognizability does not force total halting, and the statement is false.

The set $\{1{\}}^{\ast }$ is countable by length, so write its elements as $w_n:=1^n$ for $n\ge 0$. Filter the effective list from [L2] by keeping only the coded machines whose input-alphabet parameter satisfies $s\ge 1$; by [L4], this gives an effective enumeration $N_0,N_1,N_2,\dots$ of all coded deterministic one-tape machines that can read every unary word. Let $D:=\{w_n:N_n\text{ does not accept }{w}_n\}$. By [L1], the language $D$ is countable because it is a subset of the countable set $\{1{\}}^{\ast }$.

Suppose a decider decides $D$. By [F1], an equivalent coded decider occurs as some $N_k$ in the filtered enumeration. If $w_k\in D$, then step 1.1 says that $N_k$ does not accept $w_k$, contradicting the requirement that a decider for $D$ accept members. If $w_k\mathrm{\notin }D$, then step 1.1 says that $N_k$ accepts $w_k$, contradicting the requirement that a decider reject nonmembers.

Thus no decider decides the countable language $D$, so the statement is false.