Scott Aaronson: Computational Complexity and Consciousness | Lex Fridman Podcast #130

1. 0:00 – 3:31

   Introduction

   1. LFLex Fridman0:00

      The following is a conversation with Scott Aaronson, his second time on the podcast. He is a professor at UT Austin, director of the Quantum Information Center, and previously a professor at MIT. Last time, we talked about quantum computing. This time, we talk about computation complexity, consciousness, and theories of everything. I'm recording this intro, as you may be able to tell, in a very strange room in the middle of the night. I'm not really sure how I got here or how I'm going to get out, but Hunter S. Thompson saying, I think applies to today and the last few days, and actually the last couple of weeks. "Life should not be a journey to the grave with the intention of arriving safely in a pretty and well-preserved body, but rather to skid in broadside in a cloud of smoke, thoroughly used up, totally worn out, and loudly proclaiming, 'Wow, what a ride!'" So I figured whatever I'm up to here, and yes, lots of wine is involved, I'm gonna have to improvise, hence this recording. Okay, quick mention of each sponsor, followed by some thoughts related to the episode. First sponsor is SimpliSafe, a home security company I use to monitor and protect my apartment, though, of course, I'm always prepared with a fallback plan as a man in this world must always be. Second sponsor is Eight Sleep, a, uh, mattress that cools itself, measures heart rate variability, has an app, and has given me yet another reason to look forward to sleep, including the all-important power nap. Third sponsor is ExpressVPN, the VPN I've used for many years to protect my privacy on the internet. Finally, the fourth sponsor is BetterHelp, online therapy when you want to face your demons with a licensed professional, not just by doing David Goggins-like physical challenges like I seem to do on occasion. Please check out these sponsors in the description to get a discount and to support the podcast. As a side note, let me say that this is the second time I recorded a conversation outdoors. The first one was with Stephen Wolfram when it was actually sunny out. In this case, it was raining, which is why I found a covered outdoor patio, but I learned a valuable lesson, which is that raindrops can be quite loud on the hard metal surface of a patio cover. I did my best with the audio. I hope it still sounds okay to you. I'm learning, always improving. In fact, as Scott says, "If you always win, then you're probably doing something wrong." To be honest, I get pretty upset with myself when I fail, small or big, but I've learned that this feeling is priceless. It can be fuel when channeled into concrete plans of how to improve. So if you enjoy this thing, subscribe on, uh, YouTube, review it with five stars on Apple Podcast, follow on Spotify, support on Patreon, or connect with me on Twitter @lexfriedman. And now, here's my conversation with Scott Aaronson.

2. 3:31 – 8:22

   Simulation

   1. LFLex Fridman3:31

      Let's start with the most absurd question, but I've read you write some fascinating stuff about it, so, uh, let's go there. Are we living in a simulation?

   2. SAScott Aaronson3:39

      What difference does it make, Lex?

   3. LFLex Fridman3:41

      (laughs)

   4. SAScott Aaronson3:41

      I mean, I'm serious. What difference?

   5. LFLex Fridman3:43

      Because if we are living in a simulation, it raises the question, how real does something have to be in simulation for it n- it to be sufficiently immersive for us humans?

   6. SAScott Aaronson3:54

      Mm-hmm. But, I mean, even in principle, how could we ever know if we were in one, right? A perfect simulation by definition is something that's indistinguishable from the real thing.

   7. LFLex Fridman4:03

      But we didn't say anything about perfect. It could be imperfect.

   8. SAScott Aaronson4:05

      No, no. That's, that's right. Well, if, if it was an imperfect simulation, if we could hack it, you know, find a bug in it, then that would be one thing, right? If, if this was like The Matrix and there was a way for me to, you know, do flying kung fu moves or something by hacking the simulation, well then, you know, we would have to cross that bridge when we came to it, wouldn't we, right? (laughs)

   9. LFLex Fridman4:26

      (laughs)

   10. SAScott Aaronson4:26

       I mean, at that point, you know, i- i- it's, it's, uh, hard to see the difference between that and just, uh, uh, what people would ordinarily refer to as a world with miracles, you know? Uh...

   11. LFLex Fridman4:37

       What about from a different perspective, thinking about the universe as a computation, like a-

   12. SAScott Aaronson4:42

       Yeah.

   13. LFLex Fridman4:42

       ... program running on a computer.

   14. SAScott Aaronson4:43

       Uh-huh.

   15. LFLex Fridman4:44

       Is- That's kind of a neighboring concept. Do you, do-

   16. SAScott Aaronson4:46

       I- It is. It is an interesting and reasonably well-defined question to ask, "Is the world computable?"

   17. LFLex Fridman4:52

       Yeah.

   18. SAScott Aaronson4:52

       You know, you know, does the world satisfy what we would call in CS, the, uh, the Church-Turing thesis?

   19. LFLex Fridman4:58

       Yeah.

   20. SAScott Aaronson4:58

       That is, you know, uh, could we take any physical system and simulate it to, uh, you know, uh, any desired precision by a Turing machine, you know, given the appropriate input data, right? And so far, I think the indications are pretty strong that our world does seem to satisfy the Church-Turing thesis. Uh, uh, at least if it doesn't, then we haven't yet discovered why not. Uh, but, now does that mean that our universe is a simulation? Well, you know, that w- word seems to suggest that there is some other larger universe in which it is running, right?

   21. LFLex Fridman5:34

       Right.

   22. SAScott Aaronson5:34

       And the problem there is that if the simulation is perfect, then we're never going to be able to get any direct evidence about that other universe. You know, we will only be able to see, uh, the effects of the computation that is running in this universe.

   23. LFLex Fridman5:50

       Well, let's imagine an analogy.

   24. SAScott Aaronson5:52

       Mm-hmm.

   25. LFLex Fridman5:53

       Let's i- imagine a, a PC, a personal computer, a computer. Is it possible with the advent of artificial intelligence for the computer-... to look outside of itself to see, to understand its creator.

   26. SAScott Aaronson6:08

       Mm-hmm.

   27. LFLex Fridman6:08

       I mean, that's a sim-

   28. SAScott Aaronson6:09

       (chuckles)

   29. LFLex Fridman6:09

       Is that, is that a ridiculous connect analogy?

   30. SAScott Aaronson6:11

       Well, wi- well, w- well- well, I mean, with the computers that we actually have, I mean, first of all, uh, w- w- we all know that, uh, humans have done an imperfect job of, you know, in- enforcing the abstraction boundaries of computers, right?
