Problem Set 9

Due Friday, December 3 at 2:30 pm Pacific

What problems are beyond our capacity to solve? Why are they so hard? And why is anything that we've discussed this quarter at all practically relevant? In this problem set – the last one of the quarter! – you'll explore the absolute limits of computing power.

Before beginning, we recommend reading

• the Guide to Self-Reference, which does a deep-dive into undecidability via self-reference, and
• the Guide to the Lava Diagram, which explores how to classify languages.

As always, please feel free to drop by office hours or ask on Ed if you have any questions. We'd be happy to help out.

Good luck, and have fun!

Starter Files

Here are the starter files for the problems you'll submit electronically:

📦 PS9 Starter Files

Unpack the files somewhere convenient and open up the bundled project.

If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:

🖋 PS9 $\LaTeX$ Template

Problem One: Isn’t Everything Undecidable?

(We recommend reading the Guide to Self-Reference before attempting this problem.)

In lecture, we proved that $A_{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 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:

bool trickster(string w) {
    return !inL(w);
}

This proof has to be wrong because we know of many decidable languages.

1. What’s wrong with this proof? To answer this question, give us a specific claim made in the proof that is incorrect, then explain why it's incorrect.

   Go one sentence at a time. For each claim that’s made, ask yourself – why, specifically, is this statement correct? 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.

Here’s another incorrect proof that all languages are undecidable:

bool trickster(string w) {
    string me = /* source code for trickster */;

    /* See whether we'll accept, then do the opposite. */
    return !willAccept(me, w);
}

It’s a nice read, but this proof isn’t correct.

2. What’s wrong with this proof? To answer this question, give us a specific claim made in the proof that is incorrect, then explain why it's incorrect.

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 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$:

Below is a purported proof that $L$ is undecidable:

bool trickster() {
    string me = /* source code for trickster */;

    /* 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!
    }
}

This proof, unfortunately, is incorrect.

3. What’s wrong with this proof? To answer this question, give us a specific claim made in the proof that is incorrect, then explain why it's incorrect.

Problem Two: An Undecidable Problem

(We recommend reading the Guide to Self-Reference before starting this problem.)

In this problem, we'll explore the language $R_{TM}$, which is defined as follows:

This is basically $A_{TM}$, with the word "accept" replaced with "reject." The goal of this problem is to prove that $R_{TM}$ is undecidable: there's no way to automatically determine whether an arbitrary TM will reject an arbitrary string.

To begin with, let's assume $R_{TM}$ is decidable. That means there's a decider for it. In software, we can represent such a decider as a function

bool willReject(string function, string input);

that has certain properties.

1. Fill in the blanks below to describe the behavior of the willReject function. No justification is required.

   • If willReject(function, input) returns true, then $\blank$.
   • If willReject(function, input) returns false, then $\blank$.

   You know that willReject is a decider for $R_{TM}$. Use an analysis similar to the one we did in lecture for $A_{TM}$ to work out what willReject must do on its inputs.

As in the proof that $A_{TM}$ is undecidable, we'll next define a trickster function that uses self-reference to exhibit contradictory behavior.

2. Fill in the blank in trickster below so that trickster rejects its input if and only if trickster doesn't reject its input. No justification is required.

   bool trickster(string input) {
       string me = /* source code of trickster */;
       return ____;
   }
   

We now have all the pieces we need to write the formal proof.

3. Prove that $R_{TM} \notin \rlangs$.

Problem Three: Password Checking

Let's begin with an (admittedly silly) formal definition. We'll say that a function bool checkPassword(string input) is a secure password checker if

• checkPassword("iheartquokkas") returns true, and
• checkPassword(w) does not return true for any $w \ne \mathtt{iheartquokkas}$.

In other words, a secure password checker will accept exactly one string (namely, the amazing password iheartquokkas) and won't accept anything else.

We'd like to write a program that checks whether a function is a secure password checker. (In other words, we're not interested in implementing a password checker ourselves. Instead, we want to check checking whether a separate function is a password checker. That's something you might want to do if you've implemented a website and want to make sure the login page works correctly, for example.) Ideally, we could implement a function

bool isSecurePasswordChecker(string function);

that takes as input the source code of a function function, then does the following:

• If function is a secure password checker, then isSecurePasswordChecker(function) returns true.
• If function is not a secure password checker, then isSecurePasswordChecker(function) returns false.

