Fixed Point Exercises

Some­times peo­ple ask me what math they should study in or­der to get into agent foun­da­tions. My first an­swer is that I have found the in­tro­duc­tory class in ev­ery sub­field to be helpful, but I have found the later classes to be much less helpful. My sec­ond an­swer is to learn enough math to un­der­stand all fixed point the­o­rems. Th­ese two an­swers are ac­tu­ally very similar. Fixed point the­o­rems span all across math­e­mat­ics, and are cen­tral to (my way of) think­ing about agent foun­da­tions.

This post is the start of a se­quence on fixed point the­o­rems. It will be fol­lowed by sev­eral posts of ex­er­cises that use and prove such the­o­rems. While these ex­er­cises aren’t di­rectly con­nected to AI safety, I think they’re quite use­ful for prepar­ing to think about agent foun­da­tions re­search. After­wards, I will dis­cuss the core ideas in the the­o­rems and where they’ve shown up in al­ign­ment re­search.

The math in­volved is not much deeper than a first course in the var­i­ous sub­jects (logic, set the­ory, topol­ogy, com­putabil­ity the­ory, etc). If you don’t know the terms, a bit of googling, wikipe­dia and math.stack­ex­change should eas­ily get you most of the way. Note that the posts can be tack­led in any or­der.

Here are some ways you can use these ex­er­cises:

  • You can host a lo­cal MIRIx group, and go through the ex­er­cises to­gether. This might be use­ful to give a lo­cal group an af­for­dance to work on math rather than only read­ing pa­pers.

  • You can work on them by your­self for a while, and post ques­tions when you get stuck. You can also post your solu­tions to help oth­ers, let oth­ers see an al­ter­nate way of do­ing a prob­lem, or help you re­al­ize that there is a prob­lem with your solu­tion.

  • You can skip to the dis­cus­sion (which has some spoilers), learn a bunch of the­o­rems from Wikipe­dia, and use this as a start­ing point for try­ing to un­der­stand some MIRI pa­pers.

  • You can use an­swer­ing these ques­tions as a goal­post for learn­ing a bunch of in­tro­duc­tory math from a large col­lec­tion of differ­ent sub­fields.

  • You can show off by point­ing out that some of the ques­tions are wrong, and then I will prob­a­bly fix them and thank you.

The first set of ex­er­cises is here.

Thanks to Sam Eisen­stat for helping de­velop these ex­er­cises, Ben Pace for helping edit the se­quence, and many AISFP par­ti­ci­pants for test­ing them and notic­ing er­rors.

Meta

Read the fol­low­ing.

Please use the (new) spoilers fea­ture—the sym­bol ‘>’ fol­lowed by ‘!’ fol­lowed by space—in your com­ments to hide all solu­tions, par­tial solu­tions, and other dis­cus­sions of the math. The com­ments will be mod­er­ated strictly to cover up spoilers!

I recom­mend putting all the ob­ject level points in spoilers and leav­ing meta­data out­side of the spoilers, like so:

Here’s my solu­tion /​ par­tial solu­tion /​ con­fu­sion for ques­tion #5:

And put your idea in here! (re­minder: LaTex is cmd-4 /​ ctrl-4)