3. 8:22 – 14:02

   Theories of everything

   1. SAScott Aaronson8:22

      be wrong.

   2. LFLex Fridman8:22

      But do you think, uh, on the physics side of things-

   3. SAScott Aaronson8:25

      Mm-hmm.

   4. LFLex Fridman8:25

      ... you know, there's been, uh, recently a few folks, Eric Weinstein and, uh, Stephen Wolfram that came out with a theory of everything. I think there's a history of physicists dreaming and working on the unification of all the laws of physics.

   5. SAScott Aaronson8:40

      Mm-hmm.

   6. LFLex Fridman8:40

      Do you think it's possible that once we understand, uh, more physics, not necessarily the unification of the laws-

   7. SAScott Aaronson8:47

      Mm-hmm.

   8. LFLex Fridman8:47

      ... but just understand physics more deeply at the fundamental level-

   9. SAScott Aaronson8:51

      Mm-hmm.

   10. LFLex Fridman8:51

       ... we'll be able to start, you know, uh... (laughs) I mean, part of this is humorous, but, uh, looking to see if there's any bugs in the universe that could be exploited for, uh, you know, traveling a- at, uh, at not just the speed of light, but just traveling faster than our current, uh, spaceships can travel, all that kind of stuff?

   11. SAScott Aaronson9:11

       Well, I mean, to, to travel faster than our current spaceships could travel, you wouldn't need to find any bug in the universe, right? The known laws of physics, you know, let us go much faster up to the speed of light, right? And, you know, when people wanna go faster than the speed of light, well, we actually know something about what that would entail. Namely that, you know, according to relativity, that seems to entail communication backwards in time, okay? So then you have to worry about, uh, closed timelike curves and all of that stuff. So, you know, in some sense, we, we sort of know the price that you have to pay for these things, right? Uh, you know, we can't-

   12. LFLex Fridman9:48

       But under, under the current understanding of physics, yeah.

   13. SAScott Aaronson9:49

       That's right, that's right. We can't, you know, say that they're impossible, but we, you know, we know that sort of a lot else in physics breaks.

   14. LFLex Fridman9:57

       Yeah.

   15. SAScott Aaronson9:57

       Right? So, uh, now regarding, uh, Eric Weinstein and, and Stephen Wolfram, like, I wouldn't say that either of them has a theory of everything. I would say that they have ideas that they hope, you know, could someday lead to a theory of everything.

   16. LFLex Fridman10:12

       Is that a worthy pursuit?

   17. SAScott Aaronson10:13

       Well, I mean, certainly. Let's say by theory of everything, you know, we don't literally mean a theory of cats and of baseball and... you know, but we just me- mean it in the... in the more limited sense of everything. A fun- a, a fundamental theory of physics, right? Of all of the fundamental interactions of physics. Of course, such a theory, even after we had it, uh, you know, would leave the entire question of all the emergent behavior, right?

   18. LFLex Fridman10:41

       Yes.

   19. SAScott Aaronson10:41

       You know, to, uh, uh, to be explored. Uh, so it's... so it's only everything for a specific definition of everything. Okay, but in that sense, I would say, of course that's worth pursuing. I mean, that is the entire program of fundamental physics, right? All of my friends who do quantum gravity, who do string theory, who do anything like that, that is what's motivating them.

   20. LFLex Fridman11:03

       Yeah, it's, it's funny, though, but... and Eric Weinstein talks about this.

   21. SAScott Aaronson11:06

       Mm-hmm.

   22. LFLex Fridman11:06

       It is... I don't know much about the physics world-

   23. SAScott Aaronson11:08

       Mm-hmm.

   24. LFLex Fridman11:08

       ... but I know about the AI world, and-

   25. SAScott Aaronson11:10

       Mm-hmm.

   26. LFLex Fridman11:10

       ... it is a little... it- it is a little bit taboo, uh, to talk about AGI, for example-

   27. SAScott Aaronson11:17

       Hm.

   28. LFLex Fridman11:17

       ... on the AI side.

   29. SAScott Aaronson11:18

       Mm-hmm.

   30. LFLex Fridman11:18

       So really, to talk about, uh, the d- the big dream of the community, I would say-
