Recitation 6 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.
\chapter{Recitation 06: Recursion Theorem + Midterm Review}
\section{Recursion Theorem}
The recursion theorem is informally stated as follows.
\begin{theorem}[Recursion theorem, informal]
A Turing machine can obtain a description of itself and compute on it.
In other words, when writing pseudocode for a TM $R$, we're allowed to write ``Get self-description $\langle R\rangle$''
as the first step and use $\langle R\rangle$ in subsequent steps.
\end{theorem}
The recursion theorem, and more broadly the idea of self-reference (e.g., diagonalization),
is a powerful tool for proving certain things are impossible.
Here's an analogy for what a proof with the recursion theorem generally looks like:
\begin{quote}
\emph{
Suppose there's this prophet that can make certain kinds of predictions about people.
I'll ask the prophet to make such a prediction about myself, and then I'll ``disobey'' the prediction
by behaving differently from what the prophet predicted about me.
This is a contradiction, and hence the prophet cannot exist.
}
\end{quote}
Now, change ``prophet that makes certain kinds of predictions about people''
to something like ``TM $D$ that decides whether a given TM has a certain property''\footnote{
The prophet can also be other kinds of things that in a sense ``tell you something about TMs''---see
\Cref{ex:all_tm_mapred} below.
}
and the pronoun ``I'' to a TM $R$ that invokes the recursion theorem. And we have a template for
proofs that use the recursion theorem:\footnote{Such a proof doesn't work for all TM properties.
Indeed, some TM properties \textit{are decidable}, such as the one from Recitation 3:
$\{\langle M, w\rangle \mid \text{$M$ ever attempts to move its head left on input $w$}\}$.
What goes wrong when you try to use the recursion theorem to show that this language is undecidable?}
\begin{quote}
{\em
Suppose there's a decider $D$ for some TM property.
Construct a TM
$R =$ ``On input $x$,
\begin{enumerate}
\item Get self-description $\langle R\rangle$.
\item Ask $D$ whether $R$ has the property in question by running $D$ on $\langle R\rangle$.
\item Behave opposite to what $D$ said about $R$:
\begin{itemize}
\item If $D$ says $R$ has the property, then don't exhibit that property.
\item If $D$ says $R$ doesn't have the property, then exhibit that property.''
\end{itemize}
\end{enumerate}
This is a contradiction: $R$ contradicts what $D$ says about $R$.
Thus, the TM property in question is undecidable.
}
\end{quote}
As a simple example, let's show that $A_\mathsf{TM}$ is undecidable using the recursion theorem.
Note the similarity with the diagonalization proof from lecture, which also uses self-reference
to construct a TM that contradicts what an $A_\mathsf{TM}$ decider says about it.
\begin{example}
Show that $A_\mathsf{TM}$ is undecidable using the recursion theorem.
\end{example}
\begin{proof}
Suppose for the sake of contradiction that $D$ decides $A_\mathsf{TM}$. Then construct TM
$R =$ ``On input $w$,
\begin{enumerate}
\item Get self-description $\langle R\rangle$.
\item Run $D$ on $\langle R, w\rangle$.
\item Behave opposite to what $D$ said about $R$ on $w$:
\begin{itemize}
\item If $D$ accepted (i.e., predicted that $R$ would accept $w$), then reject.
\item If $D$ rejected (i.e., predicted that $R$ would reject $w$), then accept.''
\end{itemize}
\end{enumerate}
Then $R$ accepts $w$ iff $D$ rejects $\langle R, w\rangle$, so $D$ cannot be a decider for $A_\mathsf{TM}$, a contradiction.
\end{proof}
While the example above identifies ``prophet'' with ``a decider $D$ for $A_\mathsf{TM}$'',
the ``prophet'' doesn't always have to be a decider for a TM property.
It can more generally be things that ``tell you something about TMs'' in an informal sense.
For example, in the $MIN_\mathsf{TM}$ T-unrecognizability proof from lecture,
the ``prophet'' is an enumerator for a TM property (namely, minimality),
and the enumerator tells you something about the TMs that it enumerates (i.e., that they have that property and no other TM does).
In the following example, the ``prophet'' is a function $f$ from TMs to TMs,
and $f$ tells you something about the relationship between $\langle M\rangle$ and $f(\langle M\rangle)$.
\begin{example} \label{ex:all_tm_mapred}
Show that $ALL_\mathsf{TM} \not\leq_\mathrm{m} \overline{ALL_\mathsf{TM}}$ using the recursion theorem.
\end{example}
\begin{proof}
Suppose for the sake of contradiction that a mapping $f$ implementing the reduction exists. Then construct the TM
$R =$ ``On input $x$,
\begin{enumerate}
\item Get self-description $\langle R\rangle$.
\item Get $\langle R'\rangle = f(\langle R\rangle)$.
\item Simulate $R'$ on $x$.''
\end{enumerate}
Then $f$ says that $L(R) \neq L(R')$, but $R$ disobeys that prediction by behaving the same way as $R'$ (Step 3),
resulting in $L(R) = L(R')$, a contradiction. Hence, a mapping $f$ that implements the reduction
$ALL_\mathsf{TM} \not\leq_\mathrm{m} \overline{ALL_\mathsf{TM}}$
cannot exist.
\end{proof}
\section{Midterm review}
We start with a Venn diagram of language classes, which shows the relationships between
regular, context-free, Turing-recognizable, co-Turing-recognizable,\footnote{
The \textit{co-Turing-recognizable} languages are defined to be the complements of the Turing-recognizable languages.}
and decidable languages (\Cref{fig:venn}). The diagram also contains example languages in each class.
Note that the intersection of Turing-recognizable and co-Turing-recognizable languages are the decidable languages.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=11]
\newcommand{\height}{0.6}
\newcommand{\margin}{0.02}
\draw (0, 0) rectangle ++(1, \height);
\draw (0, \height) node [anchor=north west] {\scriptsize\textbf{All Languages}};
\draw (0.37, \height/2) ellipse ({0.37-\margin} and {\height/2-\margin});
\draw (0.37-2*\margin, \height-2*\margin) node [anchor=north] {\scriptsize\textbf{T-recognizable}};
\draw (0.20, 0.4) node {$A_{\mathsf{TM}}$};
\draw (0.15, 0.3) node {$\textit{HALT}_{\mathsf{TM}}$};
\draw (0.20, 0.2) node {$\overline{E_{\mathsf{TM}}}$};
\draw (0.63, \height/2) ellipse ({0.37-\margin} and {\height/2-\margin});
\draw (0.63+2*\margin, \height-2*\margin) node [anchor=north] {\scriptsize\textbf{co-T-recognizable}};
\draw (0.80, 0.4) node {$\overline{A_{\mathsf{TM}}}$};
\draw (0.85, 0.3) node {$\overline{\textit{HALT}_{\mathsf{TM}}}$};
\draw (0.80, 0.2) node {$E_{\mathsf{TM}}$};
\draw (0.5, \height-3*\margin) node [anchor=north] {\scriptsize\textbf{Decidable}};
\draw (0.40, 0.45) node {$A_{\mathsf{DFA}}$};
\draw (0.50, 0.48) node {$E_{\mathsf{DFA}}$};
\draw (0.60, 0.45) node {$EQ_{\mathsf{DFA}}$};
\draw (0.45, 0.40) node {$A_{\mathsf{CFG}}$};
\draw (0.55, 0.40) node {$E_{\mathsf{CFG}}$};
\draw (0.5, 0.22) circle (0.15);
\draw (0.5, 0.22+0.15) node [anchor=north] {\scriptsize\textbf{CFL}};
\draw (0.50, 0.3) node {$\{0^k 1^k\}$};
\draw (0.5, 0.17) circle (0.09);
\draw (0.5, 0.17+0.09) node [anchor=north] {\scriptsize\textbf{Regular}};
\draw (0.47, 0.16) node {$\Sigma^*$};
\draw (0.53, 0.16) node {$\emptyset$};
\end{tikzpicture}
\caption{Venn diagram showing the language classes: regular, context-free, (co-)Turing-recognizable, decidable.}
\label{fig:venn}
\end{figure}
A summary of these language classes is given in \Cref{tab:summary}.
\begin{table}[ht]
\centering
\begin{tabulary}{\textwidth}{cCC}
\toprule
$X$ & What recognizes an $X$ language & What generates an $X$ language \\
\midrule
Regular & DFA/NFA & Regular expression \\
CFL & (non-det.) PDA & CFG \\
T-decidable & Turing decider & --- \\
T-recognizable & Turing machine & --- \\
\bottomrule
\end{tabulary}
\caption{Summary of what recognizes/generates the language classes: regular, context-free,
decidable, and Turing-recognizable.}
\label{tab:summary}
\end{table}
Next is a table with the closure properties for each language class \Cref{tab:closure}.
In recitation, we quickly reviewed the arguments for why some of these closure properties hold,
and we recommend it as a review exercise that you do this yourself for all the closure properties.
This may help you find some knowledge gaps you may have with each model of computation.
\begin{table}[ht]
\centering
\begin{tabulary}{\textwidth}{CCCCCCC}
\toprule
Class & $\cup$ & $\cap$ & $\circ$ & $^*$ &
$\overline{L}$ & $L^\mathcal{R}$ \\
\midrule
Regular & Y & Y & Y & Y & Y & Y \\
CFL & Y & N$^{\dagger}$ & Y & Y & N & Y \\
T-decidable & Y & Y & Y & Y & Y & Y \\
T-recognizable & Y & Y & Y & Y & N & Y \\
\bottomrule
\end{tabulary}
\smallskip
\noindent{\footnotesize $\dagger$ CFL $\cap$ Regular = CFL}
\medskip
\caption{Summary of closure properties of each language class.}
\label{tab:closure}
\end{table}
Observe that consistent with our diagram above, the complement of T-recognizable is not necessarily T-recognizable (otherwise, T-recognizable = co-T-recognizable, i.e., they would be represented by the same circle in the Venn diagram).
This is because T-recognizers can reject an input by running on it forever, so the argument that we can flip the output to obtain the complement, while it works for deciders, does not work for recognizers.
The next table summarizes the decidability of questions regarding various models of computation \Cref{tab:dec}.
You can use these results to show the (un)decidability of other questions about models of computation.
\begin{table}[ht]
\centering
\begin{tabulary}{\textwidth}{CCCCC}
\toprule
$X$ & $A_X$ & $E_X$ & $ALL_X$ & $EQ_X$ \\
\midrule
DFA/NFA & Y & Y & Y & Y \\
CFG/PDA & Y & Y & N & N \\
LBA & Y & N & N & N \\
TM & N$^a$ & N$^b$ & N$^c$ & N$^c$ \\
\bottomrule
\end{tabulary}
\smallskip
\noindent{\footnotesize $^a$ T-recog. $^b$ co-T-recog. $^c$ neither T-recog.\ nor co-T-recog.}
\medskip
\caption{Summary of decidability of questions regarding various models of computation.}
\label{tab:dec}
\end{table}
We now give an overview of the techniques we have studied so far to solve different
kinds of problems, as well as tips and tricks for each one.
A summary is given in \Cref{tab:techniques}.
\begin{table}[ht]
\centering
\begin{tabulary}{\textwidth}{cLL}
\toprule
$X$ & Show is $X$ & Show is not $X$ \\
\midrule
Regular & Construct DFA/NFA/regex \newline Closure properties & Pumping lemma \newline Closure properties \\
\midrule
CFL & Construct PDA/regex \newline Closure properties & Pumping lemma \newline Closure properties \\
\midrule
Decidable & Construct decider \newline Invoke known results (\Cref{tab:dec}) & General/mapping reduction from undecidable language \newline Computation history method \newline Recursion theorem \\
\midrule
T-recog. & Construct recognizer/enumerator \newline Invoke known results (\Cref{tab:dec}) & Mapping reduction from T-unrecognizable language \\
\bottomrule
\end{tabulary}
\caption{Summary of common techniques for proving a language is (not) in a certain class.}
\label{tab:techniques}
\end{table}
All examples are from the Jeopardy I created for my recitation section: \url{https://jeopardylabs.com/play/what-kind-of-language}.
It is recommended to try to solve the yourself before looking at the solutions.
\subsection{Showing a language belongs to a certain class}
Let's first review the general approach we take when showing a given language $L$ belongs to a
certain class.
\begin{description}
\item[Showing regular] The easiest solution is often to construct an NFA recognizing $L$ or write a regular expression for $L$, although
closure properties can come in handy as well. One can also construct a DFA, but an NFA allows you to use nondeterminism, which
can often simplify your solution.
Conversely, if a problem tells you that a language $A$ is regular, you can take a DFA $M$ for this language.
You can then, for example, construct another automaton $M'$ out of $M$ to prove some related language is regular
(e.g., in proving closure properties),
or use a decider that decides some property about $M'$ to construct a decider that decides some property about $M$.
\begin{example}
Show that $L = \{w \mid \text{$w$ represents a power of 2 in binary}\}$ is regular.
\end{example}
\begin{proof}
A regular expression for $L$ is $\mathtt{1}\mathtt{0}^*$.
\end{proof}
\item[Showing context-free] Depending on the CFL, it may be easier to construct a PDA that recognizes it
or to write a CFG that generates it.
When constructing a PDA that recognizes $L$, the PDA's stack is often used for counting/comparing certain amounts, and the
nondeterminism can be used to make necessary guesses.
When constructing a CFG that generates $L$, it may be helpful to think about
the different kinds of substructures that strings in $L$ are composed of,
which correspond to the variables in your grammar.
The rules in your grammar dictate how these substructures combine to form strings in $L$.
If a problem tells you that some language $A$ is a CFL, then you can take a CFG $G$
that generates $A$ or a PDA $P$ that recognizes $A$.
You can then, for example, construct another CFG $G'$ out of $G$ or PDA $P'$ out of $P$ to prove
some related language is context-free (e.g., in proving closure properties).
Or, you can use a decider that decides some property about $G'$ or $P'$
to construct a decider that decides some property about $G$ or $P$ (e.g., PSET 2 Q6).
\begin{example}
Show that $L = \{\mathtt{a}^n \mathtt{b}^{2n} \mid n \geq 0\}$ is context-free.
\end{example}
\begin{proof}
\textit{(CFG construction)} The following CFG $G$ generates $L$:
\begin{align*}
G: \quad S &\to \mathtt{a}S\mathtt{b}\mathtt{b} \mid \varepsilon
\end{align*}
\textit{(PDA construction)} The following PDA $P$ recognizes $L$:
$P =$ ``On input $w$,
\begin{enumerate}
\item Push two $x$'s for every $\mathtt{a}$ read from the input.
Go to step 2 when a $\mathtt{b}$ is read.
\item Pop one $x$ for every $\mathtt{b}$ read from the input.
\item \textit{Accept} if the stack is empty.''
\end{enumerate}
\end{proof}
\item[Showing Turing-recognizable] Here, you can construct a Turing machine $T$ that recognizes $L$.
Since $T$ is not required to be a decider, it only needs to halt for inputs $x \in L$.
There is no need to worry about whether $T$ rejects by halting or rejects by looping on inputs not in the language.
\begin{example}
Show that $\overline{E}_\mathsf{TM}$ is Turing-recognizable.
\end{example}
\begin{proof}
The following TM $T$ recognizes $L$:
$T =$ ``On input $\langle M\rangle$,
\begin{enumerate}
\item For $k = 1, 2, 3, \ldots$,
\begin{enumerate}
\item For each of the first $k$ strings in string order, simulate $M$ on it for $k$ steps.
\item If at any point $M$ accepts, then \textit{accept}.''
\end{enumerate}
\end{enumerate}
If $L(M) \neq \emptyset$, then there's some $i$ such that the $i$th string in string order
is accepted by $M$ in $n$ steps for some $n$. Then by the end of iteration $k = \max\{i, n\}$,
$T$ has accepted $\langle M\rangle$.
Conversely, if $T$ accepts $\langle M\rangle$, then there's some $k$
such that one of the first $k$ strings in string order is accepted by $M$,
so $L(M) \neq \emptyset$.
\end{proof}
\item[Showing decidable] This involves constructing a decider $D$ for the language $L$.
Make sure that it halts both on inputs that are in the language and inputs that are not in the language.
If $L$ asks about some property about a DFA, NFA, CFG, or PDA, it is often helpful to use a decider for
languages we already proved decidable, including
$A_{\mathsf{DFA}}, E_{\mathsf{DFA}}, EQ_{\mathsf{DFA}}$, $A_{\mathsf{CFG}}, E_{\mathsf{CFG}}$
(see \Cref{fig:venn}, \Cref{tab:dec}).
This is a reduction, where you modify your input to get something that can be
passed into the decider for one of these languages, giving a solution that is often simpler
than if you wrote an algorithm from scratch.
\begin{example}
Show that $ALL_\mathsf{DFA} = \{\langle M\rangle \mid \text{DFA $M$ satisfies $L(M) = \Sigma^*$}\}$ is decidable.
\end{example}
\begin{proof}
The following TM $D$ decides $ALL_\mathsf{DFA}$:
$D =$ ``On input $\langle M\rangle$,
\begin{enumerate}
\item Construct the DFA $M'$ that recognizes the complement of $L(M)$.
\item Run the $E_\mathsf{DFA}$ decider on $\langle M'\rangle$ and return the result.''
\end{enumerate}
The decider works because $\langle M\rangle \in ALL_\mathsf{DFA}$ iff $\langle M'\rangle \in E_\mathsf{DFA}$.
\end{proof}
\end{description}
\subsection{Showing a language does \textit{not} belong to a certain class}
We finish off this review by reviewing some tips for showing that a language $L$ does \textit{not} belong to one of the classes we have studied.
\begin{description}
\item[Showing non-regular] This is most commonly done using the pumping lemma, where we assume the
language is regular and thus have a pumping length $p$. We then show that there is some string
$s \in L$ ($|s| \geq p$) that violates the lemma. Remember that you only need to give one string $s$,
constructed for some general $p$, but you need to argue that there is \emph{no way} to split it
up into $s = xyz$ ($|xy| \leq p$, $|y| > 0$) such that $xy^iz \in L$ for every $i$. In other words, you have to argue that
no matter how the string gets cut up, there is some $i$ for which $xy^iz \notin L$. In some cases it
is more convenient to ``pump up'' ($i>1$) and in other cases to ``pump down'' ($i=0$).
Sometimes, it is possible to use closure properties to show that if $L$ is regular then some
other $L'$ (which is known to be non-regular) is also regular, which gives a contradiction.
\begin{example}
Show that $L = \{\mathtt{a}^n \mathtt{b}^{2n} \mid n \geq 0\}$ is not regular.
\end{example}
\begin{proof}
Suppose $L$ is regular. For pumping length $p$, consider the string
$s = \mathtt{a}^p \mathtt{b}^{2p} \in L$ ($|s| \geq p$).
Any way of writing $s = xyz$ where $|xy| \leq p$ and $|y| > 0$
will have $y$ be a non-empty substring of the $\mathtt{a}^p$ portion of $s$.
So $xz$ will have too few $\mathtt{a}$'s to be in $L$, violating the pumping lemma.
\end{proof}
\item[Showing non-context-free] The context-free pumping lemma can be used here, similarly to
how you show non-regularity. However, using the context-free version often requires more case work,
mainly because there are more ways to split $s$ up into 5 parts $uvxyz$ ($|vxy| \leq p$, $|vy| > 0$).
Some ways of doing case work can be a lot more complicated than other ways,
so it's recommended to spend some time thinking about what cases to have to simplify your solution.
Look out for situations where your solution can be simplified by closure properties.
A particularly handy one is $\mathrm{CFL} \cap \mathrm{regular}$ is a CFL.
\begin{example}
Show that $L = \{\mathtt{0}^k \mathtt{1}^{l} \mathtt{0}^m \mathtt{1}^{n} \mathtt{0}^k \mathtt{1}^{l} \mathtt{0}^m \mathtt{1}^{n} \mid k, l, m, n \geq 0\}$ is not context-free.
\end{example}
\begin{proof}
Suppose $L$ is context-free.
Then $$L' := L \cap \mathtt{0}^*\mathtt{1}^*\mathtt{0}^*\mathtt{1}^* = \{\mathtt{0}^a \mathtt{1}^{b} \mathtt{0}^a \mathtt{1}^{b} \mid a, b \geq 0\}$$
would be context-free, but it is not (see below), hence a contradiction.
So $L$ cannot be context-free.
To show that $L'$ is not context-free, assume for the sake of contradiction that it is.
Then for pumping length $p > 0$,
consider the string $s = \mathtt{0}^p \mathtt{1}^p \mathtt{0}^p \mathtt{1}^p \in L'$ ($|s| \geq p$).
Note that any way of writing $s = uvxyz$ ($|vxy| \leq p$, $|vy| > 0$) falls under one of two cases:
\begin{description}
\item[Case 1:] Either $v$ or $y$ crosses a block boundary.\footnote{
Here, a \textit{block} is defined to be a maximal substring with one distinct character,
so that $s$ consists of 4 blocks: $\mathtt{0}^p$, $\mathtt{1}^p$, $\mathtt{0}^p$, and $\mathtt{1}^p$.}
Then $uv^2xy^2z$ won't even be of the form $\mathtt{0}^* \mathtt{1}^* \mathtt{0}^* \mathtt{1}^*$,
since the $\mathtt{0}$'s and $\mathtt{1}$'s near the crossed block boundary will be mangled.
\item[Case 2:] Neither $v$ nor $y$ crosses a block boundary.
Then since $vxy$ can span at most 2 blocks, the 4 blocks in $uv^2xy^2z$ cannot all have the same length.
\end{description}
In either case, $uv^2xy^2z \notin L$, thus violating the pumping lemma.
\end{proof}
\item[Showing undecidable] The standard approach for showing undecidability is a reduction
from a known undecidable language such as $A_\mathsf{TM}$ to $L$.
In other words, assuming there's a decider $R$ for $L$, we can use it to construct a decider $S$ for $A_\mathsf{TM}$,
which is a contradiction since $A_\mathsf{TM}$ is undecidable.
One particular approach to constructing the reduction is the \textit{computation history method}.
When $L$ is of the form $$\{\langle P\rangle \mid \text{$P$ is an instance of X problem and $P$ has a solution}\},$$
there's a mapping reduction from $A_{\mathsf{TM}}$ to $L$ that converts $\langle M, w\rangle$ to a problem instance $P$
where checking whether $P$ has a solution is equivalent to checking whether there's an accepting computation
history of $M$ on $w$.
We can also use the recursion theorem in a proof by contradiction, as described earlier in the notes.
\begin{example}
Show that $ALL_\mathsf{LBA}$ is undecidable.
\end{example}
\begin{proof}
Reduce from $A_\mathsf{TM}$ using the computation history method.
Here, a ``problem instance'' $P$ is an LBA, and a ``solution'' is a string that the LBA doesn't accept.
Assuming $R$ decides $ALL_\mathsf{LBA}$, construct the decider $S$ that decides $A_\mathsf{TM}$:
$S =$ ``On $\langle M, w\rangle$,
\begin{enumerate}
\item Construct the LBA $B$ that checks that it's input is \textit{not} an accepting computation history of $M$ on $w$:
$B =$ ``On input $x$,
\begin{enumerate}
\item Check whether $x$ begins with the start configuration of $M$ on $w$. If not, \textit{accept}.
\item Check whether $x$ ends with an accepting configuration of $M$ on $w$. If not, \textit{accept}.
\item For each consecutive pair of configurations in $x$, check whether they violate $M$'s transition function.
This involves going back and forth between the two configurations, crossing off symbols as they get compared.
(The crosses are erased afterwards.) Once a violation is found, \textit{accept}.''
\end{enumerate}
\item Run $R$ on $B$. If $R$ accepts, then \textit{reject}. If $R$ rejects, then \textit{accept}.''
\end{enumerate}
$S$ works because $L(B) = \Sigma^*$ iff there's no accepting computation history of $M$ on $w$, i.e.,
$\langle M, w\rangle \notin A_\mathsf{TM}$.
\end{proof}
\item [Showing Turing-unrecognizable] The standard approach is to construct a
mapping reduction from a Turing-unrecognizable language such as $\overline{A_{\mathsf{TM}}}$ to $L$
($\overline{A_{\mathsf{TM}}} \leq_{\mathrm m} L$). This involves constructing a computable function
$f$ such that $x \in \overline{A_{\mathsf{TM}}} \iff f(x) \in L$.
\begin{example}
Show that $ALL_\mathsf{TM} = \{\langle M\rangle \mid \text{TM $M$ is such that $L(M) = \Sigma^*$}\}$
is Turing-unrecognizable.
\end{example}
\begin{proof}
We show $\overline{A_\mathsf{TM}} \leq_\mathrm{m} ALL_\mathsf{TM}$.
The mapping $f$ is defined as
$f(\langle M, w\rangle) = $ Turing machine $T$ given by
$T = $ ``On input $x$,
\begin{enumerate}
\item Interpret $x$ as a natural number and run $M$ on $w$ for $x$ steps.
\item If $M$ hasn't accepted, \textit{accept}. Otherwise, \textit{reject}.''
\end{enumerate}
If $M$ accepts $w$, then suppose it takes $n$ steps. Then $T$ rejects $n$ so $\langle T\rangle \not\in ALL_\mathsf{TM}$.
Conversely, if $\langle T\rangle \not\in ALL_\mathsf{TM}$, then there's an $x$ that $T$ rejects.
That means that $M$ accepts $w$ within $x$ steps.
\end{proof}
\end{description}
This concludes our review of problem-solving techniques and also our midterm review.
Besides reading through these notes, we recommend you practice with the sample midterms
to get a sense for what the midterm will look like.
We will also be holding midterm review sessions on Monday and Tuesday from 7:30pm to 9:30pm,
where you can get further practice with the content.