Recitation 4 latex source
This file is provided to help students create crib sheets
in latex if they wish. Some formatting was removed for clarity.
It is missing some macros, but you can figure out what they are
by looking at the pdf image. It is not a working latex file.
\begin{document}
\chapter{Recitation 04: Undecidability, Unrecognizability, and \\ Reducibility}
In this recitation we'll practice working with reductions to show that a language is undecidable or unrecognizable. We begin by providing a diagram summarizing the languages we've seen in lecture, and whether they are decidable, recognizable, or unrecognizable. Then, we review general and mapping reducibility. Finally, we work an example using general reducibility to show that a particular language is undecidable, and another example using mapping reducibility to show that a particular language is both unrecognizable and co-unrecognizable.
\section{Undecidability and unrecognizability}
We proved the following facts about $A_{TM}$ in lecture.
\begin{theorem}
$A_{TM}$ is Turing-recognizable (T-recognizable) and undecidable.
\end{theorem}
\begin{theorem}
$\overline{A_{TM}}$ is unrecognizable.
\end{theorem}
We define the class of co-Turing-recognizable languages as the class of complements of recognizable languages.
\begin{definition}
Language $B$ is \textbf{co-Turing-recognizable} if $\overline{B}$ is Turing-recognizable.
\end{definition}
For example, $\overline{A_{TM}}$ is co-Turing-recognizable because $A_{TM}$ is Turing-recognizable.
We proved the following theorem in lecture.
\begin{theorem}\label{decidable-iff-both-recognizable}
Language $B$ is decidable iff both $B$ and $\overline{B}$ are T-recognizable.
\end{theorem}
In other words, language $B$ is decidable iff $B$ is both Turing-recognizable and co-Turing-recognizable. Figure \ref{venn-diagram} shows this visually, and lists several more examples of undecidable and/or unrecognizable languages.
\begin{figure}\label{venn-diagram}
\caption{Undecidable or unrecognizable languages we have seen in class.}
\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%Shape: Ellipse [id:dp5296145807390229]
\draw (38.73,164.27) .. controls (38.73,116.07) and (98.73,77) .. (172.73,77) .. controls (246.74,77) and (306.73,116.07) .. (306.73,164.27) .. controls (306.73,212.46) and (246.74,251.53) .. (172.73,251.53) .. controls (98.73,251.53) and (38.73,212.46) .. (38.73,164.27) -- cycle ;
%Shape: Rectangle [id:dp9052159421530435]
\draw (28.73,3.6) -- (466.73,3.6) -- (466.73,267.53) -- (28.73,267.53) -- cycle ;
%Shape: Ellipse [id:dp8312779550029692]
\draw (172.73,164.27) .. controls (172.73,116.07) and (232.73,77) .. (306.73,77) .. controls (380.74,77) and (440.73,116.07) .. (440.73,164.27) .. controls (440.73,212.46) and (380.74,251.53) .. (306.73,251.53) .. controls (232.73,251.53) and (172.73,212.46) .. (172.73,164.27) -- cycle ;
%Shape: Ellipse [id:dp15327998313031754]
\draw (185.73,172.53) .. controls (185.73,147.13) and (210.81,126.53) .. (241.73,126.53) .. controls (272.66,126.53) and (297.73,147.13) .. (297.73,172.53) .. controls (297.73,197.94) and (272.66,218.53) .. (241.73,218.53) .. controls (210.81,218.53) and (185.73,197.94) .. (185.73,172.53) -- cycle ;
%Shape: Ellipse [id:dp5510128985872493]
\draw (199.37,185.03) .. controls (199.37,169.72) and (217.89,157.3) .. (240.73,157.3) .. controls (263.58,157.3) and (282.1,169.72) .. (282.1,185.03) .. controls (282.1,200.35) and (263.58,212.77) .. (240.73,212.77) .. controls (217.89,212.77) and (199.37,200.35) .. (199.37,185.03) -- cycle ;
% Text Node
\draw (41,17) node [anchor=north west][inner sep=0.75pt] [align=left] {{\small \textbf{All languages}}};
% Text Node
\draw (209,108) node [anchor=north west][inner sep=0.75pt] [align=left] {{\small \textbf{Decidable}}};
% Text Node
\draw (106,90) node [anchor=north west][inner sep=0.75pt] [align=left] {{\small \textbf{T-recognizable}}};
% Text Node
\draw (270,88) node [anchor=north west][inner sep=0.75pt] [align=left] {{\small \textbf{co-T-recognizable}}};
% Text Node
\draw (218,175) node [anchor=north west][inner sep=0.75pt] [align=left] {{\small \textbf{Regular}}};
% Text Node
\draw (221,136) node [anchor=north west][inner sep=0.75pt] [align=left] {\textbf{CFLs}};
% Text Node
\draw (81,121.4) node [anchor=north west][inner sep=0.75pt] {$A_{T}{}_{M}$};
% Text Node
\draw (70,154.4) node [anchor=north west][inner sep=0.75pt] {$HALT_{T}{}_{M}$};
% Text Node
\draw (89,181.4) node [anchor=north west][inner sep=0.75pt] {$\overline{E_{T}{}_{M}}$};
% Text Node
\draw (312,118.4) node [anchor=north west][inner sep=0.75pt] {$\overline{A_{T}{}_{M}}$};
% Text Node
\draw (316,149.4) node [anchor=north west][inner sep=0.75pt] {$\overline{HALT_{T}{}_{M}}$};
% Text Node
\draw (320,182.4) node [anchor=north west][inner sep=0.75pt] {$E_{T}{}_{M}$};
% Text Node
\draw (175,44.4) node [anchor=north west][inner sep=0.75pt] {$EQ_{T}{}_{M}$};
\end{tikzpicture}
\end{figure}
We proved that $A_{TM}$ is undecidable using a diagonalization argument. In the following theorem, we show that there are uncountably many unrecognizable languages, using diagonalization as an intermediate step.
\begin{theorem}
The set of T-unrecognizable languages is uncountably infinite.
\end{theorem}
\begin{proof}
\marginnote{A more detailed proof is given under \textbf{Corollary 4.18} in the textbook.}
We want to show that
\begin{enumerate}
\item The set of all TMs is countable, and
\item The set of all languages is uncountable.
\end{enumerate}
We prove that the set of all TMs is countable by encoding each TM as a string $\langle M \rangle \in \Sigma^*$. We know $\Sigma^*$ is countable because there are only finitely many strings of each length.
We prove that the set of all languages is uncountable as follows. Each language $L$ is a subset of the strings $s_1, s_2, s_3, \dots$ in $\Sigma^*$. We can show a correspondence between each language and an infinite binary string, with the $i$th bit of the binary string indicating whether string $s_i$ is in $L$. Then we use a diagonalization argument (similar to the proof that $\mathbb{R}$ is uncountable) to show that the set of infinite binary strings is uncountable.
Since each TM recognizes exactly one language, we conclude that uncountably many languages do not have a corresponding TM. So the set of unrecognizable languages is uncountable.
\end{proof}
\section{Reducibility}
We have seen two types of reducibility in lecture: \textbf{"general" reducibility} and \textbf{mapping reducibility}.
\marginnote{This notion of "general reducibility" is fairly informal. It can be formalized as \textbf{Turing reducibility}, which is described in \textbf{section 6.3} of the textbook (but that material is optional for the course).}
\begin{definition}[\textbf{General reducibility}]
Language $A$ is \textbf{reducible} to language $B$ if the following holds: if we can solve $B$, then we can solve $A$ using the solver for $B$ as a subroutine.
\end{definition}
Informally, "$A$ is reducible to $B$" implies that
\begin{enumerate}
\item If $A$ is hard, then $B$ is also hard, and
\item If $B$ is easy, then $A$ is also easy.
\end{enumerate}
In other words, this means $B$ is at least as hard as $A$. We can formalize the notion that hardness of $A$ implies hardness of $B$ as follows.
\begin{theorem} Suppose $A$ is reducible to $B$ (in the general sense). Then
\begin{enumerate}
\item If $A$ is undecidable, then $B$ is undecidable.
\item If $B$ is decidable, then $A$ is decidable.
\end{enumerate}
\end{theorem}
In most cases, we use general reductions to show that a language is undecidable (by showing that another language is reducible to it).
We have a second, related definition of reducibility.
\marginnote{The condition that $f$ is a computable function means that there exists a Turing machine that takes input $w$ and halts with $f(w)$ on the tape. In practice, this applies to any transformation to $w$ that we can think of, as long as it does not take infinite time.}
\begin{definition}[\textbf{Mapping reducibility}]
Language $A$ is \textbf{mapping reducible} to language $B$ if there exists a computable function $f: \Sigma^* \rightarrow \Sigma^*$ such that $w \in A$ iff $f(w) \in B$. We write this as $A \leq_\emph{m} B$.
\end{definition}
In other words, we want $f$ to map strings in $A$ to strings in $B$, and map strings not in $A$ to strings not in $B$ (as shown in Figure \ref{mapping-reducibility}).
\begin{figure}\label{mapping-reducibility}
\caption{Mapping reducibility. We write $A \leq_\text{m} B$ if some computable function $f$ maps strings in language $A$ to strings in language $B$, and maps strings not in $A$ to strings not in $B$.}
\begin{tikzpicture}[x=0.5pt,y=0.5pt,yscale=-1,xscale=1]
%Shape: Ellipse [id:dp6477568364899582]
\draw [fill={rgb, 255:red, 214; green, 247; blue, 145 } ,fill opacity=1 ] (280,88.63) .. controls (280,78.34) and (296.79,70) .. (317.5,70) .. controls (338.21,70) and (355,78.34) .. (355,88.63) .. controls (355,98.92) and (338.21,107.27) .. (317.5,107.27) .. controls (296.79,107.27) and (280,98.92) .. (280,88.63) -- cycle ;
%Shape: Rectangle [id:dp429599694818922]
\draw (247,48) -- (430,48) -- (430,154.2) -- (247,154.2) -- cycle ;
%Shape: Ellipse [id:dp43530471965118345]
\draw [fill={rgb, 255:red, 214; green, 247; blue, 145 } ,fill opacity=1 ] (60,93.1) .. controls (60,79.24) and (80.37,68) .. (105.5,68) .. controls (130.63,68) and (151,79.24) .. (151,93.1) .. controls (151,106.96) and (130.63,118.2) .. (105.5,118.2) .. controls (80.37,118.2) and (60,106.96) .. (60,93.1) -- cycle ;
%Curve Lines [id:da1864242764197468]
\draw (105.5,93.1) .. controls (145.3,63.25) and (199.95,-32.87) .. (332,87.44) ;
\draw [shift={(334,89.27)}, rotate = 222.68] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
\draw [shift={(105.5,93.1)}, rotate = 323.13] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (0, 0) circle [x radius= 3.35, y radius= 3.35] ;
%Curve Lines [id:da17378514106655718]
\draw (75,137) .. controls (175.49,197.96) and (247.28,209.16) .. (378.02,126.52) ;
\draw [shift={(380,125.27)}, rotate = 507.53] [fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.08] [draw opacity=0] (8.93,-4.29) -- (0,0) -- (8.93,4.29) -- cycle ;
\draw [shift={(75,137)}, rotate = 31.24] [color={rgb, 255:red, 0; green, 0; blue, 0 } ][fill={rgb, 255:red, 0; green, 0; blue, 0 } ][line width=0.75] (0, 0) circle [x radius= 3.35, y radius= 3.35] ;
%Shape: Rectangle [id:dp5318546946565339]
\draw (3,49) -- (186,49) -- (186,155.2) -- (3,155.2) -- cycle ;
%Shape: Circle [id:dp5127406302347419]
\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (332.32,93.11) .. controls (332.32,90.99) and (334.04,89.27) .. (336.16,89.27) .. controls (338.28,89.27) and (340,90.99) .. (340,93.11) .. controls (340,95.23) and (338.28,96.95) .. (336.16,96.95) .. controls (334.04,96.95) and (332.32,95.23) .. (332.32,93.11) -- cycle ;
%Shape: Circle [id:dp3845192683120764]
\draw [fill={rgb, 255:red, 0; green, 0; blue, 0 } ,fill opacity=1 ] (388,125.27) .. controls (388,123.06) and (386.21,121.27) .. (384,121.27) .. controls (381.79,121.27) and (380,123.06) .. (380,125.27) .. controls (380,127.48) and (381.79,129.27) .. (384,129.27) .. controls (386.21,129.27) and (388,127.48) .. (388,125.27) -- cycle ;
% Text Node
\draw (79,74.4) node [anchor=north west][inner sep=0.75pt] {$A$};
% Text Node
\draw (301,75.4) node [anchor=north west][inner sep=0.75pt] {$B$};
% Text Node
\draw (230,2.4) node [anchor=north west][inner sep=0.75pt] {$f$};
% Text Node
\draw (9,130.4) node [anchor=north west][inner sep=0.75pt] {$\Sigma ^{*}$};
% Text Node
\draw (258,131.4) node [anchor=north west][inner sep=0.75pt] {$\Sigma ^{*}$};
% Text Node
\draw (222,189.4) node [anchor=north west][inner sep=0.75pt] {$f$};
\end{tikzpicture}
\end{figure}
Figure \ref{mapping-reducibility} also helps show the following theorem:
\begin{theorem}
If $A \leq_\emph{m} B$, then $\overline{A} \leq_\emph{m} \overline{B}$.
\end{theorem}
\begin{proof}
Suppose $A \leq_\text{m} B$. Then there exists a computable function $f$ such that for all $w \in \Sigma^*$, we have $w \in A$ iff $f(w) \in B$. This means that
\begin{enumerate}
\item If $w \in A$, then $f(w) \in B$.
\item If $w \notin A$, then $f(w) \notin B$.
\end{enumerate}
By definition of complement, this can be rewritten in terms of $\overline{A}$ and $\overline{B}$ as follows. For all $w \in \Sigma^*$,
\begin{enumerate}
\item If $w \notin \overline{A}$, then $f(w) \notin \overline{B}$.
\item If $w \in \overline{A}$, then $f(w) \in \overline{B}$.
\end{enumerate}
Thus we have $w \in \overline{A}$ iff $f(w) \in \overline{B}$. We conclude that $\overline{A} \leq_\text{m} \overline{B}$.
\end{proof}
We often use mapping reductions to show that a language is unrecognizable. We can also use mapping reductions to show that a language is undecidable (however, it is more common to prove undecidability using general reductions). The following theorem summarizes the ways in which we use mapping reductions.
\begin{theorem} \label{mapping_thm}
Suppose $A \leq_{\emph{m}} B$. Then
\begin{enumerate}
\item If $A$ is unrecognizable, then $B$ is unrecognizable.
\item If $B$ is recognizable, then $A$ is recognizable.
\item If $A$ is undecidable, then $B$ is undecidable.
\item If $B$ is decidable, then $A$ is decidable.
\end{enumerate}
\end{theorem}
Don't be confused about the direction in which mapping reductions take
place. Given $A \leq_{\emph{m}} B$, the direction of the notation
$\leq_{\emph{m}}$ is meant to compare the difficulty of $A$ and $B$. That
is, solving $A$ is not more difficult than solving $B$. Remembering the
intuition behind the notation helps us to understand the content of Thm.
\ref{mapping_thm}.
\marginnote{Solvers, or more formally oracles, which we will see later in the course, instantly decide a language -- there is no looping.}
Notice that complements of a language are always generally reducible to the original language, \textit{i.~e.,} $\overline{A}$ is reducible to $A$. If we have a solver to $A$, we may always reverse its answer to solve $\overline{A}$. However, the same is not true for mapping reductions! Notice that $\overline{A_{TM}} \not\leq_\text{m} A_{TM}$ since $\overline{A_{TM}}$ is unrecognizable but $A_{TM}$ is recognizable. That means we \textit{can't} use general reducibility to show that a language is unrecognizable. Instead we use general reductions to show undecidability, and mapping reductions to show unrecognizability.
This also tells us that mapping reducibility is a stronger condition than general reducibility. If $A \leq_\text{m} B$, then $A$ is also reducible to $B$ in the general sense. However, if $A$ is reducible to $B$ in the general sense, it is not guaranteed that $A \leq_\text{m} B$. For example, $\overline{A_{TM}}$ is reducible to $A_{TM}$ in the general sense, but $\overline{A_{TM}}$ is not mapping reducible to $A_{TM}$.
\section{Problem solving strategies: undecidability and unrecognizability}
\begin{enumerate}
\item To show that language $B$ is \emph{undecidable}, find a \emph{general reduction} from some undecidable language $A$ to $B$. Our proof outline is generally as follows:
\begin{itemize}
\item Assume for contradiction that there is a TM $R$ that decides $B$.
\item Then construct a TM $S$ that decides $A$, using $R$ for a subroutine. Often, we use $A = A_{TM}$.
\end{itemize}
\item To show that language $B$ is \emph{unrecognizable}, find a \emph{mapping reduction} from some unrecognizable language $A$ to $B$ (written as $A \leq_\text{m} B$). Describe a computable function $f$ such that $w \in A$ iff $f(w) \in B$. Often, we use $A = \overline{A_{TM}}$. Describing $f$ serves as a shorthand for the following proof outline:
\begin{itemize}
\item Assume for contradiction that there exists a TM $R$ that recognizes $B$.
\item Then construct a TM $S$ that takes an input $w$, computes $f(w)$, runs $R$ on $f(w)$, and outputs the result of $R$ on $f(w)$. $S$ will decide $A$.
\end{itemize}
\end{enumerate}
\section{Example problems}
In the following example (\textbf{Problem 5.10} in the textbook), we prove that a language is undecidable using a general reduction from $A_{TM}$.
\begin{example}
Show that
\begin{align*}
TT_{TM} = \{&\langle M, w \rangle \mid M \text{ is a 2-tape TM that writes a nonblank symbol on its} \\
& \text{second tape when run on w}\}
\end{align*}
is undecidable.
\end{example}
\begin{solution}
We construct a general reduction from $A_{TM}$ to $TT_{TM}$. Assume for contradiction that $R$ is a decider for $TT_{TM}$. We construct the following decider $S$ for $A_{TM}$.
\begin{mdframed}
\pmb{S}: On input $\langle M, w \rangle$:
\begin{enumerate}
\item Construct the following 2-tape Turing machine $T_M$:
\begin{mdframed}
\pmb{$T_M$}: On input $x$:
\begin{enumerate}
\item Simulate $M$ on $x$ using the first tape of $T_M$.
\item If $M$ accepts, write a nonblank symbol on the second tape.
\end{enumerate}
\end{mdframed}
\item Run $R$ on $\langle T_M, w \rangle$.
\item \textbf{Accept} if $R$ accepts. \\
\textbf{Reject} if $R$ rejects.
\end{enumerate}
\end{mdframed}
If $M$ accepts $w$, then when $T_M$ is run on $w$, it writes a nonblank symbol on its second tape. So $\langle T_M, w \rangle \in TT_{TM}$. Then $R$ accepts $\langle T_M, w \rangle$, so $S$ also accepts $\langle M, w \rangle$.
If $M$ rejects $w$, by halting or looping (or if the string $\langle M, w \rangle$ is garbage), then when $T_M$ is run on $w$ it does not use its second tape. So $\langle T_M, w \rangle \notin TT_{TM}$. Then, $R$ halts and rejects $\langle T_M, w \rangle$, so $S$ also halts and rejects $\langle M, w \rangle$.
\marginnote{It's possible that $M$ rejects $w$ by looping forever. However, since we have assumed that $R$ \textbf{decides} $TT_{TM}$, $R$ will always halt, meaning that $S$ will also always halt.}
Hence $S$ decides $A_{TM}$. This is a contradiction because we know $A_{TM}$ is undecidable. We conclude that $TT_{TM}$ is undecidable.
\end{solution}
In the next examples, we prove that a language is unrecognizable and co-unrecognizable using mapping reductions from $\overline{A_{TM}}$.
\bigskip
\begin{example}
Show that
\begin{equation*}
REG_{TM} = \{\langle M \rangle|~M \text{ is a TM and $L(M)$ is a regular language}\}
\end{equation*}
is unrecognizable.
\end{example}
\begin{solution} We will show that
\begin{equation*}
\overline{A_{TM}} \leq_{\emph{m}} REG_{TM}.
\end{equation*}
That is, we need to find a computable function $f$ such that $\langle M, w \rangle \in \overline{A_{TM}}$ iff $f(\langle M, w \rangle) = T_{M, w} \in REG_{TM}$.
In other words: if TM $M$ rejects $w$, then we want the language of $T_{M, w}$ to be regular. If TM $M$ accepts $w$, we want the language of $T_{M, w}$ to be nonregular. We can design $T_{M, w}$ such that if $M$ accepts $w$, then $L(T_{M, w})$ is a specific nonregular language (we use $\{0^k 1^k \mid k \geq 0\}$ in this example).
We construct $T_{M, w}$ as follows.
\begin{mdframed}
\pmb{$T_{M, w}$}: On input $x$:
\begin{enumerate}
\item Run $M$ on $w$.
\item If $M$ accepts, check if $x = 0^k 1^k$ for some $k \geq 0$. If so, \textbf{accept}. \item Otherwise, \textbf{reject}.
\end{enumerate}
\end{mdframed}
\marginnote{It's possible that $M$ rejects $w$ by looping forever. In that case, $T_{M, w}$ also rejects by looping forever (on all inputs). However, we \emph{cannot} write "if $M$ loops forever, then loop" as part of the program for $T_{M, w}$. This is because $T_{M, w}$ can't determine that $M$ will loop forever, since the halting problem $HALT_{TM}$ is undecidable.}
If $M$ accepts $w$, then $T_{M, w}$ accepts precisely the strings of the form $0^k 1^k$. So $L(T_{M, w}) = \{0^k 1^k \mid k \geq 0\}$ which is a nonregular language.
If $M$ rejects $w$, by halting or looping (or if the string $\langle M, w \rangle$ is garbage), then $T_{M, w}$ rejects all inputs (either by halting or looping). So $L(T_{M, w}) = \emptyset$ which is a regular language.
This proves that $\overline{A_{TM}} \leq_{\emph{m}} REG_{TM}$. We know $\overline{A_{TM}}$ is unrecognizable, so $REG_{TM}$ is also unrecognizable.
\end{solution}
\bigskip
\begin{example}
Show that $REG_{TM}$ is co-T-unrecognizable.
\end{example}
\begin{solution}
The proof is similar to the last problem. We will show that
\begin{equation*}
\overline{A_{TM}} \leq_{\emph{m}} \overline{REG_{TM}}.
\end{equation*} We find a computable function $f$ such that $\langle M, w \rangle \in \overline{A_{TM}}$ if and only if $f(\langle M, w \rangle) = T_{M, w} \in \overline{REG_{TM}}$.
In other words: If $M$ rejects $w$, then we want the language of $T_{M, w}$ to be nonregular. If $M$ accepts $w$, then we want the language of $T_{M, w}$ to be regular.
We construct $T_{M, w}$ as follows.
\begin{mdframed}
\pmb{$T_{M, w}$}: On input $x$:
\begin{enumerate}
\item If $x$ is of the form $0^k1^k$, \textbf{accept}.
\item Run $M$ on $w$. \textbf{Accept} if $M$ accepts.
\end{enumerate}
\end{mdframed}
If $M$ accepts $w$, then $T_{M, w}$ accepts all strings. So $L(T_{M, w}) = \Sigma^*$, which is a regular language.
If $M$ rejects $w$, by halting or looping (or if the string $\langle M, w \rangle$ is garbage), then $T_{M, w}$ only accepts inputs of the form $x = 0^k 1^k$ and rejects all other inputs (either by halting or looping). So $L(T_{M, w}) = \{0^k 1^k\ \mid k \geq 0\}$, which is a nonregular language.
We have shown that $\overline{A_{TM}} \leq_{\emph{m}} \overline{REG_{TM}}$. We know $\overline{A_{TM}}$ is unrecognizable, so $\overline{REG_{TM}}$ is also unrecognizable. This proves that $REG_{TM}$ is co-unrecognizable.
\end{solution}