4. 14:02 – 36:16

   Consciousness

   1. SAScott Aaronson14:02

      nature."

   2. LFLex Fridman14:02

      Let me bring up the next topic that people-

   3. SAScott Aaronson14:04

      Mm.

   4. LFLex Fridman14:04

      ... don't wanna mention, although they're getting more comfortable with it, is consciousness.

   5. SAScott Aaronson14:07

      Mm.

   6. LFLex Fridman14:08

      You mentioned that you have a talk on consciousness that I watched five minutes of, but the internet connection-

   7. SAScott Aaronson14:13

      Was, was thi-

   8. LFLex Fridman14:13

      ... was really bad.

   9. SAScott Aaronson14:14

      ... was thi- was this my talk about, you know, uh, uh, uh, refuting the integrated information theory?

   10. LFLex Fridman14:18

       Yes, it might have been.

   11. SAScott Aaronson14:19

       Which was this particular account of consciousness-

   12. LFLex Fridman14:21

       Yeah.

   13. SAScott Aaronson14:21

       ... that, yeah, I think one can just show it doesn't work.

   14. LFLex Fridman14:23

       (laughs) But, so let me, uh-

   15. SAScott Aaronson14:24

       Much harder to say what does work. (laughs)

   16. LFLex Fridman14:25

       What does work, yeah.

   17. SAScott Aaronson14:26

       Yeah, yeah, yeah.

   18. LFLex Fridman14:27

       So let me ask, uh, maybe it'd be nice to, uh, comment on... You, you talk about also, like, the, the semi-hard g- problem of consciousness, or like-

   19. SAScott Aaronson14:35

       Yeah.

   20. LFLex Fridman14:35

       ... almost hard problem or kinda hard p-

   21. SAScott Aaronson14:36

       Yeah, pre- pretty hard problem-

   22. LFLex Fridman14:37

       Pretty hard.

   23. SAScott Aaronson14:38

       ... I think I call it.

   24. LFLex Fridman14:38

       Great. So maybe can you, uh, talk about that, uh, their idea of, um, of, uh, the approach to modeling consciousness and why you don't find it convincing?

   25. SAScott Aaronson14:48

       Yeah.

   26. LFLex Fridman14:48

       What is it, first of all? What, how, what-

   27. SAScott Aaronson14:50

       O- okay. Well, so, so what, what, what I call the pretty hard problem of consciousness, this is my term, although many other people have said something equivalent to this, okay? Uh, but, uh, it, it's just, you know, the, the, the p- problem of, you know, giving an account of just which physical systems are conscious and which are not. Or, you know, if there were degrees of consciousness, then quantifying how conscious a given system is. Right?

   28. LFLex Fridman15:17

       Oh, awesome. So that's the pretty hard problem.

   29. SAScott Aaronson15:19

       Yeah, tha- that's what I mean by it. That-

   30. LFLex Fridman15:20

       That's it, I'm adopting it. Tha- I love it. It has a good-
