%
% 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}
\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 --- Fall 2017}
\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 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();
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}
\newpage
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\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}
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();
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}
\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{(Hint: Before you attempt to prove
this, make sure you know exactly what it is that you are trying to show.)}
\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.
\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.)
\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{(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.
\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 strongly recommend reading over the Guide to the Lava Diagram before starting this problem.
\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^*$
\begin{shaded}
\begin{answer}
\textbf{REG}
\end{answer}
\end{shaded}
\item $L_D$
\begin{shaded}
\begin{answer}
\textbf{ALL}
\end{answer}
\end{shaded}
\item $\{\ a^n\ |\ n \in \N\ \}$
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item $\{\ a^n\ |\ n \in \N$ and is a multiple of 137 $\}$
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item $\{\ 1^n+1^m \stackrel{?}{=} 1^{n+m}\ |\ m, n \in \N\ \}$
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item $\{\ \langle M\rangle\ |\ M$ is a Turing machine and $\mathscr{L}(M) \ne \varnothing\ \}$
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item $\{\ \langle M\rangle\ |\ M$ is a Turing machine and $\mathscr{L}(M) = \varnothing\ \}$
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\item $\{\ \langle M\rangle\ |\ M$ is a Turing machine and $\mathscr{L}(M) = L_D\ \}$
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\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\ \}$
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\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\ \}$
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\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\ \}$
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\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.\ \}$
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\end{enumerate}
\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.
In each case, you should provide an example of a language, but you don't need to formally prove that it
has the properties required. Instead, describe a proof technique you could use to show that the language
has the required properties. There are many correct answers to these problems, and we'll accept any of
them.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Give an example of a regular language. How might you prove that it is regular?
\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?
\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}?
\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}?
\begin{shaded}
\begin{answer}
Provide an answer here.
\end{answer}
\end{shaded}
\end{enumerate}
\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.
\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$.
\begin{shaded}
Provide a proof or disproof here.
\end{shaded}
% Congrats, you made it to the end of the last 103 pset! ^_^
\end{document}