Due Wednesday, August 16 at 4:00 pm Pacific
Solutions are available!
In this problem set – the last one of the quarter! – you’ll travel to the realm of Turing machines to explore the limits of what computers can ever hope to accomplish, and we hope that you find this as exciting as we do!
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!
Grading
To allow you to focus on final exam studying, Problem Set 7 will have the following grading scheme:
Written Questions (Problems 1 through 3)
- The written component of this problem set is optional.
- You may complete and submit any parts of the written questions, and we will only include them in your final grade if they help your overall assignment score.
- Content that is covered only in these written questions will not be tested on the final exam.
Coding Question (Problem 4)
- The coding component is still graded for points, as usual.
- Content that is covered in this question is fair game for the final exam.
Starter Files
Here are the starter files for the problems you'll submit electronically:
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:
Problem One: The Fixed-Point Theorem
Let $\Sigma$ be an alphabet. We can then think of a function $f : \powerset{\Sigma^\star} \to \powerset{\Sigma^\star}$ as a function that takes a language over $\Sigma$ as input and produces a language over $\Sigma$ as output.
Now, a new definition. A function $f : \powerset{\Sigma^\star} \to \powerset{\Sigma^\star}$ is called monotone if the following is true:
\[\forall A \in \powerset{\Sigma^\star}. \forall B \in \powerset{\Sigma^\star}. (A \subseteq B \to f(A) \subseteq f(B))\text.\]This definition is a bit more subtle than it might initially appear.
-
Let $\Sigma = \Set{\mathtt{a}, \mathtt{b}}$. Below is a list of four functions from $\powerset{\Sigma^\star}$ to itself. For each function, determine whether it's monotone. No justification is required.
- $f : \powerset{\Sigma^\star} \to \powerset{\Sigma^\star}$ defined as $f(L) = L \cup \Set{\mathtt{aaa}}\text.$
- $f : \powerset{\Sigma^\star} \to \powerset{\Sigma^\star}$ defined as $f(L) = L \cap \Set{\mathtt{aaa}}\text.$
- $f : \powerset{\Sigma^\star} \to \powerset{\Sigma^\star}$ defined as $f(L) = L - \mathtt{a}L\text.$
- $f : \powerset{\Sigma^\star} \to \powerset{\Sigma^\star}$ defined as $f(L) = L^\star\text.$
A fixed point of a function $f : \powerset{\Sigma^\star} \to \powerset{\Sigma^\star}$ is a language $L$ where $f(L) = L$.
-
For each of the functions from part (i) of this problem, determine whether that function has any fixed points and list one if one exists. No justification is necessary.
The rest of this problem considers a remarkable theorem about monotone functions:
Theorem: Let $\Sigma$ be an alphabet and let $f : \powerset{\Sigma^\star} \to \powerset{\Sigma^\star}$ be a monotone function. Then $f$ has a fixed point.
We're going to ask you to prove this theorem by showing that the following language $X$ is a fixed point of $f$:
\[X = \Set{ w \in \Sigma^\star \suchthat \exists L \in \powerset{\Sigma^\star}. (w \in L \land L \subseteq f(L))}\text.\]Yes, this definition is a mouthful. But it turns out that, indeed, if $f$ is monotone, then $X = f(X)\text.$
-
Let $L$ be a language where $L \subseteq f(L)$. Prove that $L \subseteq X\text.$
-
Prove that $X = f(X)\text.$
The overall proof of this result is not very long, but it's also not "obvious." This will be a great place to write out a list of all of the assumptions you're making and all the facts you know about $f$ and $X\text.$ Setting this problem up correctly will make it much easier to discover the solution. Make sure to include your result from part (iii) in that list of facts you know about $f$ and $X$ as it will make a couple of appearances in the proof.
Once you've finished this problem, pat yourself on the back - you've made amazing progress since the start of the quarter!
Fixed points are an amazingly powerful tool in Theoryland. They're used in optimizing compilers to infer information about what a program does, to show certain problems are undecidable, to formally define recursive functions in programming, to prove the existence of equilibria in economics, and to devise fair division protocols in algorithmic game theory. One fun application of fixed points is Sperner's lemma, which can be used to divide rent fairly among three people sharing an apartment with unequal rooms. Take CS143, CS154, CS242, and CS243 to learn more!
Problem Two: What Does it Mean to Solve a Problem?
Let $L$ be a language over $\Sigma$ and $M$ be a TM with input alphabet $\Sigma$. Here are three potential traits of $M$:
- $\forall w \in \Sigma^\star. M \haltson w.$
- $\forall w \in \Sigma^\star. (M \accepts w \to w \in L).$
- $\forall w \in \Sigma^\star. (M \rejects w \to w \notin L).$
At some level, for a TM to claim to solve a problem, it should have at least some of these properties. Interestingly, though, just having two of these properties doesn't say much.
-
Let $L$ be an arbitrary language. Write a TM that satisfies properties (1) and (2). No justification is necessary.
When we say “write a TM”, we would like you to provide a program made up of TM instructions along the lines of what we did in class.
You might be wondering “how on earth is it possible to write a TM with those properties if we have no idea what $L$ is?” That is a reasonable question to ask, and gets at the heart of what this question is about. The whole point of this problem is to show that you have to be extremely careful about how you define “solving a problem,” since if you define it incorrectly then you can “solve” a problem in a way that bears little resemblance to what we’d think of as solving a problem. Keep this in mind as you work through this one.
-
Let $L$ be an arbitrary language. Write a TM that satisfies properties (1) and (3). No justification is necessary.
-
Let $L$ be an arbitrary language. Write a TM that satisfies properties (2) and (3). No justification is necessary.
-
Suppose $L$ is a language over $\Sigma$ for which there is a TM $M$ that satisfies all of properties (1), (2), and (3). What can you say about $L$? Prove it.
In the earlier parts of this problem you showed that just having two of these three properties doesn't tell you much about $L$. As you're writing your proof for this problem, make sure you see exactly where you're citing all three of the relevant properties. If you don't use all three properties, chances are that your proof is incorrect.
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:
(Incorrect!) Theorem: All languages are undecidable.
(Incorrect!) Proof: By contradiction; assume there is a decidable language $L$. Then there is a decider $D$ for $L$. We can represent $D$ as a function
bool inL(string w);
that takes in a string $w$, then returns true if $w \in L$ and false otherwise.
Now, consider the following program:
bool trickster(string w) {
return !inL(w);
}
Since inL decides $L$, we know that
Given how trickster is written, we see that
This means that
\[\mathtt{trickster(w)}\text{ returns false} \qquad \text{if and only if} \qquad w \in L\text.\]This is impossible. We've reached a contradiction, so our assumption was wrong and $L$ is undecidable. $\qed$
This proof has to be wrong because we know of many decidable languages.
-
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:
(Incorrect!) Theorem: All languages are undecidable.
(Incorrect!) Proof: By contradiction; assume there is a decidable language $L$. Then there is a decider $D$ for $L$. We can represent $D$ as a function
bool willAccept(string function, string w);
that takes in the source code of a function function and a string $w$, then returns true if function(w) returns true and false otherwise.
Now, consider the following program:
bool trickster(string w) {
string me = /* source code for trickster */;
/* See whether we'll accept, then do the opposite. */
return !willAccept(me, w);
}
Since willAccept decides $L$ and me holds the source code of trickster, we know that
Given how trickster is written, we see that
This means that
\[\mathtt{trickster(input)}\text{ returns true}\qquad \text{if and only if} \qquad \texttt{trickster(input)} \text{ returns false.}\]This is impossible. We've reached a contradiction, so our assumption was wrong and $L$ is undecidable. $\qed$
It’s a nice read, but this proof isn’t correct.
-
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$:
\[L = \Set{ \encoded{P} \suchthat P \text{ is a syntactically valid C++ program} }\]Below is a purported proof that $L$ is undecidable:
(Incorrect!) Theorem: The language $L$ is undecidable.
(Incorrect!) Proof: By contradiction; assume $L$ is decidable. Then there is a decider $D$ for $L$. We can represent $D$ as a function
bool isValid(string function);
that takes in the source code of a function function, then returns true if function is syntactically valid and false otherwise.
Now, consider the following program:
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!
}
}
Since isValid decides $L$ and me holds the source of trickster, we know that
Given how trickster is written, we see that
This means that
\[\mathtt{trickster} \text{ is syntactically valid} \qquad \text{if and only if} \qquad \mathtt{trickster} \text{ is syntactically invalid.}\]This is impossible. We've reached a contradiction, so our assumption was wrong and $L$ is undecidable. $\qed$
This proof, unfortunately, is incorrect.
-
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: The Lava Diagram
(We recommend reading the Guide to the Lava Diagram before starting this problem.)
Download the starter files for Problem Set 7 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.
-
$\Sigma^\star$
-
$L_D$
-
$\Set{ \mathtt{a}^n \suchthat n \in \naturals }$
-
$\Set{ \mathtt{a}^n \suchthat n \in \naturals \text{ and } n \text{ is a multiple of } 137 }$
-
$\Set{ \mathtt{1}^m\mathtt{+1}^n\mathtt{=1}^{m+n} \suchthat m, n \in \naturals }$
-
$\Set{ \encoded{M} \suchthat M \text{ is a TM and } M \text{ is a recognizer for a language other than } \emptyset }$
-
$\Set{ \encoded{M} \suchthat M \text{ is a TM and } M \text{ is a recognizer for } \emptyset }$
-
$\Set{ \encoded{M} \suchthat M \text{ is a TM and } M \text{ is a recognizer for } L_D }$
-
$\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 }$
-
$\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 }$
-
$\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 }$
-
{ $\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: TMs and Regular Languages
Let $M$ be a recognizer for a language $L$ over $\Sigma$. Suppose $M$ has the following property: there exists a natural number $k$ such that when $M$ is run on any string $w$, $M$ always halts after at most $k$ steps.
Prove that $L$ is regular.