5. 36:16 – 46:28

   Roger Penrose on consciousness

   1. SAScott Aaronson36:16

      you?

   2. LFLex Fridman36:16

      What are your thoughts... I'd be curious. You're-

   3. SAScott Aaronson36:19

      Yeah.

   4. LFLex Fridman36:19

      ... a good person to ask, which is, uh, Penrose's, Roger Penrose's work on consciousness saying that there, you know, there is some, uh, with axons and so on, there might be some biological places where quantum mechanics can come into play, and through that create consciousness somehow.

   5. SAScott Aaronson36:35

      Yeah. Okay, well, um, uh-

   6. LFLex Fridman36:37

      Are you familiar with his work at all?

   7. SAScott Aaronson36:38

      Of course. You know, I read Penrose's books as a teenager. They had a huge impact on me. Uh, uh, five or six years ago, I had the privilege to actually talk these things over with Penrose, you know, at some length, at a conference in, in Minnesota. And, uh, you know, he is a, a, you know, an amazing, uh, personality. I admire the fact that he was even raising such, uh, audacious questions at all. Uh, but, you know, to, to, to answer your question, I think the first thing we need to, uh, get clear on is that he is not merely saying that quantum mechanics is relevant to consciousness-

   8. LFLex Fridman37:12

      Mm-hmm.

   9. SAScott Aaronson37:12

      ... right? That would be like a m-... you know, that would be tame compared to what he is saying, right? He is saying that, you know, even quantum mechanics is not good enough, right? If, because if, if supposing, for example, that the brain were a quantum computer, right? That's still a computer.

   10. LFLex Fridman37:28

       Yeah.

   11. SAScott Aaronson37:28

       You know, in fact, a quantum computer can be simulated by an ordinary computer.

   12. LFLex Fridman37:32

       That's right.

   13. SAScott Aaronson37:32

       It might merely need exponentially more time in order to do so, right? So that's simply not good enough for him. Okay. So what he wants is for the brain to be a quantum gravitational computer, or, or, uh, uh, uh, he wants the brain to be exploiting as yet unknown laws of quantum gravity, okay, which would, which would be uncomputable-

   14. LFLex Fridman37:55

       Uncomputable.

   15. SAScott Aaronson37:55

       ... according to this.

   16. LFLex Fridman37:56

       That's the key point.

   17. SAScott Aaronson37:57

       Okay. Yes, yes. They would be literally uncomputable, and I've asked him, you know, to clarify this, but uncomputable even if you had an oracle for the halting problem, or in, you know, in, in ... or, you know, as high up as you want to go in the sort of high-

   18. LFLex Fridman38:13

       (laughs)

   19. SAScott Aaronson38:13

       ... the usual hierarchy of uncomputability.

   20. LFLex Fridman38:15

       Mm-hmm.

   21. SAScott Aaronson38:15

       He wants to go beyond all of that. Okay. So, so, you know, just, just to be clear, like, you know, if, if we're keeping count of how many speculations-

   22. LFLex Fridman38:24

       (laughs)

   23. SAScott Aaronson38:24

       ... you know, there's probably like at least five or six of them, right?

   24. LFLex Fridman38:27

       Yeah.

   25. SAScott Aaronson38:27

       There is first of all that there is some quantum gravity theory that would involve this kind of uncomputability, right? Most people who study quantum gravity would not agree with that. They would say that what we've learned, uh, you know, what little we know about quantum gravity from the, this AdS-CFT correspondence, for example, has been very much consistent with the broad idea of nature being computable, right? Um, but, uh, but all right.

   26. LFLex Fridman38:54

       So-

   27. SAScott Aaronson38:54

       But, but sup- supposing that he's right about that, then, you know, mo- what most physicists would say is that whatever new phenomena there are in quantum gravity, you know, they might be relevant at the singularities of black holes. They might be relevant at the Big Bang. Uh, they are plainly not relevant to something like the brain, you know, that is operating at ordinary temperatures-

   28. LFLex Fridman39:20

       Right.

   29. SAScott Aaronson39:20

       ... you know, with, uh, ordinary chemistry. And, you know, the, the, the physics underlying the brain, they, they would say that we have, you know, the fundamental physics of the brain, they would say that we've pretty much completely known for, for generations now, right? Uh, because, you know, quantum field theory lets us sort of parameterize our ignorance, right? I mean, S- Sean Carroll has made this case in, you know, in great detail, right, that sort of whatever new effects are coming from quantum gravity, you know, they are sort of screened off by quantum field theory, right? And this is, this bring, you know, brings us to the whole idea of effective theories, right? But the ... Like we have, you know, the, in like the standard model of elementary particles, right, we have a quantum field theory that seems totally adequate for all of the terrestrial phenomena, right? The only things that it doesn't, you know, explain are, well, first of all, you know, the details of gravity, if you were to probe it, like at, at, uh, uh, you know, extremes of, you know, curvature, or at like incredibly small distances. It doesn't explain dark matter. It doesn't explain black hole singularities, right? But these are all very exotic things, very, you know, far removed from our life on Earth.

   30. LFLex Fridman40:36

       Yeah.
