YouSaid · the spoken record

Donald Knuth

lines on the record: 150
first: 2021-09-09
most recent: 2021-09-09
sittings or episodes: 1
sources: podcast

Every line below is reproduced as it was said and linked to the record it came from. Nothing here is summarised or generated. Directory · Search · Corrections

“Okay, now then there's an anarchist in Russia who sees that wars are something that leaders start, but actually people get killed. And so he wants to stop. Any alliance between England and Russia because that would mean that thousands and thousands of people of Russia would be killed, that wouldn't be otherwise killed. All right. And so his life's goal is to assassinate a Russian prince who's visiting England because that will mean the Tsar will not form the alliance, all right? So we have this. Question about what should the government do? Should it actually do something that will lead to is the war inevitable or is there a way to have peace? And it struck me that if I were in a position of responsibility for people's lives, in most cases were good, that these questions are too hard probably for any human being, but certainly for me.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“There's a lot of bad things all the time, and I read about, you know, I look at things and people had good ideas and they were working on great projects. And then I know that it didn't succeed, though in the end, but the new insight I've gotten actually in that way was I was reading What book was I reading recently? It was by Ken Follett and it was called The Man from St. Petersburg. But it was talking about the prequel to World War I. And Winston Churchill, according to this book, sees that Germany has been spending all its gold reserves building up a huge military. And there's no question that if Germany would attack England, that England would be wiped out. So he wants Russia to help to attack Germany from the other side because Germany doesn't have enough of an army to be fighting two wars at once.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“A fun one. Yeah. I mean, as so many people have said, it's the journey, not the destination. And people live through crises, help each other. Things come up. History repeats itself. You try to say in the world today, is there any government that's working? I read history. I know that things were...”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“But what I'm trying to say is I'm not trying to say of all the strategies I could choose or something which one, I try to do it not strategically, but I try to. To imagine that I'm following somebody's wishes.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“I strive for that. Not that I Ever think I'm going to get close to it, but it's not for me. It's saying, what should I do that that big being wants me to do? I'm trying to ask What that, I mean, did that being want me to be talking to Lex Friedman right now, you know? And I said, yes, okay.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“That was in Zen. All right, so anyway. It's only for me and But I personally Think of my belief that. That God exists, although I have no idea what that means, but I believe that there is. Something beyond human capabilities might be some AI, but whatever it is, but whatever, but I do believe that That there is something that goes beyond the realm of human understanding. But that I can try to. Learn more about how to resonate with whatever that Being would like me to do”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, oh yeah. I came earlier today and I walked around Foster Street. I didn't know what was going on in Foster City. I saw some beautiful flowers at the nursery at Home Depot for a few blocks away.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Sometimes it's more difficult than others to do this. I mean during the COVID, lots of days when I never saw another human being. But I still find other ways to...”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“I probably overreact another way when I see everybody else going some way, I probably. I probably say, hmm, too much competition. But mostly I played with things that were interesting to me and then later on I found, oh, actually the most important thing I learned was how to be interested in almost anything. Not to be bored. It makes me very sad when I see kids talking to each other and they say, That was boring. And to me, a person should feel. Upset if he had to admit that he wasn't able to find something interesting.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“You try it and it works, or it doesn't work. I mean, you learn about yourself. Life is a binary search. You try something and you find out, oh, yeah, I have a background that helped me with this. Or maybe I could do this if I worked a little bit harder. But you try something else and you say, I have really no intuition for this. And it looks like. It looks like it doesn't have my name on it”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Always the same as I've said before, I guess. Do something because it's trendy, but it's something that you personally feel that you were called to do. Rather than somebody else expects you to do.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“You give me too much credit, but anyway, this is my turn to say things that I believe. But I want to preface it by saying I also believe that other people do a lot of these things much better than I do. So I can only tell you my side of it.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Right. The one I haven't got any good reason that I'll never be able to do it any better than I am now. I mean, there are some things that I know if I do. Something else first, I'll be able to do that one better, yeah. But there's some that are going to be harder because I have forgotten some of the groundwork that went into it or something like that. So I just finished a pretty tough part of the book. And so now I'm doing the parts that are more fun. But the other thing is as I'm writing the book, of course, I want. Reader to think that I'm happy all the time I'm writing the book it's upbeat. I can have humor I can say this is cool and this I have to I have to disguise the fact that it was painful in any way”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“To others, well, I yeah, I don't know how to say it during the pandemic. I feel my productivity actually went down by half because I have to. I have to communicate by writing, which is slow, I have to, I mean, I don't like to send out a bad sentence. I go through and reread what I've written and edit and fix it. So everything takes a lot longer when I'm communicating by text messages instead of just together with somebody in a room. And it's also slower because the libraries are closed and stuff. But there's another thing about scheduling that I learned from my mother that I should probably tell you, and that is. Different from what people in robotics feel do, which is called planning. So she had this principle that was sees something that needs to be done and do it.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Oh, I see. Well, but all the time I'm working on what I want to do. But still, I'm glad to have all those unpleasant tasks finished. Yes.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“It's like coloring. But it was very lucky that we worked for the United States. I think, but the theory is still very uncomplete. But anyway, then Tom came back a couple days later and he had been able to not only find a graceful labeling, but the label of Washington was 31, the label of Idaho was 41, following the digits of pi. Going across the topic of the United States. He has the digits of Pi perfectly.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“More precisely, I had figured out a way to put labels on so that all the edges were labeled somewhere between 1 and 117. But there were some gaps in there because I should really have gone from 1 to 105, whatever the number is. So I gave myself a little too much, a lot of slack. He did it without any slack whatsoever. Perfect graceful labeling. And so I call out the contest because the problem is already solved and too easy in a sense because Tom was able to do it in an afternoon.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“But my friend Tamruki actually solved the problem by proving that, I mean, I was able to get it down. Within seven or something like that, he was able to get a perfect solution.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“So I started with a graph that I use for an organic graph, not a mathematically symmetric graph or anything, and I take the 49 states of the United States. The edges go from one state to the next state. So, for example, California. Next to Oregon, Nevada, Arizona. And I include District of Columbia. So I have 49. I can't get Alaska and Hawaii in there because they don't touch. You have to be able to drive from one to the other. So is there a graceful labeling of the United States? Each state gets a number. And then if California is number 30 and Oregon is number 11, that edge is going to be number 19. The difference between those, okay? So, is there a way to do this for all the states? And so I was thinking of having a contest for people to get it as graceful as they could.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“And so, and it turned out there was a unique way to do that. And so Pi is a source of examples where I can prove that I'm starting with something that isn't canned. And most recently, I was writing about something called graceful graphs. Graceful graphs is the following. You have a graph that has M edges to it. And you attach numbers to every vertex in the following way. So every time you have an edge between vertices, you take the difference between those numbers. And that difference has got to be, I'll tell you what edge it is. So one edge, two numbers will be one apart. There'll be another edge where the numbers are two apart. And so Great computer problem. Can you find a graceful way to label a graph?”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“You can find it on Wikipedia, certainly as an example, M-A-S-Y-U. And so I decided I would take Pi, the actual image of it. And it had pixels. And I would put a stone wherever it belongs in the letter Pi, in the Greek letter Pi. The problem was find a way to make some of the stones white, some of the stones black, so that there's a unique solution to the Masu puzzle. That was a good test case for my algorithm on how to design Master puzzles because I insisted in advance that the stones had to be placed in exactly the positions that make the letter pi, make a choice.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Pi, of course. I try to use as often as I can when I need a random example. Because it doesn't have any known characters. So for instance, I don't have here to show you, but do you know the game called Masu M-A-S-Y It's a great recreation. I mean, Sudoku is easier to understand, but Matthew is more addictive. You have black and white stones like on a go board, and you have to draw a path that... Goes straight through a white stone and makes a right angle turn at the black stone. And it turns out to be a really nice puzzle because it doesn't involve numbers, which is visual, but 3D pleasant to play with. So I wanted to use it as an example in art of computer programming. And I have exercise on how to design cool masu puzzles.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Is that symbol exists in fact? By the way, he made a movie in the early 50s. I don't remember the name of the movie. Now you can probably find it easily enough. But it features dozens and dozens of pianos all playing together at the same time. But all the scenery is sort of based on the kind of artwork that was in his books and the fantasy based of Seussland. And I saw the movie only once or twice, but it's quite... I'd like to see it again.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, I'll stick with Ubuntu, but right now I'm running something that doesn't support a lot of the new. Software, the last stable. I don't remember the number were like 14. Anyway, it's quite, and I'm going to get a new computer. I'm getting new solid state memory instead of a hard disk.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Really, yeah, I know. I mean, there's a lot of really subtle Nobel Prize class creation of intellectual property in there. And with patents, you've got a limited time to. I mean, the idea of patents is that you publish so that it's not a trade secret.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“So it's definitely worth paying Paying for all this stuff. I mean, well, they keep adding. Adding stuff that my wife and I don't care about, but Somebody, but I mean, but they have built in a fantastic undo feature, for example, in Photoshop, where you can go through a sequence of a thousand complicated steps on graphics and it can take you back anywhere in that sequence. Has a long history with really beautiful algorithms. I mean, yeah, it's.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“I didn't need the income. I already had a good job. My books were People were buying enough books that it would bring Plenty of supplemental income for everything my kids needed for education, whatever. So there was no reason for me to try to maximize income any further. Income is sort of a threshold function. If you don't have, if you don't have enough, you're starving. But if you get over the threshold, then you start thinking about philanthropy or else you're trying to take it with you. But anyway, my income was over the threshold. So I didn't need. Keep it. And so I specifically could see the advantage of making it open for everybody.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“And that was holding everything back because people were tied to a particular manufacturer and then a new equipment is invented a year later, but printing machines, they have to expect to amortize the cost over 20, 30 years.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Okay, well, the word open source didn't exist at that time, but I didn't want proprietary rights over it because I saw how proprietary rights were holding things back in the late 50s people at IBM developed the language called Fortran. They could have Kept it proprietary. They could have said only IBM can use this language. Everybody else has to, but they didn't. They said anybody who can write, who can translate Fortran into the language of their machines is allowed to make Fortran compilers too. On the other hand, in the topography industry, I had seen a lot of languages that were developed for composing pages. And each manufacturer had his own language for composing pages.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Probability was proven, yeah. I was able to prove that this and this shed light on a whole bunch of other things about random graphs, that was sort of the major thing we were after.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“It turned out the actual numbers is like 87%. I should remember the number, but I don't have it with me. But anyway, but the number, it turned out to be like 12 over pi squared, 8 over pi. Anyway, it was a nice. Related to Pi. And we could never have done that. So that's the hardest problem I ever solved in my life was to prove that this probability is”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“But anyway, he happened to visit on exactly the day after I had found this pattern and that allowed me to crack the problem so that I could develop the theory. The theory some more and understand what's happening. But because I could now write down explicit formulas for stuff. And so it would work not only the first few steps, but also study the whole process. And I worked further and further with two authors, co-authors, and we finally figured out that the problem that the rumor was true in other words look at the evolution of a random graph going from zero to complete and say what's the probability that at every point in time there was only one component with a cycle. We started with this rumor saying there's only one component with the cycle.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“And I wrote it down. And anyway, at the end of the day, he was discussing people with the development office, and he said, boy, I was really impressed with what Professor Knuth said about this giant component. And so I love this story because it shows that theoretical computer science is really worthwhile.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“So that said, oh, yeah, let me take the logarithm of this formula. And sure enough, it's going to simplify. And it happened. And I wouldn't have noticed it except for this factorization. Okay. So I go to bed and I say, oh, okay, this looks like I'm slowing down the Big Bang. I can figure out what's going on here. And the next day it turned out Bill Gates comes to Stanford to visit. They're trying to sell him on donating money for a new computer science building. And so they gave me an appointment to talk to Bill and I wrote down on the Blackboard this. This evolutionary diagram, you know, going from one to two, five twenty fourths in all this business”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Had a formula that I calculated the probability. And I could find the limiting probability that n goes to infinity, and it turned out to be this number, but the denominator was 2,000. And I looked at the denominator and I said, wait a minute. This number factors because 1001 is equal to 7 times 11 times 13. I had learned that in my first computer program. So 23023. Is seven times 11 times 13 times 23. That's not a random number. There has to be a reason why those small primes appear in the denominator. But my so all of a sudden that suggested another way of looking at the problem where small prime factors would occur.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“But then it splits again after you have either two or one, the next step is you either have three or you have two one or you have one one. And so I worked out the probability for those transitions And I worked it out up to the first five transitions. And I had these strange numbers, 524s. And I stayed up all night. And about 3 a.m. I had the numbers computed and I looked at them and here were the denominator was something like. Two threes. The probability was something over 230, 23.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“So, in other words, we start out and After I have one loop, I have one component that has a cycle in it. Now, the next step. According to the rumor would be that at the next step I would have a bicycle in the evolution of almost all graphs. It would go from cycle to a bicycle. But in fact, there's a certain probability it goes from cycle to two different cycles. And I worked out the probability it was something like five out of 24.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Right. So the complexity plus one is the number of loops. So if complexity is zero, I have one loop. If complexity is one, that means I have one more edge than I have vertex. So I might have like 11 edges and 10 vertices So we call that a bicycle because it's got two loops and it's got to have two loops.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“So, if the complexity is zero, we have one loop I call a cycle, or I call it a cyclic component. So cyclic component looks like a wheel to which you attach fibers or trees. They go branchy, but there's no more loops. There's only one loop and everything else feeds into that loop, okay? And that has complexity zero. But a tree itself has complexity minus one because it has it might have 10 vertices and nine edges to tie them together. So nine minus 10 is minus 1. So complexity minus one is a tree. It's got to be connected. That's what I mean by a component. It's got to be connected. So if I have 10 things connected, I have to have nine edges.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“And so let's watch the evolution. And at first, these edges are coming along and they're just making things without loops. Which we call trees. Okay, so then all of a sudden a loop first appears. So at that point, I have one component that has a loop. Now I say that the complexity of a component is the number of edges minus the number of vertices. So if I have a loop, I have like a loop of length five, has five edges and five vertices. Or I could put a tail on that. And that would be another edge, another vertex.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“That's it. Yeah. I started looking at this to make it quantitative. Problem was to slow down the Big Bang so that I could watch it happening. I think I can explain it actually in fairly elementary terms, even without writing a formula. That's right. Like Hawking would do.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“With very high probability, this seemed to be true. So we heard about this rumor at Stanford, and we said, if that's true, then more must also be true. So there's a whole theory out there waiting to be discovered that we haven't ever thought about. So let's take a look at that. And so we look closer and we found out, no, actually it's not true. But in fact, it's almost true namely There's a very short interval of time when it's true. And if you don't happen to look at it during that short interval of time, then you miss it. So, in other words, there'll be a period where there are two or three components that have loops, but they join together pretty soon. So, if you don't have a real fast shutter speed, you're going to miss that instant.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Take a look at what the graph is. And the rumor was that every time they looked, there was only one component that had loops in it, almost always. They do a million experiments and only three or four times did they ever ever happen to see a loop at this point. No, more than one component with the loop. So the graph gets completely full. So it starts out totally empty and gets more and more and more edges all the time. And so, okay, certainly a loop comes along once. But now all the loops stay somehow joined to that one. They're never...”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“It's exactly it's a phase transition, but it's a double phase transition. It turns out it happens. There's actually two things going on at once at this phase transition, which is very remarkable about. Okay, so. So a lot of the most important algorithms are based on random processes. And so I want to understand random processes and how there are data structures that sort of grow this way. Okay, so Dick Carp, one of the leading experts on randomized algorithms, had his students working looking at this at Berkeley. And we heard a rumor that the students had found something interesting happening are generating this simulating this random evolution of graphs and they're taking snapshots ever so often.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“I could have just as well drawn straws or something. This was a concept invented by Erdos and Rainy, and they called evolution of random graphs. And if you start out with a large number n and you repeat this process, all of a sudden a big bang happens at one half n. There will be two points together, then maybe we'll have three. Then they maybe branch out a little bit. But I'll be separate until we get to one half end. We pass one half N and all of a sudden there's substance to it. There's a big clump of stuff.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Any source of the point is every step choose totally at random one of those endpoints Choose totally at random another one of the endpoints. Make that an edge. That's the process”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, I call it the pie graph. No, no, the pie graph is actually, my pie graph is based on binary representation of pi not the decimal representation of pi. But anyway, let's suppose I was rolling dice instead. So I might”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“But if I had 0.51 inches, so a little more than half, so million points, 510,000 edges. It probably has one component that's much bigger than the others. And we call that the giant compon”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“All right, now let's take pi, the digits of pi, so two at a time. So we had 31, 41, 59, 26. We can go through pi. And so we take the first two, 31, 41, and let's put a connection between 0.31 and 0.41. That's an edge in the graph. So then we take 5926 and make another edge. The graph gets more and more connected. As we add these things one at a time, we started out with endpoints and we add M edges. Okay, each edge is completely, we forgot about edges we had before. We might get an edge twice. We might get an edge from a point to a selfie, but maybe pi is going to have a run of four digits in there. So we're going to, but anyway We're evolving a graph at random. And a magical thing happens when the number of edges is like 0.49 and so maybe n is a million and I have 490,000 edges, then all the time it consists of isolated trees.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source
“Okay, well, yeah, that's, I don't know how to answer questions like that, but in this case, it's pretty clear. Called the birth of the giant component. Okay, so now let me explain that because this actually gets Gets into physics too. It gets into something called Bose-Einstein Statistics. But anyway, it got some interesting stories and it connected with Berkeley again. So start with the idea of a random graph. Now we just say we have n points that are totally unconnected and there's no geometry involved. There's no saying some points are further apart than others. All points are exactly alike. And let's say we have 100 points and we number them from 0 to 9.”
2021-09-09 · Lex Fridman Podcast · #219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life · IDENTIFIED FROM THE TRANSCRIPT · source