In this chapter, we formally prove that almost all languages are undecidable using the countability and uncountability concepts from a previous chapter. We also present (with proofs) several explicit examples of undecidable languages. By the Church-Turing Thesis, these results highlight the inherent limitations of computation.
An important tool in showing that a language is undecidable is the concept of a reduction. We present this technique in this chapter. Reductions play an extremely important role in computer science. In fact, we will revisit them in a future chapter (in the context of the famous \(\mathsf{P}\) vs \(\mathsf{NP}\) problem.)
Our goal in this chapter is for you to get comfortable with undecidability proofs and the concept of reductions, as they are at the core of the study of computation.
Fix some input alphabet and tape alphabet. The set of all Turing machines \(\mathcal{T}= \{M : M \text{ is a TM}\}\) is countable.
We will show \(\mathcal{T}\) is countable by showing it is encodable.
First, based on Remark (Equivalence of Turing machines), we will normalize TMs and assume the set of states \(Q\) is always \(\{0,1,2,\ldots, k-1\} \cup \{q_\text{acc},q_\text{rej}\}\) for some \(k \in \mathbb N\). Then given any Turing machine, there is a way to encode it with a finite length string because each component of the \(7\)-tuple has a finite description. In particular, the mapping \(M \mapsto \left \langle M \right\rangle\), where \(\left \langle M \right\rangle \in \Sigma^*\), for some finite alphabet \(\Sigma\), is an injective map (two distinct Turing machines cannot have the same encoding).
Fix some alphabet \(\Sigma\). There are languages \(L \subseteq \Sigma^*\) that are not semi-decidable (and therefore undecidable as well).
To prove the result, we simply observe that the set of all languages is uncountable whereas the set of semi-decidable languages is countable. First, consider the set of all languages. Since a language \(L\) is defined to be a subset of \(\Sigma^*\), the set of all languages is \(\wp(\Sigma^*)\). By Corollary (The power set of an infinite set is uncountable), we know that this set is uncountable. Now consider the set of all semi-decidable languages over \(\Sigma\), which we’ll denote by \(\mathcal{S}\). Let \(\mathcal{T}\) be the set of all TMs. By Proposition (The set of Turing machines is countable), we know that \(\mathcal{T}\) is countable. Furthermore, the mapping \(M \mapsto L(M)\) can be viewed as a surjection from \(\mathcal{T}\) to \(\mathcal{S}\). So \(|\mathcal{S}| \leq |\mathcal{T}|\). Since \(\mathcal{T}\) is countable, this shows \(\mathcal{S}\) is countable and completes the proof.
The argument above is called non-constructive because it does not present an explicit undecidable language. A constructive argument would prove the undecidability of an explicit language. We present such an argument below.
Recall Important Note (Diagonalization gives an explicit construction). Since our goal in this section is to find an explicit undecidable language, it is natural to consider applying Lemma (Diagonalization). And indeed, we can diagonalize against the set of all decidable languages, or equivalently, diagonalize against the set \(\mathcal{D}\) of all decidable decision problems \(f: \Sigma^* \to \{0,1\}\). This gives us an explicit decision problem, \(f_D\), that is undecidable. The reason we can apply diagonalization is because \(\mathcal{D}\) is an encodable set, as we have seen in the proof of Theorem (Almost all languages are undecidable). Therefore \(|\Sigma^*| \geq |\mathcal{D}|\), which means the condition to apply diagonalization is satisfied.
In the previous chapter, we presented diagonalization with respect to a set of functions. However, Lemma (Diagonalization) can be applied in a slightly more general setting: it can be applied when \(\mathcal{F}\) is a set of objects that map elements of \(X\) to elements of \(Y\) (e.g. \(\mathcal{F}\) can be a set of Turing machines which map elements of \(\Sigma^*\) to elements of \(\{0,1,\infty\}\)). In other words, elements of \(\mathcal{F}\) do not have to be functions as long as they are “function-like”. Once diagonalization is applied, one gets an explicit function \(f_D : X \to Y\) such that no object in \(\mathcal{F}\) matches the input/output behavior of \(f_D\). We will illustrate this in the proof of the next theorem.
We say that a TM \(M\) self-accepts if \(M(\left \langle M \right\rangle) = 1\). The self-accepts problem is defined as the decision problem corresponding to the language \[\text{SA}_{\text{TM}}= \text{SELF-ACCEPTS}_{\text{TM}}= \{\left \langle M \right\rangle : \text{$M$ is a TM which self-accepts} \}.\] The complement problem corresponds to the language \[\overline{\text{SA}_{\text{TM}}}= \overline{\text{SELF-ACCEPTS}_{\text{TM}}}= \{\left \langle M \right\rangle : \text{$M$ is a TM which does not self-accept}\}.\] Note that if a TM \(M\) does not self-accept, then \(M(\left \langle M \right\rangle) \in \{0, \infty\}\).
The language \(\overline{\text{SA}_{\text{TM}}}\) is undecidable.
Our goal is to show that \(\overline{\text{SA}_{\text{TM}}}\) is undecidable. To accomplish this, we can either diagonalize against the set of all decidable decision problems or we can diagonalize against the set of all TMs. To illustrate Note (Diagonalization against a set of function-like objects), we will choose the second option and observe that the decision problem corresponding to \(\overline{\text{SA}_{\text{TM}}}\) is (arguably) the most natural diagonal element that the diagonalization spits out.
Recall that a decision problem \(f:\Sigma^* \to \{0,1\}\) is decidable if there is a TM \(M\) whose input/output behavior matches \(f\), that is, for all \(x \in \Sigma^*\), \(M(x) = f(x)\).
Now let \(\mathcal{F}\) denote the set of all Turing machines. A Turing machine maps elements of \(X = \Sigma^*\) to an element of \(Y = \{0,1,\infty\}\). Since the set of all Turing machines is countably infinite and \(X\) is countably infinite, we have \(|X| = |\mathcal{F}|\). Therefore we can diagonalize against \(\mathcal{F}\) to construct \(f_D : X \to Y\) that cannot correspond to any Turing machine. If we choose \(f_D\) in a way such that the range is \(\{0,1\}\), then \(f_D\) will be an undecidable decision problem.
To explicitly define \(f_D\), we pick an injection from \(\mathcal{F}\) to \(X = \Sigma^*\). The most obvious one is \(M \mapsto \left \langle M \right\rangle\). Then let \[f_D(\left \langle M \right\rangle) = \begin{cases} 1 & \text{if $M(\left \langle M \right\rangle) \in \{0, \infty\}$\; (i.e. $M(\left \langle M \right\rangle)$ does not accept);} \\ 0 & \text{otherwise.} \end{cases}\]
By construction, any TM \(M\) differs from \(f_D\) on input \(\left \langle M \right\rangle\), i.e. for all TMs \(M\), \(M(\left \langle M \right\rangle) \neq f_D(\left \langle M \right\rangle)\). Therefore \(f_D\) is not decidable by any TM.
Observe that the language corresponding to the decision problem \(f_D\) is precisely \(\overline{\text{SA}_{\text{TM}}}\).
Note that the proof of the above theorem establishes something stronger: the language \(\overline{\text{SA}_{\text{TM}}}\) is not semi-decidable. To see this, recall that if \(M\) is a semi-decider for \(f_D\), by definition, this implies that for all \(x \in \Sigma^*\):
if \(f_D(x) = 1\), then \(M(x) = 1\),
if \(f_D(x) = 0\), then \(M(x) \in \{0, \infty\}\).
However, by construction of \(f_D\), we know that for input \(x = \left \langle M \right\rangle\), if \(f_D(\left \langle M \right\rangle) = 1\) then \(M(\left \langle M \right\rangle) \in \{0, \infty\}\), and if \(f_D(\left \langle M \right\rangle) = 0\), then \(M(\left \langle M \right\rangle) = 1\). So for all TMs \(M\), \(M\) fails to semi-decide \(f_D\) on input \(x = \left \langle M \right\rangle\).
The language \(\text{SA}_{\text{TM}}\) is undecidable.
We want to show that \(\text{SA}_{\text{TM}}\) is undecidable. The proof is by contradiction, so assume \(\text{SA}_{\text{TM}}\) is decidable and let \(M_{\text{SA}}\) be a decider for it. We will use this decider to come up with a decider for \(\overline{\text{SA}_{\text{TM}}}\). Since \(\overline{\text{SA}_{\text{TM}}}\) is undecidable (Turing’s 1st Undecidability Theorem), this argument will allow us to reach a contradiction.
Here is our decider for \(\overline{\text{SA}_{\text{TM}}}\): \[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_{\overline{\text{SA}}}(\left \langle \text{TM } M \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Run $M_{\text{SA}}(\left \langle M \right\rangle)$.}\\ &{\scriptstyle 2.}~~~~\texttt{If it accepts, reject.}\\ &{\scriptstyle 3.}~~~~\texttt{If it rejects, accept.}\\ \hline\hline\end{aligned}\] Given our assumption that \(M_{\text{SA}}\) is a correct decider for \(\text{SA}_{\text{TM}}\), it is clear that \(M_{\overline{\text{SA}}}\) is a correct decider for \(\overline{\text{SA}_{\text{TM}}}\). In particular, if the input \(\left \langle M \right\rangle\) is such that \(M\) self-accepts, then \(M_{\text{SA}}(\left \langle M \right\rangle)\) would accept, and our machine would reject on line 2. And if the input \(\left \langle M \right\rangle\) is such that \(M\) does not self-accept, \(M_{\text{SA}}(\left \langle M \right\rangle)\) would reject, and our machine would accept on line 3. So for all possible inputs, our decider gives the correct answer.
The general principle that the above theorem highlights is that since decidable languages are closed under complementation, if \(L\) is an undecidable language, then \(\overline{L} = \Sigma^* \setminus L\) must also be undecidable.
We define the following languages: \[\begin{aligned} \text{ACCEPTS}_{\text{TM}}& = \{\left \langle M,x \right\rangle : \text{$M$ is a TM which accepts input $x$}\}, \\ \text{HALTS}_{\text{TM}}& = \{\left \langle M,x \right\rangle : \text{$M$ is a TM which halts on input $x$} \}, \\ \end{aligned}\]
The language \(\text{ACCEPTS}_{\text{TM}}\) is undecidable.
We want to show that \(\text{ACCEPTS}_{\text{TM}}\) is undecidable. The proof is by contradiction, so assume \(\text{ACCEPTS}_{\text{TM}}\) is decidable and let \(M_{\text{ACCEPTS}}\) be a decider for it. We will use this decider to come up with a decider for \(\text{SA}_{\text{TM}}\). We have already proved Theorem (\(\text{SA}_{\text{TM}}\) is undecidable), so this argument will allow us to reach a contradiction.
Here is our decider for \(\text{SA}_{\text{TM}}\): \[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_{\text{SA}}(\left \langle \text{TM } M \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Run $M_{\text{ACCEPTS}}(\left \langle M, \left \langle M \right\rangle \right\rangle)$.}\\ &{\scriptstyle 2.}~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 3.}~~~~\texttt{If it rejects, reject.}\\ \hline\hline\end{aligned}\] Given our assumption that \(M_{\text{ACCEPTS}}\) is a correct decider for \(\text{SA}_{\text{TM}}\), it is clear that \(M_{\text{SA}}\) is a correct decider for \(\text{SA}_{\text{TM}}\). In particular, if the input \(\left \langle M \right\rangle\) is such that \(M\) self-accepts, then \(M_{\text{ACCEPTS}}(\left \langle M, \left \langle M \right\rangle \right\rangle)\) would accept, and our machine would accept on line 2. And if the input \(\left \langle M \right\rangle\) is such that \(M\) does not self-accept, \(M_{\text{ACCEPTS}}(\left \langle M, \left \langle M \right\rangle \right\rangle)\) would reject, and our machine would reject on line 3. So for all possible inputs, our decider gives the correct answer.
The language \(\text{HALTS}_{\text{TM}}\) is undecidable.
We want to show that \(\text{HALTS}_{\text{TM}}\) is undecidable. The proof is by contradiction, so assume \(\text{HALTS}_{\text{TM}}\) is decidable and let \(M_{\text{HALTS}}\) be a decider for it. We will use this decider to come up with a decider for \(\text{ACCEPTS}_{\text{TM}}\). We have already proved Theorem (\(\text{ACCEPTS}_{\text{TM}}\) is undecidable), so this argument will allow us to reach a contradiction.
At a high level, if we wanted to come up with a TM solving \(\text{ACCEPTS}_{\text{TM}}\), on input \(\left \langle M, x \right\rangle\), we could just try running \(M(x)\) and return its answer. Unfortunately, this simple strategy does not work because \(M(x)\) can possibly loop forever, so we would not end up with a decider solving \(\text{ACCEPTS}_{\text{TM}}\). That being said, we are assuming we have access to a correct decider for \(\text{HALTS}\), namely \(M_{\text{HALTS}}\). So then we can first check if \(M(x)\) halts or not. If it does not, we know \(M(x)\) does not accept, so we can reject. If it does halt, then it is safe to run \(M(x)\). We know it will accept or reject, and so we can return its answer.
Here is the description of our decider for \(\text{ACCEPTS}_{\text{TM}}\): \[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_{\text{ACCEPTS}}(\left \langle \text{TM } M, \; \text{string } x \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Run $M_{\text{HALTS}}(\left \langle M, x \right\rangle)$.}\\ &{\scriptstyle 2.}~~~~\texttt{If it rejects, reject.}\\ &{\scriptstyle 3.}~~~~\texttt{Else:}\\ &{\scriptstyle 4.}~~~~~~~~\texttt{Run $M(x)$.}\\ &{\scriptstyle 5.}~~~~~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 6.}~~~~~~~~\texttt{If it rejects, reject.}\\ \hline\hline\end{aligned}\]
We have basically argued that this decider is correct in our high-level description of the machine. But nevertheless, we’ll lay out the detailed argument here.
To show that \(M_{\text{ACCEPTS}}\) is a correct decider, we need to argue that for all possible inputs, it gives the correct answer.
First let’s assume the input \(\left \langle M,x \right\rangle\) is such that \(M(x)\) accepts. Then on line 1, \(M_{\text{HALTS}}\) will accept, meaning we will not reject on line 2. Then in line 4, \(M(x)\) will accept. And therefore our machine will accept on line 5, as desired.
Next, let’s assume the input \(\left \langle M,x \right\rangle\) is such that \(M(x)\) does not self-accept. There are two possible cases for this: either \(M(x)\) loops, or \(M(x)\) rejects.
In the first case, \(M(x)\) loops. Then \(M_{\text{HALTS}}(\left \langle M, x \right\rangle)\) on line 1 would reject, and therefore our machine would reject on line 2, giving the correct answer.
In the second case, \(M(x)\) rejects. Then \(M_{\text{HALTS}}(\left \langle M, x \right\rangle)\) on line 1 would accept, meaning we would not reject on line 2. Afterwards, on line 4, \(M(x)\) would reject. So our machine would reject on line 6 and give the correct answer.
We have shown that for all possible inputs, \(M_{\text{ACCEPTS}}\) gives the correct answer, which completes the proof of correctness.
The languages \(\text{SA}_{\text{TM}}\), \(\text{ACCEPTS}_{\text{TM}}\), and \(\text{HALTS}_{\text{TM}}\) are all semi-decidable, i.e., they are all in \(\mathsf{RE}\).
Here are Turing machines that semi-decide \(\text{SA}_{\text{TM}}\), \(\text{ACCEPTS}_{\text{TM}}\), and \(\text{HALTS}_{\text{TM}}\) respectively. It pretty much follows directly from the definition of semi-decidability that they are correct, and therefore we omit explicitly spelling out the correctness proofs.
\[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_\text{SA}(\left \langle \text{TM } M \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Run $M(\left \langle M \right\rangle)$.}\\ &{\scriptstyle 2.}~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 3.}~~~~\texttt{If it rejects, reject.}\\ \hline\hline\end{aligned}\]
\[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_\text{ACCEPTS}(\left \langle \text{TM } M, \; \text{string } x \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Run $M(x)$.}\\ &{\scriptstyle 2.}~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 3.}~~~~\texttt{If it rejects, reject.}\\ \hline\hline\end{aligned}\]
\[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_\text{HALTS}(\left \langle \text{TM } M, \; \text{string } x \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Run $M(x)$.}\\ &{\scriptstyle 2.}~~~~\texttt{If it accepts or rejects, accept.}\\ \hline\hline\end{aligned}\]
The languages \(\text{SA}_{\text{TM}}\), \(\text{ACCEPTS}_{\text{TM}}\), and \(\text{HALTS}_{\text{TM}}\) are all in \(\mathsf{RE}\) but not in \(\mathsf{R}\).
In the last section, we have used the same technique in all the proofs. It will be convenient to abstract away this technique and give it a name. Fix some alphabet \(\Sigma\). Let \(L\) and \(K\) be two languages. We say that \(L\) reduces to \(K\), written \(L \leq K\), if we are able to do the following: assume \(K\) is decidable (for the sake of argument), and then show that \(L\) is decidable by using the decider for \(K\) as a black-box subroutine (i.e. a helper function). Here the languages \(L\) and \(K\) may or may not be decidable to begin with. But observe that if \(L \leq K\) and \(K\) is decidable, then \(L\) is also decidable. Or in other words, if \(L \leq K\) and \(K \in \mathsf{R}\), then \(L \in \mathsf{R}\). Equivalently, taking the contrapositive, if \(L \leq K\) and \(L\) is undecidable, then \(K\) is also undecidable. So when \(L \leq K\), we think of \(K\) as being at least as hard as \(L\) with respect to decidability (or that \(L\) is no harder than \(K\)), which justifies using the less-than-or-equal-to sign.
Even though in the diagram above we have drawn one instance of \(M_K\) being called within \(M_L\), \(M_L\) is allowed to call \(M_K\) multiple times with different inputs.
In the literature, the above idea is formalized using the notion of a Turing reduction (with the corresponding symbol \(\leq_T\)). In order to define it formally, we need to define Turing machines that have access to an oracle. See Section (Bonus: Oracle Turing Machines) for details.
The proofs of Theorem (\(\text{SA}_{\text{TM}}\) is undecidable), Theorem (\(\text{ACCEPTS}_{\text{TM}}\) is undecidable), and Theorem (\(\text{HALTS}_{\text{TM}}\) is undecidable) correspond to \[\begin{aligned} \overline{\text{SA}_{\text{TM}}}& \leq \text{SA}_{\text{TM}}, \\ \text{SA}_{\text{TM}}& \leq \text{ACCEPTS}_{\text{TM}}, \\ \text{ACCEPTS}_{\text{TM}}& \leq \text{HALTS}_{\text{TM}}. \end{aligned}\]
Many reductions \(L \leq K\) have the following very special structure. The TM \(M_L\) is such that on input \(x\), it first transforms \(x\) into a new string \(y = f(x)\) by applying some computable transformation \(f\). Then \(f(x)\) is fed into \(M_K\). The output of \(M_L\) is the same as the output of \(M_K\). In other words \(M_L(x) = M_K(f(x))\).
These special kinds of reductions are called mapping reductions (or many-one reductions), with the corresponding notation \(L \leq_m K\). Note that the reduction we have seen from \(\text{SA}_{\text{TM}}\) to \(\text{ACCEPTS}_{\text{TM}}\) is a mapping reduction, as well as the reduction from \(\text{ACCEPTS}_{\text{TM}}\) to \(\text{HALTS}_{\text{TM}}\). However, the reduction from \(\overline{\text{SA}_{\text{TM}}}\) to \(\text{SA}_{\text{TM}}\) is not a mapping reduction because the output of \(M_K\) is flipped, or in other words, we have \(M_L(x) = \textbf{not } M_K(f(x))\).
Almost all the reductions in this section will be mapping reductions.
Note that to specify a mapping reduction from \(L\) to \(K\), all one needs to do is specify a TM \(M_f\) that computes \(f : \Sigma^* \to \Sigma^*\) with the property that for any \(x \in \Sigma^*\), \(x \in L\) if and only if \(f(x) \in K\).
The language \(\text{SAT}_{\text{TM}}\) is undecidable.
We want to show that \(\text{SAT}_{\text{TM}}\) is undecidable. We will do so by reducing a known undecidable language to \(\text{SAT}_{\text{TM}}\). In particular, we will show that \(\text{ACCEPTS}_{\text{TM}}\leq \text{SAT}_{\text{TM}}\). To carry out this reduction, assume \(\text{SAT}_{\text{TM}}\) is decidable and let \(M_{\text{SAT}}\) be a decider for it. Using this decider, we will construct a decider for \(\text{ACCEPTS}_{\text{TM}}\) to establish the reduction.
We construct a TM that decides \(\text{ACCEPTS}_{\text{TM}}\) as follows.
\[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_{\text{ACCEPTS}}(\left \langle \text{TM } M, \; \text{string } x \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Construct the following string, which we call $\left \langle M' \right\rangle$.}\\ &{\scriptstyle 2.}~~~~\texttt{"def $M'(y)$:}\\ &{\scriptstyle 3.}~~~~~~~~\texttt{Run $M(x)$.}\\ &{\scriptstyle 4.}~~~~~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 5.}~~~~~~~~\texttt{If it rejects, reject."}\\ &{\scriptstyle 6.}~~~~\texttt{Run $M_{\text{SAT}}(\left \langle M' \right\rangle)$.}\\ &{\scriptstyle 7.}~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 8.}~~~~\texttt{If it rejects, reject.}\\ \hline\hline\end{aligned}\]
We now argue that this machine indeed decides \(\text{ACCEPTS}_{\text{TM}}\). To do this, we’ll show that no matter what input is given to our machine, it always gives the correct answer.
First let’s assume we get an input \(\left \langle M,x \right\rangle\) such that \(\left \langle M,x \right\rangle \in \text{ACCEPTS}_{\text{TM}}\), i.e. \(x \in L(M)\). Then observe that \(L(M') = \Sigma^*\), because for any input \(y\), \(M'(y)\) will accept. When we run \(M_\text{SAT}(\left \langle M' \right\rangle)\) on line 6, it accepts, and so our machine accepts and gives the correct answer.
Now assume that we get an input \(\left \langle M,x \right\rangle\) such that \(\left \langle M,x \right\rangle \not \in \text{ACCEPTS}_{\text{TM}}\), i.e. \(x \not \in L(M)\). Then either \(M(x)\) rejects, or loops forever. If it rejects, then \(M'(y)\) rejects for any \(y\). If it loops forever, then \(M'(y)\) gets stuck on line 3 for any \(y\). In both cases, \(L(M') = \varnothing\). When we run \(M_\text{SAT}(\left \langle M' \right\rangle)\) on line 6, it rejects, and so our machine rejects and gives the correct answer.
Our machine always gives the correct answer, so we are done.
In the proof above, we have defined the decider \(M_\text{ACCEPTS}\) in which we create the encoding of the machine \(M'\), denoted \(\left \langle M' \right\rangle\). Note that creating \(\left \langle M' \right\rangle\) (which is simply creating a string) is very different from actually running the machine \(M'\). In particular, even if \(M(x)\) loops forever, \(M_\text{ACCEPTS}(\left \langle M, x \right\rangle)\) does not loop forever because
\(M_\text{ACCEPTS}\) does not run \(M'\), and
\(M_\text{SAT}\) is assumed to be a decider, which means it always halts.
The language \(\text{NEQ}_{\text{TM}}\) is undecidable.
We want to show that \(\text{NEQ}_{\text{TM}}\) is undecidable and we will do so by reducing \(\text{SAT}_{\text{TM}}\) (which we know is undecidable) to \(\text{NEQ}_{\text{TM}}\). To carry out this reduction, assume \(\text{NEQ}_{\text{TM}}\) is decidable and let \(M_{\text{NEQ}}\) be a decider for it. Using this decider, we will construct a decider for \(\text{SAT}_{\text{TM}}\) to establish the reduction. The construction is as follows.
\[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_{\text{SAT}}(\left \langle \text{TM } M \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Construct string $\left \langle M' \right\rangle$ where $M'$ is a TM that rejects every input.}\\ &{\scriptstyle 2.}~~~~\texttt{Run $M_{\text{NEQ}}(\left \langle M, M' \right\rangle)$.}\\ &{\scriptstyle 3.}~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 4.}~~~~\texttt{If it rejects, reject.}\\ \hline\hline\end{aligned}\]
It is not difficult to see that this machine indeed decides \(\text{SAT}_{\text{TM}}\). Notice that \(L(M') = \varnothing\). So when we run \(M_{\text{NEQ}}(\left \langle M, M' \right\rangle)\) on line 2, we are deciding whether \(L(M) = L(M')\), which means we are deciding whether \(L(M) = \varnothing\).
In more detail, if \(M\) is such that \(\left \langle M \right\rangle \in \text{SAT}_{\text{TM}}\), then \(L(M) \neq \varnothing\). Then on line 2, \(M_{\text{NEQ}}\) accepts, and therefore \(M_{\text{SAT}}\) accepts, giving the correct output. If on the other hand \(M\) is such that \(\left \langle M \right\rangle \not\in \text{SAT}_{\text{TM}}\), then \(L(M) = \varnothing\). In this case \(M_{\text{NEQ}}\) on line 2 rejects, and therefore \(M_{\text{SAT}}\) rejects as well, which is again the correct output.
Show that the following languages are undecidable.
\(\text{HALTS-EMPTY}_{\text{TM}}= \{\left \langle M \right\rangle : \text{ $M$ is a TM and $M(\epsilon)$ halts}\}\)
\(\text{FINITE}_{\text{TM}}= \{\left \langle M \right\rangle : \text{$M$ is a TM that accepts finitely many strings}\}\)
Part 1: We want to show \(\text{HALTS-EMPTY}_{\text{TM}}\) is undecidable. We will reduce \(\text{HALTS}_{\text{TM}}\) to \(\text{HALTS-EMPTY}_{\text{TM}}\). So assume \(\text{HALTS-EMPTY}_{\text{TM}}\) is decidable and let \(M_{\text{HALTS-EMPTY}}\) be a decider for it. We construct a decider for \(\text{HALTS}_{\text{TM}}\) as follows.
\[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_\text{HALTS}(\left \langle \text{TM } M, \; \text{string } x \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Construct the following string, which we call $\left \langle M' \right\rangle$.}\\ &{\scriptstyle 2.}~~~~\texttt{"def $M'(y)$:}\\ &{\scriptstyle 3.}~~~~~~~~\texttt{Run $M(x)$.}\\ &{\scriptstyle 4.}~~~~~~~~\texttt{Ignore the output and accept."}\\ &{\scriptstyle 5.}~~~~\texttt{Run $M_\text{HALTS-EMPTY}(\left \langle M' \right\rangle)$.}\\ &{\scriptstyle 6.}~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 7.}~~~~\texttt{If it rejects, reject.}\\ \hline\hline\end{aligned}\]
To see that this is a correct decider for \(\text{HALTS}_{\text{TM}}\), first consider any input \(\left \langle M,x \right\rangle\) such that \(\left \langle M,x \right\rangle \in \text{HALTS}_{\text{TM}}\), i.e., \(M(x)\) halts. By the construction of \(M'\), this implies that \(M'(y)\) halts (and accepts) for any string \(y\). So \(M_\text{HALTS-EMPTY}(\left \langle M' \right\rangle)\) accepts, and our decider above accepts as well. So in this case, the decider gives the correct answer.
Now consider any input \(\left \langle M,x \right\rangle\) such that \(\left \langle M,x \right\rangle \not\in \text{HALTS}_{\text{TM}}\), i.e., \(M(x)\) loops. Then for any input \(y\), \(M'(y)\) would get stuck on line 3, and would never halt. This means \(M_\text{HALTS-EMPTY}(\left \langle M' \right\rangle)\) rejects, and our decider rejects as well, as desired.
For any input, our decider gives the correct answer, and the proof is complete.
Part 2: Our goal is to show that \(\text{FINITE}_{\text{TM}}\) is undecidable. For this, we will reduce \(\text{HALTS}_{\text{TM}}\) to \(\text{FINITE}_{\text{TM}}\). We assume \(\text{FINITE}_{\text{TM}}\) is decidable, so let \(M_\text{FINITE}\) be a decider for it. Here is the description of a decider for \(\text{HALTS}_{\text{TM}}\).
\[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_\text{HALTS}(\left \langle \text{TM } M, \; \text{string } x \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Construct the following string, which we call $\left \langle M' \right\rangle$.}\\ &{\scriptstyle 2.}~~~~\texttt{"def $M'(y)$:}\\ &{\scriptstyle 3.}~~~~~~~~~\texttt{Run $M(x)$.}\\ &{\scriptstyle 4.}~~~~~~~~~\texttt{Ignore the output and accept."}\\ &{\scriptstyle 5.}~~~~\texttt{Run $M_\text{FINITE}(\left \langle M' \right\rangle)$.}\\ &{\scriptstyle 6.}~~~~\texttt{If it accepts, reject.}\\ &{\scriptstyle 7.}~~~~\texttt{If it rejects, accept.}\\ \hline\hline\end{aligned}\]
To see that this is a correct decider for \(\text{HALTS}_{\text{TM}}\), first consider any input \(\left \langle M,x \right\rangle\) such that \(\left \langle M,x \right\rangle \in \text{HALTS}_{\text{TM}}\), i.e., \(M(x)\) halts. By the construction of \(M'\), this implies that \(M'(y)\) accepts for any string \(y\). So \(L(M') = \Sigma^*\) (an infinite set), and therefore \(M_\text{FINITE}(\left \langle M' \right\rangle)\) rejects. In this case, our decider for \(\text{HALTS}_{\text{TM}}\) accepts and gives the correct answer.
Now consider any input \(\left \langle M,x \right\rangle\) such that \(\left \langle M,x \right\rangle \not\in \text{HALTS}_{\text{TM}}\), i.e., \(M(x)\) loops. Then for any input \(y\), \(M'(y)\) would get stuck on line 3, and would never halt. So \(L(M') = \varnothing\) (a finite set), and therefore \(M_\text{FINITE}(\left \langle M' \right\rangle)\) accepts. In this case, our decider for \(\text{HALTS}_{\text{TM}}\) rejects and gives the correct answer.
For any input, our decider gives the correct answer, and the proof is complete.
\(\text{SAT}_{\text{TM}}\leq \text{HALTS}_{\text{TM}}\).
We want to show that deciding \(\text{SAT}_{\text{TM}}\) reduces to deciding \(\text{HALTS}_{\text{TM}}\). For this, we assume \(\text{HALTS}_{\text{TM}}\) is decidable. Let \(M_\text{HALTS}\) be a decider for \(\text{HALTS}_{\text{TM}}\). Using it, we need to construct a decider \(M_\text{SAT}\) for \(\text{SAT}_{\text{TM}}\).
The main idea in the construction of \(M_\text{SAT}\) is as follows. Given as input \(\left \langle M \right\rangle\), we want to define the description of another TM \(M'\) so that \(M\) is satisfiable (i.e. there exists \(x\) such that \(M(x)\) accepts) if and only if \(M'\) halts (regardless of what the input is). The idea behind the definition of \(M'\) is to do an exhaustive search, going through every possible input string \(y\), in order to find one \(y\) that \(M\) accepts. If we can define such an \(M'\), then indeed, \(M\) is satisfiable if and only if \(M'\) halts. That being said, we have to be careful about how \(M'\) is defined. In particular, we have to be careful that \(M'\) does not get stuck in a loop even though there is some \(y\) that \(M\) accepts. With this in mind, we construct \(M_\text{SAT}\) as follows.
\[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_\text{SAT}(\left \langle \text{TM } M \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Construct the following string, which we call $\left \langle M' \right\rangle$.}\\ &{\scriptstyle 2.}~~~~\texttt{"def $M'(x)$:}\\ &{\scriptstyle 3.}~~~~~~~~~\texttt{For $t = 1,2,3,\ldots:$}\\ &{\scriptstyle 4.}~~~~~~~~~~~~~\texttt{For each string $y$ with $|y| \leq t$:}\\ &{\scriptstyle 5.}~~~~~~~~~~~~~~~~~\texttt{Simulate $M(y)$ for at most $t$ steps.}\\ &{\scriptstyle 6.}~~~~~~~~~~~~~~~~~\texttt{If it accepts, accept."}\\ &{\scriptstyle 7.}~~~~\texttt{Run $M_\text{HALTS}(\left \langle M', \epsilon \right\rangle)$.}\\ &{\scriptstyle 8.}~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 9.}~~~~\texttt{If it rejects, reject.}\\ \hline\hline\end{aligned}\]
We now argue that this machine indeed decides \(\text{SAT}_{\text{TM}}\). First consider an input \(\left \langle M \right\rangle\) such that \(\left \langle M \right\rangle \in \text{SAT}_{\text{TM}}\). This means that there is some word \(y\) such that \(M(y)\) accepts. Note that \(M'\), by construction, does an exhaustive search, so if such a \(y\) exists, then \(M'\) will eventually find it, and accept. So \(M'(x)\) halts for any \(x\). When we run \(M_\text{HALTS}(\left \langle M', \epsilon \right\rangle)\), it accepts, and our machine accepts, giving the correct answer.
Now consider an input \(\left \langle M \right\rangle\) such that \(\left \langle M \right\rangle \not \in \text{SAT}_{\text{TM}}\). This means \(L(M) = \varnothing\). Observe that the only way \(M'\) halts is if \(M(y)\) accepts for some string \(y\). Since \(L(M) = \varnothing\), \(M'(x)\) loops forever for any string \(x\). This means that when we run \(M_\text{HALTS}(\left \langle M', \epsilon \right\rangle)\), it rejects, and so our decider above rejects, as desired.
Describe a TM that semi-decides \(\text{SAT}_{\text{TM}}\). Proof of correctness is not required.
\[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_\text{SAT}(\left \langle \text{TM } M \right\rangle):\\ &{\scriptstyle 1.}~~~~~\texttt{For $t = 1,2,3,\ldots:$}\\ &{\scriptstyle 2.}~~~~~~~~~\texttt{For each string $y$ with $|y| \leq t$:}\\ &{\scriptstyle 3.}~~~~~~~~~~~~~\texttt{Simulate $M(y)$ for at most $t$ steps.}\\ &{\scriptstyle 4.}~~~~~~~~~~~~~\texttt{If it accepts, accept.}\\ \hline\hline\end{aligned}\]
Let \(L, K \subseteq \{{\texttt{0}},{\texttt{1}}\}^*\) be languages. Prove or disprove the following claims.
If \(L \leq K\) then \(K \leq L\).
If \(L \leq K\) and \(K\) is regular, then \(L\) is regular.
Part 1: The claim is false. Let \(L\) be any decidable language. For example, we can take \(L = \varnothing\). The decider for \(L\) is a machine that rejects no matter what the input is. Let \(K = \text{HALTS}_{\text{TM}}\). Then to establish \(L \leq K\), we need to argue that given a decider for \(\text{HALTS}_{\text{TM}}\), we can decide \(\varnothing\). Since \(\varnothing\) is decidable, this is true (and we don’t even need to make use of a decider for \(\text{HALTS}_{\text{TM}}\)). On the other hand, it is not true that \(\text{HALTS}_{\text{TM}}\leq \varnothing\). For the sake of contradiction, if it was true, then this would mean that using a decider for \(\varnothing\), we can decide \(\text{HALTS}_{\text{TM}}\). And this would imply that \(\text{HALTS}_{\text{TM}}\) is decidable, a contradiction.
Part 2: The claim is false. Consider \(L = \{{\texttt{0}}^n{\texttt{1}}^n: n \in \mathbb N\}\) and \(K = \varnothing\). We have \(L \leq K\) because \(L\) is a decidable language (we don’t even need to make use of the decider for \(K\)). Furthermore, \(K\) is regular, but \(L\) is not.
In all the reductions \(L \leq K\) presented in this chapter, the TM \(M_L\) calls the TM \(M_K\) exactly once. (And in fact, almost all the reductions in this chapter are mapping reductions). Present a reduction from \(\text{HALTS}_{\text{TM}}\) to \(\text{ACCEPTS}_{\text{TM}}\) in which \(M_\text{HALTS}\) calls \(M_\text{ACCEPTS}\) twice, and both calls/outputs are used in a meaningful way.
We are assuming \(\text{ACCEPTS}_{\text{TM}}\) is decidable. Let \(M_\text{ACCEPTS}\) be a decider for it. Based on this assumption, we will show that \(\text{HALTS}_{\text{TM}}\) is decidable. Here is the description of a decider solving \(\text{HALTS}_{\text{TM}}\): \[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M_\text{HALTS}(\left \langle \text{TM } M, \; \text{string } x \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{Run $M_\text{ACCEPTS}(\left \langle M, x \right\rangle)$.}\\ &{\scriptstyle 2.}~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 3.}~~~~\texttt{Construct string $\left \langle M' \right\rangle$ by flipping the accept and reject states of $\left \langle M \right\rangle$.}\\ &{\scriptstyle 4.}~~~~\texttt{Run $M_\text{ACCEPTS}(\left \langle M', x \right\rangle)$.}\\ &{\scriptstyle 5.}~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 6.}~~~~\texttt{If it rejects, reject.}\\ \hline\hline\end{aligned}\]
Or equivalently, as a diagram:
Let’s now prove that this is indeed a correct decider for \(\text{HALTS}_{\text{TM}}\). To do this, we’ll show that no matter what input is, the machine always gives the correct answer.
First let’s assume we get any input \(\left \langle M,x \right\rangle\) such that \(\left \langle M,x \right\rangle \in \text{HALTS}_{\text{TM}}\). In this case our machine is supposed to accept. Since \(M(x)\) halts, we know that \(M(x)\) either ends up in the accepting state, or it ends up in the rejecting state. If it ends up in the accepting state, then \(M_\text{ACCEPTS}(\left \langle M,x \right\rangle)\) accepts (on line 1 of our machine’s description), and so our program accepts and gives the correct answer on line 2. If on the other hand, \(M(x)\) ends up in the rejecting state, then \(M'(x)\) ends up in the accepting state. Therefore \(M_\text{ACCEPTS}(\left \langle M',x \right\rangle)\) accepts (on line 4 of our machine’s description), and so our program accepts and gives the correct answer on line 5.
Now let’s assume we get any input \(\left \langle M,x \right\rangle\) such that \(\left \langle M,x \right\rangle \not \in \text{HALTS}_{\text{TM}}\). In this case our machine is supposed to reject. Since \(M(x)\) does not halt, it never reaches the accepting or the rejecting state. By the construction of \(M'\), this also implies that \(M'(x)\) never reaches the accepting or the rejecting state. Therefore first \(M_\text{ACCEPTS}(\left \langle M,x \right\rangle)\) (on line 1 of our machine’s description) will reject. And then \(M_\text{ACCEPTS}(\left \langle M',x \right\rangle)\) (on line 4 of our machine’s description) will reject. Thus our program will reject as well, and give the correct answer on line 6.
We have already proved that \(\overline{\text{SA}_{\text{TM}}}\) is not semi-decidable directly by diagonalization. We can show that other languages are not semi-decidable by making use of Theorem (Characterization of decidability in terms of semi-decidability).
If a language \(L\) is semi-decidable but undecidable, then \(\overline{L}\) is not semi-decidable. In other words, if \(L \in \mathsf{RE}\setminus \mathsf{R}\), then \(\overline{L} \not \in \mathsf{RE}\).
We know \(L\) is semi-decidable. If (for the sake of contradiction) \(\overline{L}\) is semi-decidable as well, then by Theorem (Characterization of decidability in terms of semi-decidability), \(L\) would be decidable, which contradicts our assumption that it is undecidable.
The languages \(\overline{\text{SA}_{\text{TM}}}\), \(\overline{\text{ACCEPTS}_{\text{TM}}}\), and \(\overline{\text{HALTS}_{\text{TM}}}\) are not semi-decidable, i.e. they are not in \(\mathsf{RE}\).
The languages \(\text{SA}_{\text{TM}}\), \(\text{ACCEPTS}_{\text{TM}}\), and \(\text{HALTS}_{\text{TM}}\) are all semi-decidable (i.e. are in \(\mathsf{RE}\)), but are not decidable (i.e. are not in \(\mathsf{R}\)). So the statement of the corollary follows from the previous theorem.
The relationship among the complexity classes \(\mathsf{REG}\), \(\mathsf{R}\), and \(\mathsf{RE}\) and can be summarized as follows.
\(\mathsf{REG}\subsetneq \mathsf{R}\) since \(\{{\texttt{0}}^n{\texttt{1}}^n : n \in \mathbb N\}\) is not regular but is decidable.
There are languages like \(\text{SA}_{\text{TM}}\), \(\text{ACCEPTS}_{\text{TM}}\), \(\text{HALTS}_{\text{TM}}\), \(\text{SAT}_{\text{TM}}\) that are undecidable (not in \(\mathsf{R}\)), but are semi-decidable (in \(\mathsf{RE}\)).
The complements of the languages above are not in \(\mathsf{RE}\).
Given some decision problem \(g : \Sigma^* \to \{0,1\}\), we define a \(g\)-oracle Turing machine (or simply \(g\)-OTM, or just OTM if \(g\) is understood from the context) as a Turing machine with an additional oracle instruction which can be used in the TM’s high-level description. The additional instruction has the following form. For any string \(x\) and any variable name \(y\) of our choosing, we are allowed to use \[y = g(x).\] After this instruction, the variable \(y\) holds the value \(g(x)\) and can be used in the rest of the Turing machine’s description. In this context, the function \(g\) is called an oracle.
We’ll use a superscript of \(g\) (e.g. \(M^g\)) to indicate that a machine is a \(g\)-OTM.
Similar to TMs, we write \(M^g(x) = 1\) if the oracle TM \(M^g\), on input \(x\), accepts. We write \(M^g(x) = 0\) if it rejects. And we write \(M^g(x) = \infty\) if it loops forever.
If \(f : \Sigma^* \to \{0,1\}\) is a decision problem such that for all \(x \in \Sigma^*\), \(M^g(x) = f(x)\), then we say \(M^g\) describes \(f\) (and the language corresponding to \(f\)).
Let \(h: \Sigma^* \to \{0,1\}\) denote the decision problem corresponding to \(\text{HALTS}_{\text{TM}}\). Here is a description of an \(h\)-oracle Turing machine. \[\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; M^h(\left \langle \text{TM } M, \; \text{string } x \right\rangle):\\ &{\scriptstyle 1.}~~~~\texttt{$y = h(\left \langle M, x \right\rangle)$}\\ &{\scriptstyle 2.}~~~~\texttt{If $y = 1$:}\\ &{\scriptstyle 3.}~~~~~~~~\texttt{Run $M(x)$.}\\ &{\scriptstyle 4.}~~~~~~~~\texttt{If it accepts, accept.}\\ &{\scriptstyle 5.}~~~~~~~~\texttt{If it rejects, reject.}\\ &{\scriptstyle 6.}~~~~\texttt{Else: reject.}\\ \hline\hline\end{aligned}\] Note that \(M^h\) describes the language \(\text{ACCEPTS}_{\text{TM}}\).
One can give a precise low-level definition for an oracle TM, however, we will not need or use that level of detail, so we choose to omit it.
Let \(L\) and \(K\) be two languages, and let \(k\) be the decision problem corresponding to \(K\). We say that \(L\) Turing-reduces to \(K\), written \(L \leq_T K\), if there is an oracle Turing machine \(M^k\) describing \(L\).
Observe that if \(L \leq_T K\) and \(K\) is decidable, then \(L\) is decidable. This is because if \(L \leq_T K\), then by definition, there is an oracle Turing machine \(M^k\) that describes \(L\). If \(K\) is decidable, there is a TM \(M_K\) deciding \(K\). Then in \(M^k\), if we replace all calls to the oracle \(k\) with \(M_K\), we end up with a TM deciding \(L\).
It follows (taking the contrapositive of the observation) that if \(L \leq_T K\) and \(L\) is undecidable, then \(K\) is undecidable.
As we have already seen, the set of all languages, \(\wp(\Sigma^*)\), is not encodable. Most languages do not have a finite description. In addition to thinking about the TM model as a computational model, it is useful to also think of it as a finite description model: Every TM finitely describes/defines the language that it decides (or semi-decides).
The TM model is not a comprehensive finite description model. There are many finitely describable languages (e.g., \(\overline{\text{SA}_{\text{TM}}}\), \(\text{ACCEPTS}_{\text{TM}}\), \(\text{HALTS}_{\text{TM}}\)) that a TM cannot finitely describe. The oracle TM model extends the reach of the TM model as a finite description model.
If we inspect the proof of Turing’s 1st Undecidability Theorem, we can see that we never really made use of the fact that TMs represent a computational model. The crucial part of the argument was that the set of TMs is encodable/countable. Or in other words, we only needed that the TM model is a finite description model for languages/decision problems. This means that for other finite description models, like the oracle TM model, we can carry out the same argument.
An important lesson here is that the main limitation Turing’s 1st Undecidability Theorem highlights about TMs is not that they form a computing model, but that they form a finite description model.
Fix an oracle \(g\). Then we can define the languages \(\text{ACCEPTS}_{\text{OTM}}\), \(\text{HALTS}_{\text{OTM}}\), \(\text{SA}_{\text{OTM}}\), and so on, analogous to how they are defined for TMs. For example, \[\text{HALTS}_{\text{OTM}}= \{\left \langle M^g,x \right\rangle : \text{$M^g$ is a $g$-OTM which halts on input $x$} \}.\]
Fix an oracle \(g\). Then there is no oracle Turing machine that describes \(\overline{\text{SA}_{\text{OTM}}}\).
The proof is exactly the same as the proof of Turing’s 1st Undecidability Theorem. Note that the set of all \(g\)-oracle Turing machines is encodable/countable. Therefore we can diagonalize against the set of all \(g\)-oracle TMs. The natural diagonal element that the diagonalization spits out is \(\overline{\text{SA}_{\text{OTM}}}\).
State 4 languages that are undecidable.
State an undecidable language whose description does not involve Turing machines.
Describe 3 languages that are not semi-decidable.
Describe how one can show that a language is undecidable using the notion of a reduction.
True or false: For languages \(K\) and \(L\), if \(K \leq L\), then \(L\) is undecidable.
True or false: For languages \(K\) and \(L\), if \(K \leq L\) and \(L \leq K\), then \(L\) and \(K\) are both decidable.
True or false: Fix some alphabet \(\Sigma\). The set of regular languages over \(\Sigma\) is countable.
True or false: Fix an alphabet \(\Sigma\). The set of undecidable languages is countable.
True or false: Fix an alphabet \(\Sigma\). The set of decidable languages is infinite.
True or false: If languages \(K\) and \(L\) are both undecidable, then their union is also undecidable.
True or false: If a language \(L\) is undecidable, then \(L\) is infinite.
True or false: \(\Sigma^* \leq \varnothing\).
True or false: \(\text{HALTS}_{\text{TM}}\leq \Sigma^*\).
True or false: Every decidable language reduces to \(\text{HALTS}_{\text{TM}}\).
True or false: For all unary languages \(L\) (i.e. languages over the alphabet \(\Sigma = \{{\texttt{1}}\}\)), \(L\) is decidable.
In a previous chapter, we saw that the language \(\text{SAT}_{\text{DFA}}\) is decidable. In particular, we saw that given the encoding of a DFA \(D\), we can determine if \(D\) accepts a string by checking if in the state diagram of \(D\), there is a directed path from the initial state to one of the accepting states.
In this chapter, we saw that the language \(\text{SAT}_{\text{TM}}\) is undecidable. Show that the strategy above that we used for DFAs does not apply to TMs by drawing the state diagram of a TM \(M\) with \(L(M) = \varnothing\), but there is a path from the starting state to the accepting state.
Here are the important things to keep in mind from this chapter.
The existence of undecidable languages follows by a counting argument: The set of all languages is uncountable whereas the set of decidable languages is countable. This shows that almost all languages are undecidable, however, it does not give us an explicit undecidable language.
We can use diagonalization to come up with an explicit language that is undecidable.
Reductions are very important. We have seen in an earlier chapter that reductions can be used to expand the landscape of decidable languages. In this chapter, you see that it can be used to expand the landscape of undecidable languages.
This chapter has many examples of undecidability proofs. It is easy to fall in the trap of trying to memorize the template of such proofs rather than really understanding the logic behind how and why these proofs work. If you struggle to understand these proofs, it is usually a sign that there are gaps in your knowledge from previous chapters. Come talk to us so we can help you identify those gaps.