6. 46:28 – 50:16

   Turing test

   1. SAScott Aaronson46:28

   2. LFLex Fridman46:29

      So on Alan Turing, you took part in the Loebner Prize? Uh-

   3. SAScott Aaronson46:32

      Uh, not really, no.

   4. LFLex Fridman46:33

      Or was it-

   5. SAScott Aaronson46:34

      I didn't. I mean, there was this, uh, uh-

   6. LFLex Fridman46:37

      Oh, so-

   7. SAScott Aaronson46:37

      ... kind of ridiculous claim that was made, uh, some, almost a decade ago about an, a chatbot called Eugene Goostman.

   8. LFLex Fridman46:46

      Yeah, apologize. I guess you didn't participate as a judge in the Loebner Prize-

   9. SAScott Aaronson46:48

      I didn't, no.

   10. LFLex Fridman46:49

       ... but you participated as a judge in that, I guess it was an ex- exhibition event or something like that, or with Eugene, uh-

   11. SAScott Aaronson46:56

       Yeah, no, Eugene Goostman, that was just me writing a blog post because some journalist-

   12. LFLex Fridman47:00

       Oh.

   13. SAScott Aaronson47:00

       ... called me to ask about it.

   14. LFLex Fridman47:01

       Did you ever chat with him? I thought there was-

   15. SAScott Aaronson47:03

       I did chat with Eugene Goostman.

   16. LFLex Fridman47:04

       Okay.

   17. SAScott Aaronson47:04

       I mean, a bit, it was available on the web, the chapter.

   18. LFLex Fridman47:06

       Oh, interesting, I didn't know.

   19. SAScott Aaronson47:07

       So yeah. So all, all, all that happened (laughs) was that, uh, so, you know, a bunch of journalists started writing breathless articles about, you know, when, uh, you know, first, uh, chatbot that passes the Turing test, right? And it was this thing called Eugene Goostman that was supposed to simulate a 13-year-old boy-

   20. LFLex Fridman47:24

       Yeah.

   21. SAScott Aaronson47:25

       ... and, um, you know, and apparently someone had done some test where, you know, people couldn't, you know, you know, were, were less than perfect, let's say, at distinguishing it from a human. And they said, "Well, if you look at Turing's paper and you look at, you know, the percentages that he, that he talked about, then, you know, it seemed like we're past that threshold," right? And, you know, I had a sort of, you know, different way to look at it instead of the legalistic way, like, "Let's just try the actual thing out and let's see what it can do with questions like, you know, is Mount Everest bigger than a shoebox?"

   22. LFLex Fridman48:01

       Right.

   23. SAScott Aaronson48:01

       Okay? Or just, you know, like the most obvious questions, right? And then, and, you know, and the answer is, well, it just kind of parries you because it doesn't know what you're talking about, right? Yeah.

   24. LFLex Fridman48:11

       So, so just to clarify exactly in which way they're obvious. They're obvious-

   25. SAScott Aaronson48:16

       Yeah.

   26. LFLex Fridman48:16

       ... in the sense that you convert the sentences into the meaning of the objects they represent and then do some basic... Obvious would mean they, you're-

   27. SAScott Aaronson48:25

       Well-

   28. LFLex Fridman48:25

       ... common sense reasoning, uh, with the objects that the sentences represent.

   29. SAScott Aaronson48:29

       Uh, right, right. It was not able to answer, you know, or, or even intelligently respond to basic common sense questions. But let me say something stronger than that. There was a famous chatbot in the '60s called ELIZA, right? That, you know, that managed to actually fool, you know, a lot of people, right? Or people would pour their hearts out into this ELIZA 'cause it, it simulated a therapist, right? And most of what it would do is it would just throw back at you whatever you said, right? And this turned out to be incredibly effective, right? Uh, may- maybe, you know, therapists, uh, know this. This is, you know, one of their tricks. But, uh, it, um, um, you know, it, it, it really had some people convinced. Uh, but, you know, this, this thing was just like... I think it was literally just a few hundred lines of Lisp code, right? It was... Not only was it not intelligent, it wasn't e- especially sophisticated.

   30. LFLex Fridman49:22

       (laughs)
7. 50:16 – 58:46

   GPT-3

   1. LFLex Fridman50:16

      Yeah, I'd love to hear your thoughts about GPT-3-

   2. SAScott Aaronson50:18

      Yeah, yeah, in the- yeah-

   3. LFLex Fridman50:19

      ... and advancements -

   4. SAScott Aaronson50:19

      ... in the last, in the last few months, we've had, you know, we've, we've, the world has now seen a, uh, chat engine, or a text engine, I should say, called GPT-3, um, that, you know, I think it, it still, you know, it does not pass a touring test. You know, there were no real claims that it passes the touring test, right? You know, this is, comes out of the group at OpenAI, and you know, they're, you know, they've been relatively careful in what they've claimed about this system. But I think this, this, this, uh, uh, a- as clearly as Eugene Goostman was not an advance over ELIZA, it is equally clear that this is a major advance-

   5. LFLex Fridman50:58

      It is.

   6. SAScott Aaronson50:58

      ... over, over, over ELIZA, or really over anything that the world has seen before. Uh, this is a text engine that can come up with kind of on-topic, you know, reasonable-sounding completions to just about anything that you ask. You can ask it to write a poem about topic X in the style of poet Y-

   7. LFLex Fridman51:21

      Mm-hmm.

   8. SAScott Aaronson51:21

      ... and it will have a go at that.

   9. LFLex Fridman51:22

      Yeah.

   10. SAScott Aaronson51:23

       And it will do, you know, not a perf- not a great job, not an amazing job, but you know, a passable job. You know, definitely, you know, as, as good as, you know, you know, in, in many cases I would say better than I would've done, right? Uh, you know, you can ask it to write, you know, an essay, like a student essay about pretty much any topic, and it will get something that I am pretty sure would get at least a B-, you know, in most, you know, high school or even college classes, right? And, you know, in some sense, you know, the way that it did this, the way that it achieves this, um, you know, Scott Alexander of the, you know, the much, uh, mourned blog, uh, Slate Star Codex, uh, had a wonderful way of putting it. He said that they basically just ground up the entire internet into a slurry.

   11. LFLex Fridman52:10

       (laughs)

   12. SAScott Aaronson52:10

       Okay?

   13. LFLex Fridman52:11

       Yeah.

   14. SAScott Aaronson52:11

       And you know, and I, to tell you the truth, I had wondered for a while why nobody had tried that, right? Like, why not write a chatbot by just doing deep learning over a corpus consisting of the entire web, right?

   15. LFLex Fridman52:24

       Right.

   16. SAScott Aaronson52:25

       And, and so, so the, so, uh, now they finally have done that, right? And, you know, the results are, are very impressive. You know, it's not clear that, you know, people can argue about whether this is truly a step toward general AI or not, but this is an amazing capability, uh, that, you know, uh, uh, we didn't have a few years ago. That, you know, if- a few years ago, if you had told me that we would have it now, that would've surprised me.

   17. LFLex Fridman52:53

       Yeah.

   18. SAScott Aaronson52:53

       And I think that anyone who denies that is just not engaging with, with what's there.

   19. LFLex Fridman52:57

       So their model takes a large part of the internet-

   20. SAScott Aaronson53:02

       Mm-hmm.

   21. LFLex Fridman53:02

       ... and compresses it in a small number of parameters-

   22. SAScott Aaronson53:05

       Mm-hmm.

   23. LFLex Fridman53:05

       ... relative to the size of the internet.

   24. SAScott Aaronson53:07

       Mm-hmm.

   25. LFLex Fridman53:07

       And is able to, without fine-tuning, uh, do a basic kind of a querying mechanism, just like you described, where you specify a kind of poet, and then you wanna write a poem, and somehow is able to do basically a lookup on the internet-

   26. SAScott Aaronson53:22

       Well-

   27. LFLex Fridman53:23

       ... of relevant things. I mean, that's what it...

   28. SAScott Aaronson53:25

       I mean, I mean, I mean, the- the-

   29. LFLex Fridman53:26

       How else do you explain it?

   30. SAScott Aaronson53:27

       Well, okay, I mean, I mean, I mean, the, the training involved, you know, massive amounts of data from the internet, and actually took lots and lots of computer power, lots of electricity, right? You know, there, there are some, some very prosaic reasons why this wasn't done earlier, right?
