Request for "Tests" for the MIRI Research Guide

29Qiaochu_Yuan

9habryka

7Ben Pace

10[anonymous]

1Hazard

9Ben Pace

6Hazard

4crybx

3Jayson_Virissimo

2TurnTrout

0Gordon Seidoh Worley

4Qiaochu_Yuan

1Gordon Seidoh Worley

2gjm

New Comment

Thoughts off the top of my head. It's very unclear to me what "huge swath" means or ought to mean. I'm going to describe some problems I think it would be good if you knew how to solve but not going to make strong claims about whether they're necessary or sufficient to do MIRI research, which I think is the more relevant question than whether they certify a complete understanding of the topic. Some of them are exercises more than tests. I have more opinions about more standard stuff and fewer opinions about MIRI-specific stuff, much of which I'll skip.

Also I don't want to spend a ton of time on this so this is by no means exhaustive.

Also it's confusing to mix in topics like "set theory" with topics like "logical uncertainty" because lots of people understand set theory but there's an important sense in which nobody understands logical uncertainty.

**Set theory**

1. Prove Cantor's theorem.

2. Explain the way in which the structure of the proof of Cantor's theorem is identical to, roughly in increasing order of difficulty: Russell's paradox, the proof of the undecidability of the halting problem, the large-scale structure of the proof of the incompleteness theorem. (See this blog post for a sequence of increasingly large hints.)

**Probability, probabilistic inference, and statistics**

1. Suppose you repeatedly flip a coin with unknown bias, that your prior over the bias is uniform, and that you update your beliefs about the bias via Bayes' theorem. Prove that as the number of flips goes to infinity your beliefs about the bias converge to the true bias. Along the way, reinvent the concept of KL divergence for Bernoulli distributions.

2. Generalize the preceding result to an n-sided die. Along the way, reinvent the concept of KL divergence for distributions over finite sets. (Again, see this blog post for a sequence of increasingly large hints.)

**Machine learning**

1. Prove the universal approximation theorem.

2. Explain why the universal approximation theorem is not a sufficient explanation for the power of neural networks in practice.

**Solomonoff induction**

1. Prove that Kolmogorov complexity is uncomputable.

2. Does this imply that Solomonoff induction is uncomputable?

**VNM decision theory**

1. Reconcile the VNM theorem and the St. Petersburg paradox.

**First-order logic**

1. Prove that there are countable models of ZFC set theory and uncountable models of (first-order) Peano arithmetic, assuming their consistency.

2. Prove that there exist "self-hating" models of ZFC in which the statement "ZFC is consistent" is false (and also explain what it even means that this is the case), again assuming that ZFC is in fact consistent.

**Linear algebra**

1. Compute the derivative of the function sending an invertible square matrix to its inverse. Also explain what sort of mathematical object this derivative is.

**Topology**

1. Suppose is a connected topological space, is a topological space, and is a function. Prove that if is continuous, then the graph of is connected. Is the converse true? (I picked this one sort of randomly so don't take it too seriously, it's tricky to do this for topology.)

2. (Also first-order logic) Explain what the compactness theorem has to do with topological compactness.

**Category theory**

1. (Also set theory) Prove Lawvere's fixed point theorem, and use it to prove Cantor's theorem.

2. (Also type theory, kinda) Explain the way in which the proof of Lawvere's fixed point theorem is identical to the construction of the Y combinator.

3. (Also linear algebra) Explain why a finite-dimensional vector space is not naturally isomorphic to its dual , but is naturally isomorphic to its double dual .

(Edit: nuts, what happened to LaTeX support?)

Yeah, I'd be excited to see these too - I've been thinking for a while about how to create tests for the core concepts.

Even baring a full blown test, hints like (I'm going to make stuff up) "If you can prove how Solomonoff Induction across a transfinite ordinal ensures Turing-completeness, you're on the right track"

This might read like confident advice, but it's mostly just the strategy I've been using because it seems sensible to me.

For any of these topics with dedicated books (especially ones recommended as high quality), there will be proofs presented along the way while reading them. Don't just read the proofs. Try pausing before you read/understand the proof and try to work out how you would prove it yourself. Then read (and maybe re-read) until you think you get it, and try to prove it again without looking back at the material.

Keeping a list of these exercises might be handy to test yourself with later.

Also keep notes as you go about anything you find remotely confusing. Follow up on the confusion.

This doesn't tell you that you've "mastered the topic," but mastery comes in building blocks of deliberate practice.

From my work so far, I get the sense that you’ll be able to tell if you’re learning the material diligently. I also think that if you follow the list, you’ll be proficient enough to know when you need to look stuff up. Honestly, I’d just jump in with the easier material and ramp up. Even the basic set theory I learned has already paid substantial dividends, from notation legibility, to being able to quickly translate certain questions into set theory, prove them in ZF, and then translate back.

Aside: if you want a study partner, feel free to message me to work together and/or join Diffractor’s Discord. It’s basically a MIRI study group.

Being able to write and explain the complete proof of the Banach-Tarski theorem is a good proxy for understanding the basics of topology: it appears in the middle of most intro topology books for this reason.

What? A large part of the proof, as I understand it, is basically group-theoretic. Most of the central concepts of topology don't seem to appear. Are you thinking of a different theorem?

Hmm, wikipedia gives a very different proof than the one I learned for Banach-Tarkski, but it's also possible I've misremembered and I was thinking of Tychonoff's theorem.

I'd be astonished if there were a proof of Banach-Tarski that uses (1) most of the key notions in basic topology and (2) not much else. And I've certainly never seen a proof of BT in the middle of an introductory (or any other) topology book.

Lately I've been looking into learning the material in the MIRI research guide. After some time, I noticed that my biggest trepidation about diving in was the nagging question of, "But how will I know if I actually learned the stuff?"

Once I realized that was the thing holding me back, it became easier to think about solutions. Some of the topics correspond with courses that are common in universities, so I can pilfer final exams from their sites (woot to MIT open courseware). But for other topics I wanted to see what people here thought.

In whatever domain you specialize in, what are some examples of problems or questions that one can only answer by having a solid understanding of a huge swath of said domain? Below I've listed everything from the MIRI research guide that I could perceive as a distinct category.

(ex. If you were learning about Digital Systems and Computer Architecture, my test would be "In systemVerilog, simulate a basic 16-bit processor that can be programmed using a RISC assembly language of your design.")

(edit: I know that "huge swaths" is pretty vague, and suggestions don't have to be things that you think certify/prove that you get a topic. While a "comprehensive test" would be nice, problems/prompts like what Qiaochu commented are exactly what I'm looking for)