%
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%
\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color} %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{wrapfig}
\usepackage{hyperref}
\hypersetup{
colorlinks=true,
linkcolor=blue,
filecolor=magenta,
urlcolor=blue,
}
\usepackage{minted}
\usepackage{scrextend}
\usepackage{mathrsfs}
\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#9}
\author{Sachin Padmanabhan}
\date{\today}
\lhead{Sachin Padmanabhan}
\chead{Problem Set \#9}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2018}
\rfoot{\thepage}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}
\newcommand\VRule[1][\arrayrulewidth]{\vrule width #1}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Ber}{Bernoulli}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}
\definecolor{shadecolor}{gray}{0.9}
\theoremstyle{plain}
\newtheorem*{lem}{Lemma}
\theoremstyle{plain}
\newtheorem*{claim}{Claim}
\theoremstyle{definition}
\newtheorem*{answer}{Answer}
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\setlength{\parindent}{0pt}
\pagestyle{fancy}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\begin{document}
\maketitle
\section{Isn't Everything Undecidable?}
\textit{(We recommend reading the Guide to Self-Reference on the course website before attempting this problem.)} \\
In lecture, we proved that $A_{\text{TM}}$ and the halting problem are undecidable -- that, in some sense, they're beyond the reach of algorithmic problem-solving. The proofs we used involved the nuanced technique of
self-reference, which can seem pretty jarring and weird the first time you run into it. The good news is
that with practice, you'll get the hang of the technique pretty quickly! \\
One of the most common questions we get about self-reference proofs is why you can't just use a self-reference
argument to prove that \textit{every} language is undecidable. As is often the case in Theoryland, the best
way to answer this question is to try looking at some of the ways you might use self-reference to prove
that \textit{every} language is undecidable, then see where those arguments break down. \\
To begin with, consider this proof:
\vspace{-1em}
\begin{quote}
\begin{thm}
All languages are undecidable.
\end{thm}
\begin{proof}
Suppose for the sake of contradiction that there is a decidable language $L$. This
means there's a decider for $L$; call it \texttt{inL}. \\
Now, consider the following program, which we'll call $P$:
\begin{addmargin}[5em]{0em}
\begin{minted}{c++}
int main() {
string input = getInput();
/* Do the opposite of what's expected. */
if (inL(input)) {
reject();
} else {
accept();
}
}
\end{minted}
\end{addmargin}
Now, given any input $w$, either $w \in L$ or $w \not\in L$. If $w \in L$, then the call to \texttt{inL(input)}
will return true, at which point $P$ rejects $w$, a contradiction! Otherwise, if $w \not\in L$, then
the call to \texttt{inL(input)} will return false, at which point $P$ accepts $w$, a contradiction! \\
In both cases we reach a contradiction, so our assumption must have been wrong.
Therefore, no languages are decidable.
\end{proof}
\end{quote}
This proof has to be wrong because we know of many decidable languages.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item What's wrong with this proof? Be as specific as possible.
\textit{\textcolor{blue}{ Go one sentence at a time and check that each claim is correct. Something is fishy here. }}
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Here's another incorrect proof that all languages are undecidable:
\vspace{-1em}
\begin{quote}
\begin{thm}
All languages are undecidable.
\end{thm}
\begin{proof}
Suppose for the sake of contradiction that there is a decidable language $L$. This
means that there is some decider $D$ for the language $L$, which we can represent in software
as a method \texttt{willAccept}. Then we can build the following self-referential program,
which we'll call $P$:
\begin{addmargin}[5em]{0em}
\begin{minted}{c++}
int main() {
string me = mySource();
string input = getInput();
/* See whether we'll accept, then do the opposite. */
if (willAccept(me, input)) {
reject();
} else {
accept();
}
}
\end{minted}
\end{addmargin}
Now, given any input $w$, program $P$ either accepts $w$ or it does not accept $w$. If $P$ accepts
$w$, then the call to \texttt{willAccept(me, input)} will return true, at which point $P$
rejects $w$, a contradiction! Otherwise, we know that $P$ does not accept $w$, so the call to
\texttt{willAccept(me, input)} will return false, at which point $P$ accepts $w$, a contradiction! \\
In both cases we reach a contradiction, so our assumption must have been wrong.
Therefore, no languages are decidable.
\end{proof}
\end{quote}
It's a nice read, but this proof isn't correct.
\begin{enumerate}[resume*]
\item What's wrong with this proof? Be as specific as possible.
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Many of the examples we've seen of undecidable languages involve checking for properties of Turing machines
or computer programs, which might give you the sense that \textit{every} question you might want to ask
about TMs or programs is undecidable. That isn't the case, though, and this question explores why. \\
Consider the following language $L$:
\begin{equation*}
L = \{\ \langle P \rangle \ |\ P \text{ is a syntactically valid C++ program }\}
\end{equation*}
Below is a purported proof that $L$ is undecidable:
\vspace{-1em}
\begin{quote}
\begin{thm}
The language $L$ is undecidable.
\end{thm}
\begin{proof}
Suppose for the sake of contradiction that $L$ is decidable. That means that there's
some decider $D$ for $L$, which we can represent in software as a function \texttt{isSyntacticallyValid}
that takes as input a program and then returns whether that program has
correct syntax. Given this function, consider the following program $P$:
\begin{addmargin}[5em]{0em}
\begin{minted}{c++}
int main() {
string me = mySource();
/* Execute a line based on whether our syntax is right. */
if (isSyntacticallyValid(me)) {
oops, this line of code isn?t valid C++!
} else {
int num = 137; // Perfectly valid syntax!
}
}
\end{minted}
\end{addmargin}
Now, either this program $P$ is syntactically valid or it is not. If $P$ has valid syntax, then
when $P$ is run on any input, it will get its own source code, determine that it is syntactically
valid, then execute a syntactically invalid line of code -- a contradiction! Otherwise,
if $P$ is not syntactically valid, then when $P$ is run on any input, it will get its own
source code, determine that it is not syntactically valid, at which point it executes a
perfectly valid line of C++ code -- a contradiction! \\
In either case we reach a contradiction, so our assumption must have been incorrect.
Therefore, $L$ is undecidable.
\end{proof}
\end{quote}
This proof, unfortunately, is incorrect.
\begin{enumerate}[resume*]
\item What's wrong with this proof? Be as specific as possible.
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\end{enumerate}
\section{Password Checking}
\textit{(We recommend reading the Guide to Self-Reference on the course website before attempting this problem.)} \\
If you're an undergraduate here, you've probably noticed that the dorm staff have master keys they can
use to unlock any of the doors in the residences. That way, if you ever lock yourself out of your room,
you can, sheepishly, ask for help back in. (Not that I've ever done that or anything.) Compare this to a
password system. When you log onto a website with a password, you have the presumption that your password
is the only possible password that will log you in. There shouldn't be a ``master key'' password that
can unlock any account, since that would be a huge security vulnerability. But how could you tell? If you
had the source code to the password checking system, could you figure out whether your password was
the only password that would grant you access to the system? \\
Let's frame this question in terms of Turing machines. If we wanted to build a TM password checker,
``entering your password'' would correspond to starting up the TM on some string, and ``gaining access''
would mean that the TM accepts your string. Let's suppose that your password is the string
\texttt{iheartquokkas}. A TM that would work as a valid password checker would be a TM $M$ where
$\mathscr{L}(M) = \{\texttt{iheartquokkas}\}$: the TM accepts your string, and it doesn't accept anything else.
Given a TM, is there some way you could tell whether the TM was a valid password checker? \\
Consider the following language $L$:
\begin{center}
$L = \{\ \langle M\rangle\ |\ M$ is a TM and $\mathscr{L}(M) = \{\texttt{iheartquokkas}\}\ \}$
\end{center}
Your task in this problem is to prove that $L$ is undecidable (that is, $L \not\in \mathbf{R}$). This means that there's no algorithm that can mechanically check whether a TM is suitable as a password checker. Rather than dropping
you headfirst into this problem, we've split this problem apart into a few smaller pieces. \\
Let's suppose for the sake of contradiction that $L \in R$. That means that there is some function \\
\begin{addmargin}[13em]{0em}
\begin{minted}{c++}
bool isPasswordChecker(string program)
\end{minted}
\end{addmargin}
with the following properties:
\begin{itemize}
\item If \texttt{program} is the source of a program that accepts just the string \texttt{iheartquokkas}, then calling \\
\texttt{isPasswordChecker(program)} will return true.
\item If \texttt{program} is not the source of a program that accepts just the string \texttt{iheartquokkas}, then calling
\texttt{isPasswordChecker(program)} will return false.
\end{itemize}
We can try to build a self-referential program that uses the isPasswordChecker function to obtain a contradiction.
Here's a first try: \\
\begin{addmargin}[5em]{0em}
\begin{minted}{c++}
int main() {
string me = mySource();
string input = getInput();
if (isPasswordChecker(me)) {
reject();
} else {
accept();
}
}
\end{minted}
\end{addmargin}
This code is, essentially, a (minimally) modified version of the self-referential program we used to get a
contradiction for the language $A_{\text{TM}}$.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Prove that the above program $P$ is not a valid password checker.
\textit{\textcolor{blue}{ What is the definition of a password checker? Based on that, what do you need to prove to show that P is
not a password checker? }}
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Suppose that this program is \textit{\textbf{not}} a valid password checker. Briefly explain why no contradiction
arises in this case -- no formal justification is necessary.
\textit{\textcolor{blue}{ A good question to think about in the course of answering part (ii) of this problem: this program is very
close to the one from the proof that $A_{TM}$ is not decidable. Why \underline{do} you get a contradiction in the original
proof that $A_{TM}$ is undecidable? Why doesn't that same contradiction work here? }}
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Ultimately, the goal of building a self-referential program here is to have the program cause a contradiction
regardless of whether or not it's a password checker. As you've seen in part (ii), this particular program
does not cause a contradiction if it isn't a password checker. Consequently, if we want to prove that
$L \not\in \mathbf{R}$, we need to modify it so that it leads to a contradiction in the case where it is not a password
checker.
\begin{enumerate}[resume*]
\item Modify the above code so that it causes a contradiction regardless of whether it's a password
checker. Then, briefly explain why your modified program is correct. (No formal proof is necessary
here; you're going to do that in the next step.)
\textit{\textcolor{blue}{ Follow the advice from the Guide to Self-Reference. Write out a specification of what your self-referential
program is trying to do. Based on that, craft code for each of the two cases. }}
\begin{shaded}
\begin{minted}{c++}
// write some code here
\end{minted}
Provide justification here.
\end{shaded}
\item Formalize your argument in part (iii) by proving that $L \not\in \mathbf{R}$. Use the proof that $A_{\text{TM}} \not\in \mathbf{R}$ as a template for your proof.
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
\section{$L_D$, Cantor's Theorem, and Diagonalization}
Here's another perspective of the proof that $L_D \not\in \mathbf{RE}$. Suppose we let $TM$ be the set of all encodings of
Turing machines. That is,
\begin{equation*}
TM = \{\ \langle M\rangle\ |\ M\text{ is a TM}\ \}
\end{equation*}
We can then define a function $\widehat{\mathscr{L}}\ :\ TM \rightarrow \wp(TM)$ as follows:
\begin{equation*}
\widehat{\mathscr{L}}(\langle M\rangle) = \mathscr{L}(M) \cap TM
\end{equation*}
This question explores some properties of this function.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Briefly describe, in plain English, what $\widehat{\mathscr{L}}(\langle M\rangle)$ represents.
\textit{\textcolor{blue}{ You shouldn't need more than a sentence. }}
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item Trace through the proof of Cantor's theorem from the Guide to Cantor's Theorem, assuming that
the choice of the function $f$ in the proof is the function $\widehat{\mathscr{L}}$. What is the set $D$ that is produced in
the course of the proof? Why?
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
\section{Double Verification}
This problem explores the following beautiful and fundamental theorem about the relationship between
the \textbf{R} and \textbf{RE} languages:
\begin{center}
If $L$ is a language, then $L \in \mathbf{R}$ if and only if $L \in \mathbf{RE}$ and $\overline{L} \in \mathbf{RE}$
\end{center}
This theorem has a beautiful intuition: it says that a language $L$ is decidable ($L \in \mathbf{R}$) precisely if for every
string in the language, it's possible to prove it's in the language ($L \in \mathbf{RE}$) and, simultaneously, for every
string not in the language, it's possible to prove that the string is not in the language ($\overline{L} \in \mathbf{RE}$). In this
problem, we're going to ask you to prove one of the two directions of this theorem. \\
Let $L$ be a language where $L \in \mathbf{RE}$ and $\overline{L} \in \mathbf{RE}$. This means that there's a verifier $V_{yes}$ for $L$ and a verifier $V_{no}$ for $\overline{L}$. In software, you could imagine that $V_{yes}$ and $V_{no}$ correspond to methods with these signatures: \\
\begin{addmargin}[13em]{0em}
\begin{minted}{c++}
bool imConvincedIsInL(string w, string c)
bool imConvincedIsNotInL(string w, string c)
\end{minted}
\end{addmargin}
Prove that $L \in \mathbf{R}$ by writing pseudocode for a function \\
\begin{addmargin}[17em]{0em}
\begin{minted}{c++}
bool isInL(string w)
\end{minted}
\end{addmargin}
that accepts as input a string $w$, then returns true if $w \in L$ and returns false if $w \not\in L$. Then, write a brief
proof explaining why your pseudocode meets these requirements. You don't need to write much code
here. If you find yourself writing ten or more lines of pseudocode, you're probably missing something. \\
The theorem you proved in this problem is extremely useful for building an intuition for what languages
are decidable. You'll see this in the next problem. \\
\textit{\textcolor{blue}{ What other constructions have we done on verifiers? How did they work? }}
\begin{shaded}
\begin{minted}{c++}
// write some code here
\end{minted}
Provide a proof here.
\end{shaded}
\section{The Lava Diagram}
Below is a Venn diagram showing the overlap of different classes of languages we've studied so far. We
have also provided you a list of twelve numbered languages. For each of those languages, draw where in
the Venn diagram that language belongs. As an example, we've indicated where Language 1 and Language
2 should go. No proofs or justifications are necessary -- the purpose of this problem is to help you
build a better intuition for what makes a language regular, \textbf{R}, \textbf{RE}, or none of these. \\
We \textit{\textbf{strongly}} recommend reading over the Guide to the Lava Diagram before starting this problem. \\
To submit your answers, edit the file $\mathsf{LavaDiagram.h}$ in the $\mathsf{src/}$ directory of the starter files for this
problem set.
\begin{center}
\begin{tikzpicture}
\draw (-2,0) ellipse [x radius=1.5cm, y radius=1.5cm];
\draw (-1.6,0) node {\textbf{REG}};
\draw (-1,0) ellipse [x radius=3cm, y radius=2.25cm];
\draw (1.3,0) node {\textbf{R}};
\draw (0,0) ellipse [x radius=4.5cm, y radius = 3cm];
\draw (3.75, 0) node {\textbf{RE}};
\draw (0,3.5) node {\textbf{ALL}};
\draw (-5.5,-4) rectangle (5.5, 4.5);
\draw (-2.8,0.2) node {\textbf{1}};
\draw (2,3.75) node {\textbf{2}};
\end{tikzpicture}
\end{center}
\begin{enumerate}
\item $\Sigma^*$
\item $L_D$
\item $\{\ a^n\ |\ n \in \N\ \}$
\item $\{\ a^n\ |\ n \in \N$ and is a multiple of 137 $\}$
\item $\{\ 1^n+1^m \stackrel{?}{=} 1^{n+m}\ |\ m, n \in \N\ \}$
\item $\{\ \langle M\rangle\ |\ M$ is a Turing machine and $\mathscr{L}(M) \ne \varnothing\ \}$
\item $\{\ \langle M\rangle\ |\ M$ is a Turing machine and $\mathscr{L}(M) = \varnothing\ \}$
\item $\{\ \langle M\rangle\ |\ M$ is a Turing machine and $\mathscr{L}(M) = L_D\ \}$
\item $\{\ \langle M, n\rangle\ |\ M$ is a TM, $n \in \N$, and $M$ \textit{\textbf{accepts}} all strings in its input alphabet of length at most $n\ \}$
\item $\{\ \langle M, n\rangle\ |\ M$ is a TM, $n \in \N$, and $M$ \textit{\textbf{rejects}} all strings in its input alphabet of length at most $n\ \}$
\item $\{\ \langle M, n\rangle\ |\ M$ is a TM, $n \in \N$, and $M$ \textit{\textbf{loops}} on all strings in its input alphabet of length at most $n\ \}$
\item $\{\ \langle M_1, M_2, M_3, w\rangle\ |\ M_1, M_2,$ and $M_3$ are TMs, $w$ is a string, and at least two of
$M_1, M_2,$ and $M_3$ accept $w.\ \}$
\end{enumerate}
\begin{shaded}
Submit your edited $\mathsf{LavaDiagram.h}$ file on Gradescope.
\end{shaded}
\section{The Big Picture}
We have covered a \textit{lot} of ground in this course throughout our whirlwind tour of computability and complexity
theory. This last question surveys what we have covered so far by asking you to see how everything
we have covered relates. \\
Take a minute to review the hierarchy of languages we explored:
\begin{equation*}
\mathbf{REG \subsetneq CFL \subsetneq P \stackrel{?}{=} NP \subsetneq R \subsetneq RE \subsetneq ALL}
\end{equation*}
The following questions ask you to provide examples of languages at different spots within this hierarchy.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Give an example of a regular language. How might you prove that it is regular? You don't need to
actually prove that it's regular -- just tell us what proof technique you'd use.
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item Give an example of a context-free language is not regular. How might you prove that it is context-free?
How might you prove that it is not regular? Just tell us what techniques you'd use for these
proofs; no formal proof is actually necessary here.
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item Give an example of a language in \textbf{P}.
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item Give an example of an \textbf{NP}-complete language. \textit{(We'll talk about this on Wednesday.)}
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item Give an example of a language in \textbf{RE} not contained in \textbf{R}. How might you prove that it is \textbf{RE}?
How might you prove that it is not contained in \textbf{R}? Again, we just need to proof techniques you'd
use, not actual formal proofs.
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item Give an example of a language that is not in \textbf{RE}. How might you prove it is not contained in \textbf{RE}? As before, we're just looking for proof techniques, not actual proofs.
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\end{enumerate}
\section{Class Participation Opt-Out}
You have the option to choose to shift the 5\% weight of your grade that's normally associated with your
class participation onto the final exam. If you do this, you will receive no credit based on participation,
and your final exam will be worth 40\% of your grade rather than the regular 35\%. \\
If you'd like to opt out of your class participation grade and shift the weight to the final, follow \href{https://docs.google.com/forms/d/e/1FAIpQLSdjYKor9b_y561gs1cx6r28EjlWKuUy2QyEVzOHoP14B6CdWw/viewform}{\underline{this link}}
and fill out the form. \textit{\textbf{Do not submit your answer through GradeScope; Keith and Cynthia won't see it.}} \\
If you'd like to keep 5\% of your grade for participation, you don't need to do anything. You're all set!
\section*{Optional Fun Problem One: Quine Relays (1 Point Extra Credit)}
Write four different C++ programs with the following properties:
\begin{itemize}
\item Running the first program prints the complete source code of the second program.
\item Running the second program prints the complete source code of the third program.
\item Running the third program prints the complete source code of the fourth program.
\item Running the fourth program prints the complete source code of the first program.
\item None of the programs perform any kind of file reading.
\end{itemize}
In other words, we'd like a collection of four different programs, each of which prints the complete source
of the next one in the sequence, wrapping back around at the end. You can download starter files for this
assignment from the course website and should submit your files through GradeScope. \\
\textit{\textcolor{blue}{ This is actually a really fun problem to try. Once you figure out the trick, it's not that hard to code it up. }}
\begin{shaded}
Submit files on Gradescope.
\end{shaded}
\section*{Optional Fun Problem Two: P $\stackrel{?}{=}$ NP (Worth an A+, \$1,000,000, and a Ph.D)}
Prove or disprove: $P = NP$. \\
\textit{\textcolor{blue}{ Take fifteen minutes and try this. Seriously. And if you can't crack this problem, feel free to submit your
best effort, or the silliest answer you can think of. }}
\begin{shaded}
Provide a proof or disproof here.
\end{shaded}
% Congrats, you made it to the end of the last 103 pset! ^_^
\end{document}