8. 58:46 – 1:05:17

   Universality of computation

   1. SAScott Aaronson58:46

   2. LFLex Fridman58:47

      Let me go on another topic-

   3. SAScott Aaronson58:48

      Yeah. Sure.

   4. LFLex Fridman58:48

      ... that is amazing, uh, which is complexity.

   5. SAScott Aaronson58:52

      Hm.

   6. LFLex Fridman58:53

      Uh, what, uh... (laughs) and then start with the most absurdly romantic question of what's the most beautiful idea in the computer science or theoretical computer science to you? Like, what just-

   7. SAScott Aaronson59:04

      Yeah.

   8. LFLex Fridman59:04

      ... earl- early on in your life, or in general-

   9. SAScott Aaronson59:06

      Mm-hmm.

   10. LFLex Fridman59:06

       ... have captivated you-

   11. SAScott Aaronson59:07

       Yeah.

   12. LFLex Fridman59:07

       ... and just grabbed you?

   13. SAScott Aaronson59:08

       I think I'm gonna have to go with the idea of universality. Uh, you know, if you're really asking for the most beautiful. (laughs) I mean, uh, so universality, uh, is the idea that, you know, you put together a few simple operations, like, in the case of Boolean logic, that might be the AND gate, the OR gate, the NOT gate, right? And then your first guess is, "Okay. This is a good start, but obviously, as I wanna do more complicated things, I'm gonna need more complicated building blocks to express that," right? And, and that was actually my guess when I first learned what programming was. I mean, when I was, you know, an adolescent, and I... someone showed me, uh, uh, Apple BASIC, and then, you know, uh-

   14. LFLex Fridman59:52

       (laughs)

   15. SAScott Aaronson59:52

       ... GW-BASIC, if, uh-

   16. LFLex Fridman59:54

       Oh, wow.

   17. SAScott Aaronson59:54

       ... any, any, anyone listening remembers that. Okay. But, uh, you know, I thought, "Okay. Well, now..." You know, I mean, I mean, I, I thought, I felt like, um, this is a revelation. You know, it's like finding out where babies come from.

   18. LFLex Fridman1:00:06

       Yeah. (laughs)

   19. SAScott Aaronson1:00:06

       It's like that level of, you know, "Why didn't anyone tell me this before?"

   20. LFLex Fridman1:00:09

       Yeah. (laughs)

   21. SAScott Aaronson1:00:09

       Right? But I thought, "Okay. This is just the beginning. Now I know how to write a basic program." But to, you know, really write a, an interesting program, like a, you know, a video game, which had always been my, my dream as a kid to, you know, create my own Nintendo games, right?

   22. LFLex Fridman1:00:25

       (laughs)

   23. SAScott Aaronson1:00:25

       That, you know, but I'm... You know, obviously, I'm gonna w- need to learn some way more complicated form of programming than that. Okay? But, you know, eventually, I learned this incredible idea of universality, and that says that, no, you throw in a few rules, and then you can... you already have enough to express everything. Okay? So for example, the AND, the OR, and the NOT gate, uh, can all... or in fact, even just the AND and the NOT gate-

   24. LFLex Fridman1:00:51

       Right. Exactly.

   25. SAScott Aaronson1:00:51

       ... or e- even just, even just the NAND gate, for example, uh, is already enough to express any Boolean function on any number of bits. You just have to string together enough of them, right?

   26. LFLex Fridman1:01:01

       You can build a universe with NAND gates.

   27. SAScott Aaronson1:01:03

       You can build a universe out of NAND gates, yeah. Uh, you know, the, the simple instructions of BASIC are already enough d- at least in principle, you know? If we ignore details like how much memory can be accessed-

   28. LFLex Fridman1:01:16

       Mm-hmm.

   29. SAScott Aaronson1:01:16

       ... and stuff like that, that is enough to express what could be expressed by any programming language whatsoever. And the way to prove that is very simple. We simply need to show that in BASIC or whatever, we could write a, an interpreter or a compiler for whatever is... other programming language we care about, like C or, or Java or whatever. And as soon as we had done that, then ipso facto, anything that's expressible in C or Java is also expressible in BASIC. Okay? And-So this idea of universality, you know, goes back, uh, at least to Alan Turing in the 1930s, when, you know, he, uh, uh, um, wrote down this incredibly simple pared down model of a computer, the Turing machine, right, which, uh, you know, he pared down the instruction set to just read a symbol, you know, go, mo-, write a symbol, move to the left, move to the right, uh, halt, change your internal state, (laughs) right? That's it.

   30. LFLex Fridman1:02:16

       Simple.
