flâneur

Shtetl-Optimized » Blog Archive » The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me

scottaaronson.blog · 37,937 words · saved by 1 readers

I’ve supervised a lot of great student projects in my nine years at MIT, but my inner nerdy teenager has never been as personally delighted by a project as it is right now. Today, I’m proud to announce that Adam Yedidia, a PhD student at MIT (but an MEng student when he did most of this work), has explicitly constructed a one-tape, two-symbol Turing machine with 7,918 states, whose behavior (when run on a blank tape) can never be proven from the usual axioms of set theory, under reasonable consistency hypotheses. Adam has also constructed a 4,888-state Turing machine that halts iff there’s a counterexample to Goldbach’s Conjecture, and a 5,372-state machine that halts iff there’s a counterexample to the Riemann Hypothesis. In all three cases, this is the first time we’ve had a reasonable explicit upper bound on how many states you need in a Turing machine before you can see the behavior in question. Here’s our research paper, on which Adam generously included me as a coauthor, even

Shtetl-Optimized >> Blog Archive >> The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me Shtetl-Optimized The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel. Also, please read Zvi Mowshowitz's masterpiece on how to fix K-12 education! --> << &#8220;Largely just men doing sums&#8221;: My review of the excellent Ramanujan film Three announcements >> The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me I&#8217;ve supervised

related reading