Unfortunately, it's not possible to implement the isSecurePasswordChecker function so that it meets the above requirements. Prove why not.

Problem Four: Double Verification

This problem explores the following beautiful and fundamental theorem about the relationship between the $\rlangs$ and $\relangs$ languages:

If $L$ is a language, then $L \in \rlangs$ if and only if $L \in \relangs$ and $\overline{L} \in \relangs$.

This theorem has a beautiful intuition: it says that a language $L$ is decidable $(L \in \rlangs)$ precisely if for every string in the language, it's possible to prove it's in the language $(L \in \relangs)$ 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 \relangs)$. 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 \relangs$ and $\overline{L} \in \relangs$. 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 functions with these signatures:

bool checkInL(string w, string c)

bool checkInLBar(string w, string c)

Since these functions represent verifiers, they have the following properties:

• checkInL and checkInLBar halt on all inputs.
• $\forall w \in \Sigma^\star. (w \in L \leftrightarrow \exists c \in \Sigma^\star. \mathtt{checkInL(w, c)}\text{ returns true})\text.$
• $\forall w \in \Sigma^\star. (w \notin L \leftrightarrow \exists c \in \Sigma^\star. \mathtt{checkInLBar(w, c)}\text{ returns true})\text.$

Show that $L \in \rlangs$ by writing pseudocode for a function

bool isInL(string w)

that accepts as input a string $w$, then returns true if $w \in L$ and returns false if $w \notin L$. 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. No justification is required.

Problem Five: The Lava Diagram

(We recommend reading the Guide to the Lava Diagram before starting this problem.)

Download the starter files for Problem Set 9 and extract them somewhere convenient. Run the provided program and choose “The Lava Diagram.” You’ll be presented with 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, $\rlangs$, $\relangs$, or none of these.

Use the provided to test your solution locally, then submit the file res/LavaDiagram.answers to Gradescope when you’re done.

1. $\Sigma^\star$

2. $L_D$

3. $\Set{ \mathtt{a}^n \suchthat n \in \naturals }$

4. $\Set{ \mathtt{a}^n \suchthat n \in \naturals \text{ and } n \text{ is a multiple of } 137 }$

5. $\Set{ \mathtt{1}^m\mathtt{+1}^n\mathtt{=1}^{m+n} \suchthat m, n \in \naturals }$

6. $\Set{ \encoded{M} \suchthat M \text{ is a TM and } M \text{ is a recognizer for a language other than } \emptyset }$

7. $\Set{ \encoded{M} \suchthat M \text{ is a TM and } M \text{ is a recognizer for } \emptyset }$

8. $\Set{ \encoded{M} \suchthat M \text{ is a TM and } M \text{ is a recognizer for } L_D }$

9. $\Set{ \encoded{M, n} \suchthat M\text{ is a TM, } n \in \naturals, \text{ and } M \text{ accepts all strings in } \Set{\mathtt{a}, \mathtt{b}}^\star \text{ of length at most } n }$

10. $\Set{ \encoded{M, n} \suchthat M\text{ is a TM, } n \in \naturals, \text{ and } M \text{ rejects all strings in } \Set{\mathtt{a}, \mathtt{b}}^\star \text{ of length at most } n }$

11. $\Set{ \encoded{M, n} \suchthat M\text{ is a TM, } n \in \naturals, \text{ and } M \text{ loops on all strings in } \Set{\mathtt{a}, \mathtt{b}}^\star \text{ of length at most } n }$

12. { $\encoded{M_1, M_2, M_3, w} \suchthat 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$. }

Optional Fun Problem: Quine Relays

Write four different C++ programs with the following properties:

• Running the first program prints the complete source code of the second program.
• Running the second program prints the complete source code of the third program.
• Running the third program prints the complete source code of the fourth program.
• Running the fourth program prints the complete source code of the first program.
• None of the programs perform any kind of file reading.

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 a set of starter files for this Optional Fun Problem. There’s a separate autograder for this problem that you can submit to on Gradescope.

Grand Challenge Problem: $\mathbf{P} \stackrel{?}{=} \mathbf{NP}$

(Worth an A+, $1,000,000, and a Ph.D)

Prove or disprove: $\mathbf{P} = \mathbf{NP}$.

Congratulations on finishing the last problem set of the quarter!

We’re extremely impressed with how much progress you’ve made since the start of the quarter.

Best of luck on the final exam!