9. 1:05:17 – 1:11:23

   Complexity

   1. SAScott Aaronson1:05:17

   2. LFLex Fridman1:05:17

      Exactly, so-

   3. SAScott Aaronson1:05:18

      Yeah.

   4. LFLex Fridman1:05:18

      ... you- you've, uh, I don't know if you created complexity zoo, or, uh-

   5. SAScott Aaronson1:05:21

      I did create the complexity zoo.

   6. NANarrator1:05:23

      Definitely-

   7. LFLex Fridman1:05:23

      What is it? What's complexity?

   8. SAScott Aaronson1:05:25

      Oh, okay. Oh, all right, all right, all right, all right. Complexity theory is the study of sort of the inherent resources needed to solve, uh, computational problems.

   9. LFLex Fridman1:05:34

      Mm-hmm.

   10. SAScott Aaronson1:05:34

       Okay, so, uh, uh, it- it's easiest to give an example. Uh, like, uh, let's say we want to, um, um, add two- two numbers, right? If I wanna add them, uh, um, you know, if- if the numbers are twice as long, then it only... it will take me twice as long to add them, but only twice as long, right? It's no worse than that. Multi-

   11. LFLex Fridman1:05:54

       For a computer.

   12. SAScott Aaronson1:05:55

       For a computer-

   13. LFLex Fridman1:05:56

       (laughs)

   14. SAScott Aaronson1:05:56

       ... or- or- or for a person. We're using pencil and paper, for that matter.

   15. LFLex Fridman1:05:59

       If you have a good algorithm.

   16. SAScott Aaronson1:06:00

       Yeah, that's right. I mean, even-

   17. LFLex Fridman1:06:01

       You- you could have an inefficient algorithm.

   18. SAScott Aaronson1:06:01

       ... if you just, if you just use the elementary school algorithm-

   19. LFLex Fridman1:06:04

       Right.

   20. SAScott Aaronson1:06:04

       ... of just carrying, you know, then it- it takes time that is linear in the length-

   21. LFLex Fridman1:06:09

       The-

   22. SAScott Aaronson1:06:09

       ... of the numbers, right? Now, multiplication, if you use the elementary school algorithm, is harder, because you have to multiply each digit of the first number by each digit of the second one.

   23. LFLex Fridman1:06:20

       That's right, yeah. Yeah.

   24. SAScott Aaronson1:06:21

       You know, and then deal with all the carries. So that's what we call a quadratic time algorithm, right? If, um, the numbers become twice as long, now you need four times as much time, okay? So, uh, now, as it turns out, we, uh, uh, uh, people discovered much faster ways to multiply numbers using computers.

   25. LFLex Fridman1:06:41

       Mm-hmm.

   26. SAScott Aaronson1:06:41

       And today, we know how to multiply two numbers that are n-digits long using a number of steps that's nearly linear in n. These are questions you can ask, but now let's think about a different thing that people, uh, you know, they've encountered in elementary school, uh, factoring a number.

   27. LFLex Fridman1:06:58

       Mm-hmm.

   28. SAScott Aaronson1:06:58

       Okay, take a number and find its prime factors.

   29. LFLex Fridman1:07:02

       Mm-hmm.

   30. SAScott Aaronson1:07:02

       Right? And here, you know, if I give you a number with 10 digits and I ask you for its prime factors, well, maybe it's even, so you know that two is a factor. You know, maybe it ends in zero, so you know that 10 is a factor, right? But, you know, other than a few obvious things like that, you know, if the prime factors are all very large, then it's not clear how you even get started, right? You know, you- it seems like you have to do an exhaustive search among an enormous number of factors. Now, um, and- and, uh, as many people might know, uh, the, uh, for- for- for better or worse, the, uh, security, you know, of most of the encryption that we currently use to protect the internet is based on the belief, and this is not a theorem, it's a belief-
