SatireV

Breaking

and entering

The Function Mapping Your CS121 Performance to a Good Grade is Uncomputable

Boaz
If I had 100 Turing machines for every 0/4 reading quiz I've seen, well, I’d be able to compute as many functions as one Turing machine.

By: Boaz Barak (instructor), Brain Sapozhnikov (Head TF), Albert Chalom, Alexis Ross, Charles O’Mara, Larry Bacow, Barak Obama, Barack Obama, Alan Turing, David Malan, David MalNAND, Bonnie from Lev, Mark Zuckerberg (Extension TF), Ivanka Trump (Patel Fellow)

 

Hi all,

Many students have asked why the quizzes, problem sets, and midterm have been so NP-hard to NP-complete. Well I NAND'd the numbers and their prefix-free encodings, and it appears that the function mapping your CS121 performance to a good grade is actually uncomputable.

Despite the fact that this proof is clearly trivial, I would expect you to rigorously prove every letter of every sentence of every paragraph of this on your homework, starting only from the axioms of mathematical logic.

Proof Idea: The idea that you cannot achieve a good grade is simple. I would offer the proof in Python since I know you'd pay extra special attention to it and not immediately scroll past. However, I think that I can accomplish more in the following SIZE(4n) lines.

Proof by contradiction: Assume you earned above a B in CS121. This implies that you did the readings, watched lecture, and finished psets early. It also means that you did not crowdsource solutions at office hours, “collaborate” on reading quizzes, spam Piazza at 11:59pm with anonymous, all-caps questions that I can instantly de-anonymize (surprise!), or answer the online polls that are clearly made for the sole purpose of taking attendance (surprise, surprise!) from your bedroom. This contradicts our assumption that it is YOU whom we're talking about, hence it cannot be true. ∎

Side Note (optional): Interestingly enough, we can still compute how much you've personally contributed to your pset partnership so far, because by Rice’s Theorem the constant 0 function must be computable.

I thought about further explaining the derivation of the above proofs and their intuitive underpinnings. Instead, however, I think I’ll just insert a colorful box yelling at you to reread them four more times until they make sense. Here's also a meaningless cluster of NANDs that should clarify everything:

 NAND(NAND(NAND(NAND(NAND(NAND(NAND(X[0],NAND(X[0],NAND(X[1],X[0]))),NAND(NAND(X[1],X[0]),NAND(X[0],NAND(X[1],X[0])))),NAND(NAND(X[0],NAND(X[0],NAND(X[1],X[0]))),NAND(NAND(X[1],X[0]),NAND(X[0],NAND(X[1],X[0]))))), NAND(NAND(X[0],NAND(X[1],X[0])),NAND(X[2],X[2]))),NAND(NAND(NAND(NAND(X[0],NAND(X[0],NAND(X[1],X[0]))),NAND(NAND(X[1],X[0]),NAND(X[0],NAND(X[1],X[0])))),NAND(NAND(X[0],NAND(X[0],NAND(X[1],X[0]))),NAND(NAND(X[1],X[0]),NAND(X[0],NAND(X[1],X[0]))))), NAND(NAND(X[0],NAND(X[1],X[0])),NAND(X[2],X[2])))), NAND(NAND(X[0], X[4]), NAND(X[1], X[0]))),NAND(NAND(NAND(NAND(NAND(NAND(X[0],NAND(X[0],NAND(X[1],X[0]))),NAND(NAND(X[1],X[0]),NAND(X[0],NAND(X[1],X[0])))),NAND(NAND(X[0],NAND(X[0],NAND(X[1],X[0]))),NAND(NAND(X[1],X[0]),NAND(X[0],NAND(X[1],X[0]))))), NAND(NAND(X[0],NAND(X[1],X[0])),NAND(X[2],X[2]))),NAND(NAND(NAND(NAND(X[0],NAND(X[0],NAND(X[1],X[0]))),NAND(NAND(X[1],X[0]),NAND(X[0],NAND(X[1],X[0])))),NAND(NAND(X[0],NAND(X[0],NAND(X[1],X[0]))),NAND(NAND(X[1],X[0]),NAND(X[0],NAND(X[1],X[0]))))), NAND(NAND(X[0],NAND(X[1],X[0])),NAND(X[2],X[2])))), NAND(NAND(X[0], X[4]), NAND(X[1], X[0]))))

Just like everything in CS121, we can also prove this with a reduction from the halting problem. Specifically, we will reduce your GPA to a binary number.

That being said, I do realize this class can be frustrating. But that's why I always provide hints in the most cryptic ways possible on psets. Here’s one for this week: To prove that the set U is uncountably infinite, come up with a one-to-one map between its elements and the set D, where D is the infinite set of typos in the textbook.

To make this rigorous I would advise a proof by induction or contradiction. When you inevitably fail at those, I would consider the increasingly popular proof technique of desperately begging for answers during this week's office hours that I am probably going to cancel, then referencing an absurd number of textbook theorems you don't understand to create the illusion of rigor in your write-up. Just remember that XOR(understanding the material, finishing on time) = 1.

I wouldn't take this too personally. In fact, by Godel's Incompleteness Theorem, there exists no proof that this class is passable.

*Note: A reading quiz on this material which was due yesterday morning will be released tomorrow.

Boaz

© 2018
Category: