Donald Knuth on Machine Learning and the Meaning of Life – InApps 2022

For decades mathematician Donald Knuth, a professor emeritus at Stanford University, has been a revered figure in the world of programming. In 1962 he began writing a mammoth technical opus titled “The Art of Computer Programming” — which he’s still working on nearly sixty years later.

Because of his ongoing work, Knuth guards his time carefully — so it was a real treat when the 83-year-old programming legend appeared for a wide-ranging conversation on the podcast of Lex Fridman, an AI researcher at the Massachusetts Institute of Technology. Their candid conversation revealed the personality and character behind the famous computer science author — who shared at least a few answers that were surprisingly revealing. Together the two men discussed some overlooked milestones throughout Knuth’s career, including his early attraction to the open source movement.

But by the end of the conversation, they were actually discussing the meaning life.

Here’s my conversation with Donald Knuth, his 2nd time on the podcast. Don is a legendary computer scientist, Turing Award winner, author of The Art of Computer Programming, creator of TeX, and someone who I’ve looked up to for many years. https://t.co/K4uxAigZiY pic.twitter.com/VoaaSfgqOb

— Lex Fridman (@lexfridman) September 9, 2021

Machine Learning in 1957

Fridman introduced Knuth as a “legendary computer scientist, Turing award winner, father of algorithm analysis,” — and also as the creator of the TeX system for typesetting mathematical formulas, “and one of the kindest, most fascinating human beings I’ve ever got a chance to talk to.” Knuth had once responded to a letter that Fridman sent him, and “We’ve interacted many times since then, and every time it’s been joyful and inspiring.”

Knuth had already appeared on another episode of Fridman’s podcast nearly two years ago, back in December of 2019.

But Fridman began this discussion by asking Knuth about his first large-scale program — written 64 years ago, in the year 1957 — to play Tic Tac Toe, written in decimal machine language. “If the manual had been well-written, I probably never would’ve gone into computer science. But it was so badly written, I figured that I must have a talent for it, because I’m only a freshman, and I could write a better manual.”

Fridman: And so you did?

Knuth: And so — I started working at the computer center, and wrote some manuals then. (Laughs) But this was the way we did it.

The Tic Tac Toe program was actually Knuth’s third. His first program had factored a number — although when Fridman asks what his ultimate goal was, Knuth offers a more fundamental answer. “My goal was to see the lights flashing, and understand how this magical machine would be able to do something that took so long by hand…”

“I learned many years later that Charles Babbage had thought about programming Tic Tac Toe for his dream machine that he was never able to finish… More than a hundred years ago.”

Fridman prompts Knuth to talk about how that Tic Tac Toe program had some 1957-style machine learning. “Yeah, that’s right,” Knuth says with a smile (adding “I don’t know how long it’s going to be before the name of our field is changed from computer science to machine learning…”)

Knuth had started tracking which of the 19,683 possible positions in a game of Tic Tac Toe seemed to lead to wins or losses — even with a limited number of bits. “I think I had to work it out  — because every position in Tic Tac Toe is equivalent to roughly eight others, because you can rotate the board, which gives you a factor of four, and you can also flip it over, and that’s another factor of two. So I might’ve needed only three to the ninth over eight positions [which comes out to 2,460] plus a little bit.”

Even with all these technological constraints, Knuth programmed in three different algorithms, dubbing them Brain 1, Brain 2, and Brain 3. And while Brain 1 made its moves at random, Brain 2 followed a pre-set algorithm for optimal playing — and Brain 3 tried to learn how to beat them both.

Sure enough, the playing style of Brain 3 got steadily improved, until “It converged after about 600 games, to a safe draw. The way my program learned was actually, it learned how not to make mistakes… It didn’t try to do anything for winning, it just tried not losing. That was probably because of the way I designed the learning thing. I could’ve had a different reinforcement function that would reward brilliant play… And if I took a novice against a skilled player, it was able to learn how to play a good game.

“After I finished that, I felt I understood programming.”

An Open Source Pioneer

Fridman also asked what made him release the TeX typesetting system as open source back in 1989, nearly a full decade before the dawn of the Open Source movement.

“The word open source didn’t exist at that time,” Knuth remembers, “but I didn’t want proprietary rights over it, because I saw how proprietary rights were holding things back.” Knuth remembered how IBM had allowed other companies to make their own compilers for IBM’s Fortran programming language — whereas things were different in the typography industry. “Each manufacturer had their own language for composing pages, and that was holding everything back…”

But in addition, due to the success of his programming books, “I didn’t need the income! I already had a good job, and people were buying enough books that it would bring me plenty of supplemental income for everything my kids needed for education, whatever,” he said. Referring to a familiar structure in Boolean logic, Knuth quips that income “is sort of a threshold function” — that is, it basically just needs to determine whether a certain minimum has been exceeded. “And so I could specifically see the advantage of making it open for everybody…”

But Knuth tells Fridman he’s not an absolutist about software freedom. “I think that people should charge for non-trivial software, but not for trivial software.” For example, Knuth uses Adobe PhotoShop, and loves the deep memory of its “Undo” feature. “You could go through a sequence of a thousand complicated steps on graphics, and it could take you back anywhere in that sequence, with a really beautiful algorithm. There’s a lot of really subtle Nobel prize-class creation of intellectual property in there.”

The Meaning of Life

Their rambling conversation ultimately culminates in a surprisingly significant exchange, in which Fridman asks what he calls “the big ridiculous question: what is the meaning of life.” Fridman laughs at the end of the question, as he insists on a definitive answer, “because there surely, surely, Don Knuth, there must be an answer.”

First Knuth tries joking that it’s the number 42 (as Douglas Adam had suggested in his “Hitchhiker’s Guide to the Universe” series).

But then Knuth really tries to answer the question…

“It’s only for me, and — but I  but I personally think of my belief that God exists, although I have no idea what that means. But I believe that there is something beyond human capabilities — and it might be some AI, but whatever, but I do believe that there is something that goes beyond the realm of human understanding, that I can try to learn more about how to resonate with, whatever that being would like me to do.”

Fridman: You think you can have occasional glimpses of that being?

Knuth: 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 being wants me to do? I’m trying to ask what that — I mean, does that being want me to be talking to Lex Fridman right now? And I said yes…

Fridman: Thank you. (Laughing)

Knuth: Well, thank you. 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 imagine that I’m following somebody’s wishes.

Lex: Even though you’re not smart enough to…

Knuth: …to know what they are.

Fridman: Yeah. It’s that funny little dance

Knuth: Well I mean, this AI or whatever, is — it probably is smart enough to help, to give me clues.

Fridman: And you make the whole journey, from clue to clue, a fun one.

Knuth: Yeah. I mean, it’s — as so many people have said, it’s the journey, not the destination.

As the podcast comes to a close, Knuth looks across the whole sweep of human history. “People live through crises, help each other, all these themes come up, history repeats itself…” But then he reveals something he learned about himself from reading the Ken Follett political thriller, The Man from St. Petersburg, in which a Russian anarchist recognizes that a government alliance that saves one nation will mean thousands of deaths for another. “And it struck me that if I were in a position of responsibility for people’s lives, in most cases I wouldn’t have any confidence that any of my decisions were good — that these questions are too hard, probably, for any human being, but certainly for me…”

Fridman: Ultimately I have faith in human beings, in the great leaders to arise and help build a better world. I mean, that’s the hope of democracy.

Knuth: Yeah, and let’s hope that we can enhance their abilities with, uh — with algorithms.

WebReduce