[proofplan] The four sets $\operatorname{Emp}$, $\operatorname{Fin}$, $\operatorname{Inf}$, $\operatorname{Tot}$ are each non-trivial index sets, so non-computability follows immediately from [Rice's Theorem](/theorems/1835). The emptiness problem for type 0 grammars is $\operatorname{Emp}$ transported along the computable coding $v \mapsto G_v$ of grammars, so its computability would imply that of $\operatorname{Emp}$ — a contradiction. The equivalence problem $\operatorname{Eq} = \{(w, v) : W_w = W_v\}$ reduces to deciding $\operatorname{Emp}$ via the total computable map $w \mapsto (w, e)$ where $W_e = \varnothing$: the key identity $\mathbb{1}_{\operatorname{Emp}}(w) = \mathbb{1}_{\operatorname{Eq}}(w, e)$ shows that computability of $\operatorname{Eq}$ would yield computability of $\operatorname{Emp}$, again a contradiction. [/proofplan] [step:Fix notation for the four index sets and the coding of grammars] Fix the course alphabet $\Sigma$ with distinguished accept letter $a \in \Sigma$ and write $\mathbb{W} = \Sigma^*$. The course fixes computable codings so that every $v \in \mathbb{W}$ is the code of a register machine (write $W_v = \operatorname{dom} f_{v, 1}$ for its halting set) *and* the code of a type 0 grammar $G_v$. These codings are independent — no relation between the machine with code $v$ and the grammar with code $v$ is assumed — and each coding is surjective from $\mathbb{W}$ onto its target. The four index sets are \begin{align*} \operatorname{Emp} &:= \{v \in \mathbb{W} : W_v = \varnothing\}, \\ \operatorname{Fin} &:= \{v \in \mathbb{W} : W_v \text{ is finite}\}, \\ \operatorname{Inf} &:= \{v \in \mathbb{W} : W_v \text{ is infinite}\}, \\ \operatorname{Tot} &:= \{v \in \mathbb{W} : W_v = \mathbb{W}\}. \end{align*} Each is defined by a condition on $W_v$ alone, so each is closed under weak equivalence $v \sim u \iff W_v = W_u$, i.e. each is an *index set* in the sense of Step 1 of the proof of [Rice's Theorem](/theorems/1835). The two problems about type 0 grammars are \begin{align*} \operatorname{EmpGram} &:= \{w \in \mathbb{W} : \mathcal{L}(G_w) = \varnothing\}, \\ \operatorname{EqGram} &:= \{(w, v) \in \mathbb{W}^2 : \mathcal{L}(G_w) = \mathcal{L}(G_v)\}. \end{align*} A problem is *unsolvable* iff its associated set is not computable. [/step] [step:Show that $\operatorname{Emp}$, $\operatorname{Fin}$, $\operatorname{Inf}$, $\operatorname{Tot}$ are non-trivial] We verify for each set $I \in \{\operatorname{Emp}, \operatorname{Fin}, \operatorname{Inf}, \operatorname{Tot}\}$ that $I \neq \varnothing$ and $I \neq \mathbb{W}$. Fix two explicit codes: - $e \in \mathbb{W}$ is the code of a register machine that loops on every input (as in Step 1 of the proof of [Rice's Theorem](/theorems/1835)), so $W_e = \varnothing$; - $t \in \mathbb{W}$ is the code of a register machine that halts on every input (e.g., the machine with a single halting instruction, which terminates immediately regardless of its input register contents), so $W_t = \mathbb{W}$. With these in hand: - $\operatorname{Emp}$: $e \in \operatorname{Emp}$ (since $W_e = \varnothing$) and $t \notin \operatorname{Emp}$ (since $W_t = \mathbb{W} \neq \varnothing$). So $\operatorname{Emp} \neq \varnothing$ and $\operatorname{Emp} \neq \mathbb{W}$. - $\operatorname{Fin}$: $e \in \operatorname{Fin}$ (since $W_e = \varnothing$ is finite) and $t \notin \operatorname{Fin}$ (since $W_t = \mathbb{W}$ is infinite). So $\operatorname{Fin} \neq \varnothing$ and $\operatorname{Fin} \neq \mathbb{W}$. - $\operatorname{Inf}$: $t \in \operatorname{Inf}$ (since $W_t = \mathbb{W}$ is infinite) and $e \notin \operatorname{Inf}$ (since $W_e = \varnothing$ is not infinite). So $\operatorname{Inf} \neq \varnothing$ and $\operatorname{Inf} \neq \mathbb{W}$. - $\operatorname{Tot}$: $t \in \operatorname{Tot}$ (since $W_t = \mathbb{W}$) and $e \notin \operatorname{Tot}$ (since $W_e = \varnothing \neq \mathbb{W}$). So $\operatorname{Tot} \neq \varnothing$ and $\operatorname{Tot} \neq \mathbb{W}$. Each set is an index set (Step 1) and non-trivial, so by [Rice's Theorem](/theorems/1835) each is not computable. [/step] [step:Show the emptiness problem for type 0 grammars is unsolvable] We must show $\operatorname{EmpGram}$ is not computable. The argument is that $\operatorname{EmpGram}$ is a re-encoding of $\operatorname{Emp}$ along a computable bijection of codings, up to the fact that "type 0 language = computably enumerable set = halting set" and computable enumerability witnesses are interchangeable. Define \begin{align*} \gamma : \mathbb{W} &\to \mathbb{W}, \\ w &\mapsto \operatorname{code-of-register-machine-recognising}(\mathcal{L}(G_w)). \end{align*} Concretely, $\gamma(w)$ is the code of the register machine that, on input $v \in \mathbb{W}$, searches over $u \in \mathbb{W}$ for a derivation code in the grammar $G_w$ producing $v$ (as constructed in Step 2 of the proof of [Type 0 Languages Are Computably Enumerable](/theorems/1827)). [claim:$\gamma$ is total computable and $W_{\gamma(w)} = \mathcal{L}(G_w)$ for every $w \in \mathbb{W}$] Step 2 of the proof of [Type 0 Languages Are Computably Enumerable](/theorems/1827) exhibits, for every type 0 grammar $G$, a register machine $M_G$ of arity $1$ with $\operatorname{dom} f_{M_G, 1} = \mathcal{L}(G)$. Inspecting the construction, the code of $M_G$ is a total computable function of the code of $G$: the steps in its construction — extract the grammar's rules from $\operatorname{code}(G)$, build a simulator that loops over candidate derivation codes and validates each — involve only primitive-recursive manipulations of the grammar's encoding (extracting rules, building a validator, combining simulators). Concretely, the function $w \mapsto \operatorname{code}(M_{G_w})$ is total computable by the standard construction of the universal machine for type 0 derivations (combined with the $s$-$m$-$n$ theorem if one prefers to present the construction as currying). Set $\gamma(w) := \operatorname{code}(M_{G_w})$. Then $W_{\gamma(w)} = \operatorname{dom} f_{\gamma(w), 1} = \mathcal{L}(G_w)$, as required. [/claim] *Reduction.* For every $w \in \mathbb{W}$, \begin{align*} w \in \operatorname{EmpGram} &\iff \mathcal{L}(G_w) = \varnothing \iff W_{\gamma(w)} = \varnothing \iff \gamma(w) \in \operatorname{Emp}. \end{align*} So $\gamma$ is a many-one reduction from $\operatorname{EmpGram}$ to $\operatorname{Emp}$: $\operatorname{EmpGram} \leq_m \operatorname{Emp}$. This reduction goes in the *wrong direction* for transferring non-computability: we need to place the *known* non-computable set on the source and the *target* set on the target, because the implication "$A \leq_m B$ and $B$ computable $\Rightarrow$ $A$ computable" transfers non-computability from the source to the target by contraposition. So we need the reverse reduction, $\operatorname{Emp} \leq_m \operatorname{EmpGram}$. [claim:$\operatorname{Emp} \leq_m \operatorname{EmpGram}$] By [Computably Enumerable Sets Are Type 0 Languages](/theorems/???) (the converse of [Type 0 Languages Are Computably Enumerable](/theorems/1827)), every computably enumerable set is $\mathcal{L}(G)$ for some type 0 grammar $G$, and the construction is uniform: there is a total computable $\delta : \mathbb{W} \to \mathbb{W}$ with $\mathcal{L}(G_{\delta(v)}) = W_v$ for every $v \in \mathbb{W}$. (Concretely, $\delta$ sends the code $v$ of a register machine to the code of a type 0 grammar whose productions simulate $M_v$; see Step 3 of the proof of [Computably Enumerable Sets Are Type 0 Languages](/theorems/???).) Then for every $v \in \mathbb{W}$, \begin{align*} v \in \operatorname{Emp} &\iff W_v = \varnothing \iff \mathcal{L}(G_{\delta(v)}) = \varnothing \iff \delta(v) \in \operatorname{EmpGram}. \end{align*} Hence $\delta$ is a total computable reduction from $\operatorname{Emp}$ to $\operatorname{EmpGram}$. [/claim] By Step 2, $\operatorname{Emp}$ is not computable. If $\operatorname{EmpGram}$ were computable, then $\operatorname{Emp} \leq_m \operatorname{EmpGram}$ together with [Computable Sets Are Downward-Closed Under $\leq_m$](/theorems/???) would force $\operatorname{Emp}$ to be computable — a contradiction. Hence $\operatorname{EmpGram}$ is not computable: the emptiness problem for type 0 grammars is unsolvable. [guided] A brief word on why both $\gamma$ and $\delta$ appear. *Why introduce $\gamma$ at all?* It is cleanest to reason in the world of register machines (where $\operatorname{Emp}$ lives) rather than grammars (where $\operatorname{EmpGram}$ lives), because the sets $\operatorname{Emp}, \operatorname{Fin}, \operatorname{Inf}, \operatorname{Tot}$ are defined in terms of $W_v$. So we want to translate *from* the grammar world *to* the register-machine world. The function $\gamma$ performs this translation: given a grammar code $w$, produce a register-machine code $\gamma(w)$ whose halting set equals the language of the grammar. Its existence is a constructive consequence of [Type 0 Languages Are Computably Enumerable](/theorems/1827). *Why is the reduction direction $\operatorname{Emp} \leq_m \operatorname{EmpGram}$, not the reverse?* Because we want to conclude "$\operatorname{EmpGram}$ is not computable" from "$\operatorname{Emp}$ is not computable". Many-one reducibility transfers *non-computability* from the target to the source (via the contrapositive of downward-closure of computability). So we need the simpler/known set on the source: $\operatorname{Emp}$ (known not computable) reduces to $\operatorname{EmpGram}$ (unknown, deduced not computable). *Why do we need $\delta$ at all?* Because the coding of grammars and the coding of register machines are independent. Given a register-machine code $v$, there is no canonical $w$ with $G_w$ recognising the same language as $M_v$ — we have to *construct* $\delta(v)$ by translating $v$'s register-machine behaviour into grammar productions. This is Step 3 of the proof of [Computably Enumerable Sets Are Type 0 Languages](/theorems/???). *Why are $\gamma$ and $\delta$ both needed in this proof, even though only $\delta$ is used directly?* In fact only $\delta$ is strictly needed; we derived $\gamma$ first to make the link between $\operatorname{EmpGram}$ and $\operatorname{Emp}$ bidirectional (and to record both reductions, which both hold). The forward reduction $\operatorname{EmpGram} \leq_m \operatorname{Emp}$ is used, for example, when one wants to place $\operatorname{EmpGram}$ *below* $\operatorname{Emp}$ in the many-one hierarchy — useful for upper bounds. For non-computability, $\operatorname{Emp} \leq_m \operatorname{EmpGram}$ via $\delta$ is what matters. [/guided] [/step] [step:Show the equivalence problem for type 0 grammars is unsolvable] Define the register-machine analogue of $\operatorname{EqGram}$: \begin{align*} \operatorname{Eq} &:= \{(w, v) \in \mathbb{W}^2 : W_w = W_v\}. \end{align*} We show $\operatorname{Eq}$ is not computable, then transfer the result to $\operatorname{EqGram}$ via $\delta$ (as in Step 3). [claim:$\operatorname{Emp} \leq_m \operatorname{Eq}$] Recall the empty-domain witness $e \in \mathbb{W}$ from Step 2, so $W_e = \varnothing$. Define \begin{align*} \alpha : \mathbb{W} &\to \mathbb{W}^2, \\ w &\mapsto (w, e). \end{align*} *$\alpha$ is total computable.* A register machine $M_\alpha$ takes $w$ in register $0$, copies it to register $0$ (identity, total computable by projection L0 of Step 3 of the proof of [Recursive Implies Computable](/theorems/1817)), and writes the constant $e$ to register $1$ (constant-function computability by L0). Halt. The result is the pair $(w, e)$; pairing is a total computable primitive (L2 of Step 4 of the proof of [Recursive Implies Computable](/theorems/1817)). Hence $\alpha$ is total computable. *Reduction.* For every $w \in \mathbb{W}$, \begin{align*} w \in \operatorname{Emp} &\iff W_w = \varnothing \iff W_w = W_e \iff (w, e) \in \operatorname{Eq} \iff \alpha(w) \in \operatorname{Eq}. \end{align*} Hence $\alpha$ reduces $\operatorname{Emp}$ to $\operatorname{Eq}$. [/claim] Equivalently, writing $\mathbb{1}$ for indicators of the respective sets, \begin{align*} \mathbb{1}_{\operatorname{Emp}}(w) &= \mathbb{1}_{\operatorname{Eq}}(\alpha(w)) = \mathbb{1}_{\operatorname{Eq}}(w, e). \end{align*} By Step 2, $\operatorname{Emp}$ is not computable. If $\operatorname{Eq}$ were computable, then $\operatorname{Emp} \leq_m \operatorname{Eq}$ together with [Computable Sets Are Downward-Closed Under $\leq_m$](/theorems/???) would force $\operatorname{Emp}$ to be computable — a contradiction. Hence $\operatorname{Eq}$ is not computable. *Transfer to grammars.* The same function $\delta$ from Step 3 converts $\operatorname{Eq}$ into $\operatorname{EqGram}$ coordinate-wise. Define \begin{align*} \beta : \mathbb{W}^2 &\to \mathbb{W}^2, \\ (w, v) &\mapsto (\delta(w), \delta(v)). \end{align*} $\beta$ is total computable (coordinate application of the total computable $\delta$, combined by pairing — L1, L2). For every $(w, v) \in \mathbb{W}^2$, \begin{align*} (w, v) \in \operatorname{Eq} &\iff W_w = W_v \iff \mathcal{L}(G_{\delta(w)}) = \mathcal{L}(G_{\delta(v)}) \iff \beta(w, v) \in \operatorname{EqGram}. \end{align*} Hence $\operatorname{Eq} \leq_m \operatorname{EqGram}$. By the same downward-closure argument, $\operatorname{EqGram}$ is not computable: the equivalence problem for type 0 grammars is unsolvable. [guided] The structure of the equivalence-problem argument is a two-step reduction: $\operatorname{Emp} \leq_m \operatorname{Eq} \leq_m \operatorname{EqGram}$. *Why introduce $\operatorname{Eq}$ as an intermediary?* Because the natural argument — "equivalence is hard because emptiness is hard, and emptiness is a special case of equivalence (equivalence with the empty-language code)" — lives purely in the register-machine world. The map $w \mapsto (w, e)$ is the simplest possible reduction: pair the input with a fixed empty witness. This move uses only one fact: that *some* code $e$ with $W_e = \varnothing$ exists. The grammar world is then reached by applying $\delta$ coordinate-wise. *Why not reduce $\operatorname{Emp}$ directly to $\operatorname{EqGram}$?* We could: compose $\delta$ with $\alpha$. The composition would be $w \mapsto (\delta(w), \delta(e))$, which is total computable and witnesses $\operatorname{Emp} \leq_m \operatorname{EqGram}$ directly. The two-step presentation is for bookkeeping — it records the intermediate fact that the register-machine equivalence problem is itself undecidable, which is independently interesting. *Why does $\operatorname{Emp} \leq_m \operatorname{Eq}$ follow from such a simple reduction?* Because $\operatorname{Emp}$ is *exactly* the slice of $\operatorname{Eq}$ at the second coordinate $v = e$: $w \in \operatorname{Emp} \iff W_w = W_e \iff (w, e) \in \operatorname{Eq}$. The reduction $\alpha : w \mapsto (w, e)$ is the "slice" map, and slice maps always witness that a slice-defined set reduces to the original. *Remark on a stronger result alluded to in the course.* One can strengthen $\operatorname{Emp} \leq_m \mathbb{W} \setminus \mathbb{K}$ to $\operatorname{Emp} \equiv_m \mathbb{W} \setminus \mathbb{K}$ — meaning $\operatorname{Emp}$ and $\mathbb{W} \setminus \mathbb{K}$ are *many-one equivalent*, both $\Pi_1$-complete. That result is stated in the course notes but not proven here; its proof uses the full $s$-$m$-$n$ machinery. It is in fact Case 1 of [Rice's Theorem](/theorems/1835) applied to $I = \operatorname{Emp}$, which gives the $\leq_m$ direction we use; the reverse direction is standard. [/guided] [/step] [step:Conclude] Step 2 establishes that $\operatorname{Emp}$, $\operatorname{Fin}$, $\operatorname{Inf}$, $\operatorname{Tot}$ are non-computable, by direct application of [Rice's Theorem](/theorems/1835) to each (each is a non-trivial index set). Step 3 establishes that the emptiness problem $\operatorname{EmpGram}$ for type 0 grammars is unsolvable, by the reduction $\operatorname{Emp} \leq_m \operatorname{EmpGram}$ via the grammar-encoding $\delta$. Step 4 establishes that the equivalence problem $\operatorname{EqGram}$ is unsolvable, via the chain of reductions $\operatorname{Emp} \leq_m \operatorname{Eq} \leq_m \operatorname{EqGram}$. In each case, the key fact is that many-one reducibility transfers non-computability from the source to the target (equivalently, computability is $\leq_m$-downward-closed). [/step]