10. 1:11:23 – 1:23:41

    P vs NP

    1. SAScott Aaronson1:11:23

    2. LFLex Fridman1:11:23

       So what kind of interesting classes are there?

    3. SAScott Aaronson1:11:25

       Yeah.

    4. LFLex Fridman1:11:25

       I mean, y- you could have just, maybe say what are the, if you take any kinda computer science class, what are the classes you learn?

    5. SAScott Aaronson1:11:32

       Good. Let me, let me tell you sort of the, the, the biggest ones, the ones that you would learn first. So, you know, first of all, there is P, that's what it's called, okay? It stands for polynomial-time. And this is just the class of all of the problems that you could solve with a conventional computer, like your iPhone or your laptop, uh, you know, by a completely deterministic algorithm, right? Using a number of steps that grows only like the size of the input raised to some fixed power.

    6. LFLex Fridman1:12:05

       Mm-hmm.

    7. SAScott Aaronson1:12:05

       Okay? So, uh, if your algorithm is linear-time, like, you know, for adding numbers, okay, that, that problem is in P. If you have an algorithm that's quadratic-time, like the, uh, elementary school algorithm for multiplying two numbers, that's also in P. Even if it was the size of the input to the 10th power or to the 50th power, well, that wouldn't be very, uh, good in practice, but, you know, formally, we would still count that. That would still be in P. Okay? But if your algorithm takes exponential time, meaning, like, if every time I add one more, uh, data point to your input, if the time that needed by the algorithm doubles-

    8. LFLex Fridman1:12:47

       Mm-hmm.

    9. SAScott Aaronson1:12:47

       ... if you need time like two to the power of the amount of input data, then, uh, that is a, that we call an exponential-time algorithm, okay? And th- that is not polynomial, okay? So P is all of the problems that have some polynomial-time algorithm. Okay? So that includes most of what we do with our computers on a day-to-day basis, you know, all the, you know, sort- sorting, basic arithmetic, you know, whatever is going on in your email reader or in Angry Birds, okay? It's al- it's all in P.

    10. LFLex Fridman1:13:19

        Okay.

    11. SAScott Aaronson1:13:19

        Then the next, uh, super important class is called NP. Uh, that stands for non-deterministic polynomial, okay? Does not stand for not polynomial-

    12. LFLex Fridman1:13:29

        Yeah.

    13. SAScott Aaronson1:13:29

        ... which is a, a-

    14. LFLex Fridman1:13:30

        (laughs)

    15. SAScott Aaronson1:13:30

        ... common confusion. Um, but, but NP is basically all of the problems where if there is a solution, then it is easy to check the solution if someone shows it to you.Okay? So actually, a perfect example of a problem in NP is, uh, factoring, the one I told you about before. Like, if I gave you a number with thousands of digits and I told you that it ha- you know, I- I- I asked you, "Does this, uh, does this have at least, um, three non-trivial divisors?" Right? That might be a super hard problem to solve, right? It might take you millions of years-

    16. LFLex Fridman1:14:07

        Yeah.

    17. SAScott Aaronson1:14:07

        ... using any algorithm that's known, at least running on, on our existing computers. Okay? But if I simply showed you the divisors, I said, "Here are three divisors of this number," then it would be very easy for you to ask your computer to just check each one and see if it works, just divide it in, see if there's any remainder, right? And if they all go in, then you've checked, "Well, I guess there were," (laughs) right? So, um, so any problem where, you know, whe- wherever there's a solution, there is a short witness that can be easily like, a polynomial size witness, that can be checked in polynomial time, that, we call an NP problem. Okay?

    18. LFLex Fridman1:14:48

        Beautiful.

    19. SAScott Aaronson1:14:49

        And, uh, yeah. So, so every problem that's in P is also in NP, right? Because, you know, you could always just ignore the witness and just, you know, if a problem is in P, you can just solve it yourself.

    20. LFLex Fridman1:15:00

        Right.

    21. SAScott Aaronson1:15:00

        Okay? But now the, in some sense, the central, you know, mystery of theoretical computer science is, is every NP problem in P. So, if you can easily check the answer to a, a, a, a computational problem, does that mean that you can also easily find the answer?

    22. LFLex Fridman1:15:18

        Even though there's all these problems that appear to be very difficult to find the answer, it's still an open question whether a-

    23. SAScott Aaronson1:15:26

        Yeah.

    24. LFLex Fridman1:15:26

        ... good answer exists. So what's your-

    25. SAScott Aaronson1:15:27

        Because no one has proven that there's no way to do it, right?

    26. LFLex Fridman1:15:29

        It's arguably the most, uh, I don't know, the most famous, the most maybe interesting, maybe you disagree with that-

    27. SAScott Aaronson1:15:38

        Well-

    28. LFLex Fridman1:15:38

        ... problem in theoretical computer science. So what's your-

    29. SAScott Aaronson1:15:40

        The most famous, for sure. (laughs)

    30. LFLex Fridman1:15:41

        P equals NP.

Episode duration: 1:52:36