Problem Set 9

Due Friday, December 8 at 1:00 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: Verifier Warmups

Verifiers can feel a bit weird the first time you encounter them. The definition is abstract, and it never feels like they're actually solving a problem. These questions are designed to get you playing around a bit more with verifiers so you can build a better intuitive feel for them.

1. Consider the language $L = \Set{ \langle n \rangle \suchthat n \in \naturals \land n \text{ is a perfect square}}\text.$ Below is a list of programs that purport to be verifiers for $L\text.$ Which are, and which aren't? Briefly justify your answers, but no formal proof is necessary.

   • bool checkSquare1(int n) {
         for (int i = 0; i <= n; i++) {
             if (i * i == n) return true;
         }
         return false;
     }
     

   • bool checkSquare2(int n) {
         int i = 0;
         while (true) {
             if (i * i == n) return true;
             i++;
         }
     }
     

   • bool checkSquare3(int n, string w) {
         return w == "n is a perfect square."
     }
     

   • bool checkSquare4(int n, int k) {
         return k * k == n;
     }
     

   • bool checkSquare5(int n, int k, int m) {
         return k * m == n;
     }
     

   • bool checkSquare6(int n, int k) {
         for (int i = 0; i < k; i++) {
             if (i * i == n) return true;
         }
         return false;
     }
     

   • bool checkSquare7(int n, int i) {
         while (true) {
             if (i * i == n) return true;
             i++;
         }
     }
     

2. Briefly explain why the following is a verifier for $A_{TM}\text.$ No formal proof is necessary.

   bool checkAccepts(TM M, string w, int n) {
       set up a simulation of M running on w;
       for (int i = 0; i < n; i++) {
           simulate one more step of M running on w;
       }
       return whether M executed the command "Return True";
   }
   

Problem Two: Computable Functions

A function $f : \Sigma^\star \to \Sigma^\star$ is called a computable function when it is possible to implement, in code, a function

  string compute_f(string w)

such that for all $w \in \Sigma^\star\text,$ calling compute_f(w) returns $f(w)\text.$ Intuitively, a computable function is one that you can implement in code.

Not all functions are computable. Here's a simple example of an uncomputable function:

If we could compute this function, we could solve the halting problem by just calling $f(\langle M, w \rangle)$ and seeing whehter the result is YES.

Below are a series of properties of computable functions and $\relangs$ languages. In each case, we've provided the outline of a program that proves those properties. Each program has one or more blanks in them. Fill in the blanks to complete the constructions. You should write at most one line of code in the body of each function. No justification is required.

1. The computable functions are closed under composition: if $g$ and $f$ are computable, so is $g \circ f\text.$ Fill in the blank below with a single line of code to show this.

   /* Function that computes f. This is given to you. */
   string compute_f(string w);
   
   /* Function that computes g. This is given to you. */
   string compute_g(string w);
   
   /* Function that computes g o f. You need to write this, and it must
    * be exactly one line of code long.
    */
   string compute_gof(string w) {
       _____________________;
   }
   

2. If $f$ is a computable function and $L \in \relangs\text,$ then $f^{-1}[L] \in \relangs\text.$ Fill in the blanks below with a single line of code to show this.

   /* Function that computes f. This is given to you. */
   string compute_f(string w);
   
   /* Verifier for the language L. This is given to you and has the
    * following properties:
    *
    *    checkInL(w, c) always halts.
    *    for all strings w, (w in L if and only if there's a c where
    *         checkInL(w, c) returns true
    *    )
    *
    * Beyond this, you should make no assumptions about checkInL.
    */
   bool checkInL(string w, string c);
   
   /* Verifier for the language f-1[L]. You need to write this, and it
    * must be exactly one line of code long. You can add any number of
    * additional parameters.
    */
   bool checkInFPreimageL(string w, _______________________________) {
       _____________________;
   }
   

3. If $f$ is a computable function and $L \in \relangs\text,$ then $f[L] \in \relangs\text.$ Fill in the blanks below with a single line of code to show this.

   /* Function that computes f. This is given to you. */
   string compute_f(string w);
   
   /* Verifier for the language L. This is given to you and has the
    * following properties:
    *
    *    checkInL(w, c) always halts.
    *    for all strings w, (w in L if and only if there's a c where
    *         checkInL(w, c) returns true
    *    )
    *
    * Beyond this, you should make no assumptions about checkInL.
    */
   bool checkInL(string w, string c);
   
   /* Verifier for the language f[L]. You need to write this, and it
    * must be exactly one line of code long. You can add any number of
    * additional parameters.
    */
   bool checkInFImageL(string w, _______________________________) {
       _____________________;
   }
   

Problem Three: 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 Four: 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 Five: 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 for $L$ and a verifier for $\overline{L}$. In software, you could imagine that these verifiers correspond to functions with these signatures:

/* Verifier for L. This function has these properties:
 *
 *    checkInL(w, c) always halts.
 *    for all strings w, (w in L if and only if there's a c
 *        where checkInL(w, c) returns true
 *    )
 */
bool checkInL(string w, string c);

/* Verifier for L^bar. This function has these properties:
 *
 *    checkInLBar(w, c) always halts.
 *    for all strings w, (w in L^bar if and only if there's a c
 *        where checkInLBar(w, c) returns true
 *    )
 */
bool checkInLBar(string w, string c); 

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 Six: 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: Undecidability Phase Transitions

Let $A_{TM}^{(n)}$ be the following language:

The language $A_{TM}^{(0)}$ is the empty language because there are no 0-line TMs. As a result, $A_{TM}^{(0)}$ is decidable. Similarly, $A_{TM}^{(1)}$ is decidable - the only legal 1-line TM is the TM Start:, which implicitly rejects every string. $A_{TM}^{(2)}$ is also decidable, but it's a bit more interesting because there are two-line TMs that accept their inputs. More generally, as we increase $n\text,$ we start dealing with more and more complex TMs, and the language becomes more and more complex.

Prove that there exists an $n \in \naturals$ where $A_{TM}^{(n)}$ is undecidable. This shows that there is a "phase transition" in these languages - they begin decidable, are decidable for some range of values of $n\text,$ but then abruptly switch to undecidable.

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!