% % 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. % % Updated for Fall 2018 by Michael Zhu % Updated for Winter 2020 by Cynthia Lee \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{Your Name(s) Here} \date{\today} \lhead{Your Name(s) Here} \chead{Problem Set \#9} \rhead{\today} \lfoot{} \cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2020} \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}} % start MZ \let\oldemptyset\emptyset \renewcommand{\emptyset}{\text{\O}} \renewcommand\qedsymbol{$\blacksquare$} \newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol} \renewcommand{\emph}[1]{\textit{\textbf{#1}}} \newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}} \usepackage{stmaryrd} \usepackage{minted} \usepackage{mathtools} \usepackage{alltt} \newcommand{\ttt}[1]{\texttt{#1}} \newcommand{\match}[1]{\textbf{\underline{#1}}} \usepackage{parskip} \newcommand{\lcurly}{\textbf{\ttt{\{}}} \newcommand{\rcurly}{\textbf{\ttt{\}}}} \newcommand{\coRE}{\text{co-}\mathbf{RE}} \newcommand{\ATM}{A_{\text{TM}}} \newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}} % end MZ \begin{document} \maketitle \annotate{Because this problem set is due on the last day of class, no late days may be used and no late submissions will be accepted. Sorry about that! On the plus side, we'll release solutions as soon as the problem set comes due, so you can study them for Monday's final exam.} \annotate{Grading note: This pset will be graded CHECKPOINT STYLE. In other words, as long as you show some kind of attempt for the problem, you will get full credit. It's really just to help you study for the exam. } \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: \begin{quote} \emph{Theorem:} All languages are undecidable. \emph{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. \qedsymbol \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. \annotate{Go one sentence at a time and check that each claim is correct. Something is fishy here.} \begin{shaded} Provide an answer here. \end{shaded} \end{enumerate} Here's another incorrect proof that all languages are undecidable: \begin{quote} \emph{Theorem:} All languages are undecidable. \emph{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. \qedsymbol \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. \annotate{This one is subtle. Pull up the proof that $A_{TM}$ is undecidable and compare this proof and that one side-by-side, going one sentence at a time if you need to.} \begin{shaded} Provide an answer here. \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: \begin{quote} \emph{Theorem:} The language $L$ is undecidable. \emph{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. \qedsymbol \end{quote} This proof, unfortunately, is incorrect. \begin{enumerate}[resume*] \item What's wrong with this proof? Be as specific as possible. \begin{shaded} Provide an answer here. \end{shaded} \end{enumerate} \pagebreak \section{Password Checking} \textit{(We recommend reading the Guide to Self-Reference on the course website before attempting this problem.)} \\ 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 your password is the string \texttt{iheartquokkas}. We'll say that a \emph{password checker} is a TM $M$ where $$\mathscr{L}(M) = \{\texttt{iheartquokkas}\};$$ that is, the TM accepts your password \texttt{iheartquokkas}, and it doesn't accept anything else. Given a TM, is there some way you could tell whether the TM was a password checker? Consider the following language $L$: \begin{center} $L = \{\ \langle M\rangle\ |\ M$ is a TM and $M$ is a password checker\ \}. \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 \mathbf{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 \ttt{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 \ttt{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 password checker. \annotate{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 \emph{not} a valid password checker. Briefly explain why no contradiction arises in this case -- no formal justification is necessary. \annotate{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} Provide an answer here. \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. \annotate{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} \end{enumerate} \pagebreak \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 checkIsInL(string w, string c) bool checkIsNotInL(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. \annotate{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} \pagebreak \section{Unrecognizable Languages} Consider the following language: \begin{equation*} L_{DV} = \{\ \langle M \rangle \ |\ M \text{ is a TM, and for every $w\in \Sigma^*$, $M$ does not accept $\langle M, w \rangle$} \ \}. \end{equation*} Prove that $L_{DV} \not\in \mathbf{RE}$. As a hint, this is the diagonalization language for verifiers. \begin{shaded} Provide a proof here. \end{shaded} \pagebreak \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 \emph{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 $\{\ \ttt{a}^n\ |\ n \in \N\ \}$ \item $\{\ \ttt{a}^n\ |\ n \in \N$ and is a multiple of 137 $\}$ \item $\{\ \ttt{1}^n\ttt{+1}^m \stackrel{\ttt{?}}{\ttt{=}} \ttt{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 \mid M_1, M_2,$ and $M_3$ are TMs, $w$ is a string, and at least two of \\ \hphantom{$\{\ \langle M_1, M_2, M_3, w\rangle \mid$} $M_1, M_2,$ and $M_3$ accept $w.\ \}$ \end{enumerate} \begin{shaded} Submit your edited $\mathsf{LavaDiagram.h}$ file on Gradescope. \end{shaded} \pagebreak \section{co-RE, Disjoint Unions, and Terrifyingly Difficult Problems} When we first saw that $\ATM$ is undecidable, we could at least take consolation in the fact that $\ATM$ is recognizable. Then we discovered that $L_D$ is unrecognizable, and up to now we haven't had a comforting fact to fall back on. But there is something about $L_D$ we can console ourselves with: the complement of $L_D$, the language $\overline{L}_D$, is an $\mathbf{RE}$ language.\footnote{While we're not going to ask you to formally prove that $\overline{L}_D$ is an $\mathbf{RE}$ language, we would \textit{definitely} recommend taking a few minutes to ponder how you'd build a recognizer or verifier for it.} In other words, while there's no general way to prove that some TM \textit{will not} accept its own encoding, there \textit{is} a general way to prove that some TM \textit{will} accept its own encoding. The fact that $L_D$ isn't an $\mathbf{RE}$ language while $\overline{L}_D$ is still in $\mathbf{RE}$ suggests that there might be a bit more to the computability landscape than just $\mathbf{R}$ and $\mathbf{RE}$. And indeed there is: the same way that $\ATM$ is the poster child of an $\mathbf{RE}$ language, the language $L_D$ is the poster child of a $\coRE$ language. Formally speaking, the class $\coRE$ consists of all the languages whose complement is an $\mathbf{RE}$ language: \begin{equation*} \coRE = \{\ L \mid \overline{L} \in \mathbf{RE}\ \}. \end{equation*} Intuitively speaking, the $\coRE$ languages are languages where if you have a string that \textit{isn't} in the language, there's some easy way to prove that it isn't in the language. \begin{enumerate}[label=\roman*.] \item Prove that $A_{\text{TM}} \notin \coRE$ \annotate{You haven't seen the term ``$\coRE$'' before, but you have seen something like this somewhere.} \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} At this point, we have an $\mathbf{RE}$ language that's not in $\coRE$ ($\ATM$) and a $\coRE$ languages that's not in $\mathbf{RE}$ ($L_D$). As a coda to our treatment of unsolvable problems, let's see a language that's neither in $\mathbf{RE}$ nor $\coRE$. In other words, there's no general way to prove that strings in that language are indeed in that language, nor is there way to prove that strings not in that language are indeed not in that language. Yikes! In what follows, let's assume all languages are over the alphabet $\Sigma = \{\ttt{0}, \ttt{1}\}$. Given two languages $A$ and $B$ over $\Sigma$, the \emph{disjoint union} of $A$ and $B$, denoted $\emph{A} \cupdot \emph{B}$, is the language \begin{equation*} A \cupdot B = \ttt{0}A \cup \ttt{1}B \end{equation*} For example, if $A = \{1, 10, 100, 1000 \}$ and $B = \{\varepsilon, \ttt{0}, \ttt{1}, \ttt{00}, \ttt{01}, \ttt{10}, \ttt{11} \}$, then $A \cupdot B$ is the language \begin{equation*} A \cupdot B = \{\ \ttt{01}, \ttt{010}, \ttt{0100}, \ttt{01000}, \ttt{1}, \ttt{10}, \ttt{11}, \ttt{100}, \ttt{101}, \ttt{110}, \ttt{111} \ \} \end{equation*} Notice how each string in $A \cupdot B$ is tagged with which language it originated in. Any string that starts with \ttt{0} came from $A$, and any string that starts with \ttt{1} came from $B$. \begin{enumerate}[resume*] \item Let $A$ and $B$ be languages where $A \cupdot B \in \mathbf{RE}$. Prove that $A \in \mathbf{RE}$. Structure your proof like what you did in Problem Four: assume you have code for a verifier or recognizer for $A \cupdot B$, use it to write code for a verifier or recognizer for $A$, then explain why that code works as intended. \begin{shaded} Provide a proof here. \end{shaded} \item Let $A$ and $B$ be languages where $A \cupdot B \in \coRE$. Prove that $A \in \coRE$. \annotate{If you have a language in $\coRE$, what can you say about that language? If you want to prove that a language is in $\coRE$, what do you need to prove about that language?} \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} The results you proved in parts (ii) and (iii) of this problem can be extended to show that if $A \cupdot B \in \mathbf{RE}$, then $B \in \mathbf{RE}$, and if $A \cupdot B \in \coRE$, then $B \in \coRE$, though you don't need to prove this. \begin{enumerate}[resume*] \item Let $L$ be an undecidable language. Prove $L \cupdot \overline{L} \notin \mathbf{RE}$ and $L \cupdot \overline{L} \notin \coRE$. \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} Your result from part (iv) shows there are problems harder than $\ATM$ and $L_D$; one example is $L_D \cupdot \overline{L}_D$. But even this nightmarish problem sits within a class of problems that can still be touched by computing power, if only in a very weak sense. Specifically, $L_D \cupdot \overline{L}_D$ is what's called a $\Delta_2^0$ language, where $\Delta_2^0$ is a class of languages that contains all of $\mathbf{RE}$ and $\coRE$, plus a bunch of other problems. And $\Delta_2^0$ itself sits inside even larger classes of languages, stretching outward to infinity. Want to learn more? Take Phil 152! \begin{shaded} Submit files on Gradescope. \end{shaded} \pagebreak \section*{Optional Fun Problem: CS103 Takes Over TikTok (Extra Credit)} Make a TikTok about some concept from CS103. Of course it can be really silly, but ideally it could in some small way help future CS103 students remember that concept for the final exam! To submit, post a link to your TikTok on Piazza and/or email it to cs103-win1920-staff@lists.stanford.edu. \section*{Optional Fun Problem: Quine Relays (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. \section*{Grand Challenge Problem: P $\stackrel{?}{=}$ NP (Worth an A+, \$1,000,000, and a Ph.D)} Prove or disprove: $\mathbf{P} = \mathbf{NP}$. \begin{shaded} Provide a proof or disproof here. \end{shaded} % Congrats, you made it to the end of the last 103 pset LaTeX template! \end{document}