Problem Set 9

Due Friday, June 9 at 2:30 pm Pacific

Grading

To allow you to focus on final exam studying, the written part of this problem will be graded for "participation" only, not correctness. In other words, write a good attempt, and you'll get full credit. The autograded/coding part is still for points (as shown on Gradescope, as usual).

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:

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

    /* Execute a line based on whether our syntax is right. */
    if (isValid(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: Password Checking

When you log onto a website with a password, some code on the server side needs to check that your password is correct. For the purposes of this problem, we’ll model password-checking in the following way. Let’s suppose your password is the string iheartquokkas. A password-checker would be a function that takes in a string, then returns true if and only if that string is iheartquokkas. So, for example, the following function is a password checker:

bool checkPassword(string password) {
    return password == "iheartquokkas";
}

as is this one:

bool checkPassword(string pass) {
    return pass.length() == 13 &&
           pass[0]  == 'i' && pass[1]  == 'h' && pass[2]  == 'e' &&
           pass[3]  == 'a' && pass[4]  == 'r' && pass[5]  == 't' &&
           pass[6]  == 'q' && pass[7]  == 'u' && pass[8]  == 'o' &&
           pass[9]  == 'k' && pass[10] == 'k' && pass[11] == 'a' &&
           pass[12] == 's';
}

And, surprisingly, the program shown below is a password-checker as well. (You aren't expected to understand how it works, just to marvel that it does. That said, those of you in CS107 might enjoy teasing this one apart!)

bool checkPassword(string password) {
    if (password.length() != 13) return false;
    
    uint64_t values[2] = {0, 0};
    for (int i = 0; i < 13; i++) {
        values[i / 8] += (uint8_t(password[i]) << (8 * (i % 8)));
    }
    
    return values[0] == 0x7571747261656869 &&
           values[1] == 0x73616b6b6f;
}

Now, suppose you’re doing a security audit of a website’s code. You’re tasked with confirming that, indeed, the password-checking logic on the server is correct. That is, you’re supposed to review the code that checks passwords to make sure that the server accepts the password iheartquokkas and rejects everything else. As you can see from the above examples, there are many ways to implement a password-checker – some of which are surprisingly complicated!

1. Below is a list of six functions. For each function, tell us whether

   1. the function doesn't accept iheartquokkas;
   2. the function accepts a string other than iheartquokkas;
   3. both (1) and (2) are true; or
   4. neither (1) nor (2) is true and the function is a password checker.

   
   No justification is necessary. Be wary - some of these functions are deceptive!

   As a note for that first one: the syntax password.find("text") != string::npos is the C++ way of saying "the string password contains the substring "text".

   bool hydrogen(string password) {
       return password.find("i") != string::npos &&
              password.find("heart") != string::npos &&
              password.find("quokkas") != string::npos;
   }
   
   bool helium(string password) {
       return true;
   }
   
   bool lithium(string password) {
       if (password.length() > 13) return false;
   
       string expected = "iheartquokkas";
       for (int i = 0; i < password.length(); i++) {
           if (password[i] != expected[i]) return false;
       }
       return true;
   }
   
   bool beryllium(string password) {
       return password == "lheartquokkas";
   }
   
   bool boron(string password) {
       if (password == "iheartquokkas");
           return true;
       return false;
   }
   
   bool carbon(string password) {
       if (password == "iheartquokkas") {                                       return true; } else if (password == "secret") {
          return true;
       } else {
          return false;
       }
   }
   

   The purpose of this exercise to show you that code is complicated and seemingly correct code can be deceptive. Whether it's deceptive because a human programmer made a silly error or because someone is intentionally trying to hide something sneaky in the code depends on context. Take CS155 for more details!

As you’ve seen from this exercise, it can be tricky to check by hand whether a password-checker is correct. Wouldn’t it be nice if we could automate this process? That is, is it possible to write a function

bool isPasswordChecker(string function);

that takes as input the source code of a function function, then returns true if function is a password-checker and returns false if function isn’t a password-checker? Such a function would have the following behavior:

• If function is the source of a function that accepts just the string iheartquokkas, then calling isPasswordChecker(function) will return true.
• If function is not the source of a function that accepts just the string iheartquokkas, then calling isPasswordChecker(function) will return false.

Unfortunately, it’s not possible to implement this isPasswordChecker function. To prove this, we’ll use self-reference. We’ll write a trickster function that tricks isPasswordChecker into giving the wrong answer.

Here’s an initial attempt at such a trickster function.

bool trickster(string w) {                    
    string me = /* source code of trickster */;
    return !isPasswordChecker(me);             
}

This code is, essentially, a (minimally) modified version of the self-referential program we used to get a contradiction for the language $A_{TM}$.

2. Prove by contradiction that the function trickster is not a password checker.

   As above, a password checker is a function that accepts iheartquokkas and doesn't accept any other string. Your intuition might tell you something about why trickster is or isn't a password checker, but your answer needs to formally address the definition.

3. Suppose trickster is not a password checker. Briefly explain why no contradiction arises in this case – no formal justification is necessary.

   A good question to think about: this program is very close to the one from the proof that $A_{TM}$ is not decidable. Why do you get a contradiction in the original proof that $A_{TM}$ is undecidable? Why doesn’t that same contradiction work here?

Ultimately, the goal of building a self-referential function 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 (iii), this particular trickster does not cause a contradiction if it isn't a password checker. Consequently, if we want to prove that it’s impossible to implement isPasswordChecker, we need to modify trickster so that it leads to a contradiction in the case where it is not a password checker.

4. Modify trickster so that it causes a contradiction regardless of whether it's a password checker. Then, briefly explain why your modified function is correct. No formal proof is necessary.

Problem Three: 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 Four: 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$. }

Problem Five: $\corelangs$ and Beyond

When we first saw that $A_{TM}$ is undecidable, we could at least take consolation in the fact that $A_{TM}$ 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 $\relangs$ language. (Do you see why?) In other words, while there’s no general way to prove that some TM will not accept its own encoding, there is a general way to prove that some TM will accept its own encoding.

The fact that $L_D$ isn’t an $\relangs$ language while $\overline{L_D}$ is still in $\relangs$ suggests that there might be a bit more to the computability landscape than just $\rlangs$ and $\relangs\text.$ And indeed there is: the same way that $A_{TM}$ is the poster child of an $\relangs$ language, the language $L_D$ is the poster child of a $\corelangs$ language. Formally speaking, the class $\corelangs$ consists of all the languages whose complement is an $\relangs$ language:

Intuitively speaking, the $\corelangs$ languages are languages where if you have a string that isn’t in the language, there’s some easy way to prove that it isn’t in the language.

1. Prove that $A_{TM} \notin \corelangs\text.$

   You haven't seen the term $\corelangs$ prior to this problem, but you have seen something somewhere before that would be helpful in solving this problem.

At this point, we have an $\relangs$ language that’s not in $\corelangs\, (A_{TM})$ and a $\corelangs$ language that’s not in $\relangs\, (L_D)\text.$ As a coda to our treatment of unsolvable problems, let’s see a language that’s neither in $\relangs$ nor $\corelangs\text.$ 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 = \Set{\mathtt{0}, \mathtt{1}}\text.$ Given two languages $A$ and $B$ over $\Sigma\text,$ the disjoint union of $A$ and $B\text,$ denoted $A \uplus B\text,$ is the language

For example, if $A = \Set{ {\color{blue} \mathtt{1}, \mathtt{10}, \mathtt{100}, \mathtt{1000} }}$ and $B = \Set{ {\color{red}\varepsilon, \mathtt{0}, \mathtt{1}, \mathtt{00}, \mathtt{01}, \mathtt{10}, \mathtt{11}} }\text,$ then $A \uplus B$ is the language

Notice how each string in $A \uplus B$ is tagged with which language it originated in. Any string that starts with $\mathtt{0}$ came from $A\text,$ and any string that starts with $\mathtt{1}$ came from $B\text.$

2. Let $A$ and $B$ be languages where $A \uplus B \in \relangs\text.$ This means that there is a recognizer for $A \uplus B\text,$ which we can represent in software as a function

   bool isInA_uplus_B(string w);

   that takes as input a string, then returns true if and only if that string is in $A \uplus B\text.$

   Show that $A \in \relangs$ by writing code for a function

   bool isInA(string w);

   that takes as input a string, then returns true if and only if that string is in $A\text.$ No justification is necessary.

   The amount of code you need to write here is very small, so if you're finding that you're writing a lot of code here, pause, back up, and see if you can find something simpler.

3. Let $A$ and $B$ be languages where $A \uplus B \in \corelangs\text.$ This means that there is a recognizer for $\overline{A \uplus B}\text,$ which we can represent in software as a function

   bool isInComplement_A_uplus_B(string w);

   that takes as input a string, then returns true if and only if that string is in $\overline{A \uplus B}\text.$

   Show that $B \in \corelangs$ by writing code for a function

   bool isInComplement_B(string w);

   that takes as input a string, then returns true if and only if that string is in $\overline{B}\text.$ No justification is necessary.

   As above, you don't need to write a lot of code here.

4. Using your results from parts (ii) and (iii) of this problem, prove that $L_D \uplus A_{TM} \notin \relangs$ and that $L_D \uplus A_{TM} \notin \corelangs\text.$

Your result from part (iv) shows that, in a very real sense, the language $L_D \uplus A_{TM}$ is a "harder" problem than both $L_D$ and $A_{TM}\text;$ it's neither in $\relangs$ nor in $\corelangs\text!$ 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 \uplus A_{TM}$ is what’s called a $\Delta^0_2$ language, where $\Delta^0_2$ is a class of languages that contains all of $\relangs$ and $\corelangs\text,$ plus a bunch of other problems. And $\Delta^0_2$ itself sits inside even larger classes of languages, stretching outward to infinity.

In a sense, the same way that Cantor's theorem gives a way of finding infinite sets of progressively larger sizes, it's possible to find undecidable problems of progressively "harder" difficulty. Want to learn more? Take Phil 152!

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!