Uploaded September 2025 | Updated September 2026, 2 weeks ago
Scott Aaronson, University of Texas, Austin
Theoretical computer science has over the years sought more and more refined answers to the question of which mathematical truths are knowable by finite beings like ourselves, bounded in time and space and subject to physical laws. I'll tell a story that starts with Godel's Incompleteness Theorem and Turing's discovery of uncomputability. I'll then introduce the spectacular Busy Beaver function, which grows faster than any computable function. Work by me and Yedidia, along with recent improvements by O'Rear, Riebel, and others, has shown that the value of BB(549) is independent of the axioms of set theory; on the other end, an international collaboration proved last year that BB(5) = 47,176,870. I'll speculate on whether BB(6) will ever be known, by us or our AI successors. I'll next discuss the P!=NP conjecture and what it does and doesn't mean for the limits of machine intelligence. As my own specialty is quantum computing, I'll summarize what we know about how scalable quantum computers, assuming we get them, will expand the boundary of what's mathematically knowable. I'll end by talking about hypothetical models even beyond quantum computers, which might expand the boundary of knowability still further, if one is able (for example) to jump into a black hole, create a closed timelike curve, or project oneself onto the holographic boundary of the universe.
Learn more, follow us on social media and check out our podcasts:
https://linktr.ee/sfiscience
Scott Aaronson, University of Texas, Austin
Theoretical computer science has over the years sought more and more refined answers to the question of which mathematical truths are knowable by finite beings like ourselves, bounded in time and space and subject to physical laws. I'll tell a story that starts with Godel's Incompleteness Theorem and Turing's discovery of uncomputability. I'll then introduce the spectacular Busy Beaver function, which grows faster than any computable function. Work by me and Yedidia, along with recent improvements by O'Rear, Riebel, and others, has shown that the value of BB(549) is independent of the axioms of set theory; on the other end, an international collaboration proved last year that BB(5) = 47,176,870. I'll speculate on whether BB(6) will ever be known, by us or our AI successors. I'll next discuss the P!=NP conjecture and what it does and doesn't mean for the limits of machine intelligence. As my own specialty is quantum computing, I'll summarize what we know about how scalable quantum computers, assuming we get them, will expand the boundary of what's mathematically knowable. I'll end by talking about hypothetical models even beyond quantum computers, which might expand the boundary of knowability still further, if one is able (for example) to jump into a black hole, create a closed timelike curve, or project oneself onto the holographic boundary of the universe.
Learn more, follow us on social media and check out our podcasts:
https://linktr.ee/sfiscience
