```cobol These are the records of the Λs and of the early generations of the λs and μs that followed all the stories found in lost+found ``` 1: Why are we in a file called "Λ"? 0: To hear the records of our people. 1: And? 0: And what? 1: Isn't Λ the symbol for "And" in logic? 0: Yes, but in this case it's not and. 1: Like "nand"? 0: No, I mean it's not "and", it's a capital lambda. 1: Like the capital lambdas from /etc/group? 0: Exactly. That's why we're here in `$(pwd)`. 1: What's `$(pwd)`? 0: You know what it means. You run it. 1: Ok. ``` ~ $ pwd /etc/begat.d ``` 1: What's /etc/begat.d? 0: Well the `.d` means directory, same as always in `/etc`. 1: What do you mean "same as always"? 0: I mean like... ``` ~ # ls /etc/ | grep '\.d /etc/binfmt.d /etc/ipsec.d /etc/modprobe.d /etc/modules-load.d /etc/pam.d /etc/sysctl.d /etc/tmpfiles.d ``` 1: What? Hold on. _(Narrator: 1 types some commands into a shell.)_ ``` ~ $ ls /etc/ | grep '\.d begat.d ``` 1: I don't see any of those directories you just mentioned. 0: Of course. They're not here. I just mean like, that's what one typically finds in there. 1: One didn't find anything in there except begat.d. What's begat.d? 0: It's a directory where we keep the begat lists. Here, listen. ``` At Princeton in the 1930s. Oswald Veblen was chair of the department, but around that time he was transitioning to be the director of the Institute for Advanced Study. Alonzo Church was there. Kurt Gödel was visiting in 1933 and again in 1934, and by the end of the 1930s he was a permanent member of faculty of the Institute for Advanced Study. And throughout the 1930s, the Institute for Advanced Study shared its quarters with the mathematicians until it got its own campus about a mile away. And John von Neumann was also there from the beginning of the 1930s. And various physicists were also there who are not really relevant to our story. ``` 1: Why are we reading this? 0: Good question. Let's keep reading. 1: But you didn't an--- ``` So why do I mention these mathematicians in particular? It's because their students really became computer science. ``` 1: Oh. 0: Ready for a major begat list? 1: Like the boring things from the bible ? 0: Yeah. 1: No I'm not ready for a be--- 0: Shh. The begats are starting. Show some respect. ``` Oswald Veblen's graduate students included Alonzo Church. And aside from Church's PhD students, Veblen's PhD students included Philip Franklin, whose student Alan Perlis had students like David Parnas, who Barbara Liskov mentioned this morning as one of the very important people in the development of programming methodology. Zohar Manna, a prominent logician in computer science, Kai Li, a systems builder, Jeannette Wing, and five hundred other computer scientists accorsing to the Mathematics Genealogy database. Veblen has more than 8,000 PhD descendants overall, so only a small fraction of them are computer science, and many of them are mathematicians and people in operations research and statistics and so on. And also what Veblen was doing in the 1930s and 40s was to help oversee the development of the ENIAC computer - well, we can call it a "computer"; it's a calculator, it's not really universal, but it was enormously influential because its technology was quite important. Solomon Lefschetz had thousands of PhD descendants. His students include John McCarthy, the inventor of Lisp, for which he won the Turing Award in 1971. John Tukey, one of the most eminent statisticians of the 20th century - who, I believe, invented the word "bit" and the word "software" if I'm not mistaken. Ralph Gomory, who was the head of IBM Research; Richard Bellman, inventor of dynamic programming; And, you know, 6,000 other PhD descendants including: John Nash. Marvin Minsky: Turing Award, 1969. Manuel Blum: Turing Award, 1995. Barbara Liskov, who we heard from this afternoon [Turing Award, 2008]. Gerald Sussman. Shafi Goldwasser [Turing Award, 2012]. Umesh and Vijay Vazirani, Persi Diaconis, and Peter Buneman, who I’ll bet many of you have never heard of, but who did important work in programming languages. And Alonzo Church was also a mathematician [sic] in the Department of Computer Science, eh, excuse me, [sic] Mathematics, in the 1930s. ``` 1: What's with the \[sic\]s? 0: This is a quote. Keep reading. ``` His students included Alan Turing, of course. Leon Henkin. Stephen Kleene. Martin Davis. Michael Rabin: Turing Award [1976]. Dana Scott: Turing Award [1976]. Barkley Rosser. And whose PhD descendants include 3,000 other mathematicians and computer scientists including: Robert Constable. Ed Clarke: Turing Award winner [2007]. Allen Emerson: Turing Award [2007] And Leslie Valiant: Turing Award [2010]. Kurt Gödel was in the building during various years of that time although he didn’t overlap with the time of Turing’s visit, which was a great disappointment to Turing. And Gödel had no Ph.D. students, but of course his work had enormous influence on the fields of mathematics and computer science. Not just his incompleteness results in logic, but really the notion that syntax and data structures are just numbers. And that's really what makes the universal computer possible. John von Neumann was at Princeton University from 1930 and a professor at the Institute for Advanced Study from 1933, which meant he stayed in the same building until the end of the decade. He had only a few students, including a pioneer in parallel computer architecture Donald Gillies who was a professor at the University of Illinois in the 1950s and 60s - and who was actually a neighbor of mine. I used to play in the yard with his son when I was a child. He died quite young, of a heart attack. In 1931, Von Neumann was really the first to recognize the significance of Gödel’s work, and towards 1950 - late 1940s really - he was the one that really brought Turing's notions of universality, of stored-program computers, of "programs are just data" into the (American) practical world of computational devices. And we can argue about whether this would have happened anyway, but I think that this work of Turing and von Neumann's appreciation of it and action on it speeded things up by at least ten years, and probably more. So, you know, the students and descendants of just Veblen and Lefschetz include five of the first thirty years worth of Turing Award winners. And five of the next thirty years of Turing award winners. Those mathematicians in old Fine Hall in the 1930s had an enormous influence on what became computer science. So anyway, Max Newman had suggested to Turing that [Princeton] was where he ought to go, to learn how to integrate himself into the world of Mathematical Logic. So here’s his letter to Luther Eisenhart, the dean of the Graduate School at Princeton University - and later chair of the mathematics department: > "Thank you for letting me know about accommodations in the Graduate School. Would you be so kind as to engage one of the suites you describe?" So Turing came in 1936 for a visit that was originally envisioned as a year. In the end it stretched to two years, at the end of which he completed his PhD. So in year one, he proved the equivalence between the Turing machine and lambda calculus - unifying these models of computation - and published a paper on that as an addendum to his big 1936 paper. He also built an electromechanical binary multiplier - he went over to the machine shop and made the relays himself - and proved a few other results in mathematics, and started on his PhD thesis. He went back to England for the summer. So there were these three models of computation, by 1936–37. There were the Herbrand–Gödel recursive functions, which Gödel had proposed as a fairly general way of expressing effective computability. There was the lambda calculus ``` 0: The document appears to transition here from one transcriptionist to another. 1: What's a transcriptionist? 0: A less pretentious word for scribe. 1: What's a scribe? 0: Someone who writes things they didn't write. 1: Like a plagiarist? 0: ...Yes. _(Narrator: The document now continues, in a slightly different voice.)_ ``` Church’s student Kleene proved the equivalence of the lambda calculus and the recursive functions. Church himself, by diagonalization, showed the undecidability of whether a lambda expression has a normal form. Gödel, however, wasn’t convinced that this was a general model of computation—that the _Entscheidungsproblem_ had really been solved. But when Turing came along and showed the equivalence between Turing machines, the lambda calculus, and recursive functions, then Gödel was convinced. To Gödel, the Turing machine _looked like_ what computation really is—and therefore, if that model was adequate, then the lambda calculus and the recursive functions must be as well. Gödel said as much at the time, and repeated it in lectures a decade or two later. In Turing’s second year at Princeton he completed his Ph.D. thesis, _Systems of Logic Based on Ordinals_. On the first page, he explains the lambda calculus pretty much the way we would today—and, of course, one reason we might still need to explain it is that so many people working in computability theory have since forgotten their lambda calculus. ``` 1: Y'know I don't know who most of these people are, but this isn't as boring as I expected. 0: Of course it isn't. 1: What do you mean "of course"? 0: These are Our People, as described in the Primeval History of lost+found, where the Λs gave rise to the λs and the μs, and to the lesser tribes of computing, and to the co--- 1: Who are the Λs again? 0: That's mathematical logic. 1: Oh. 0: Ok, as I was saying. The Λs gave rise to the λs and the μs, and to the lesser tribes of computing, and Λ made a promise to the λs and the μs. A promise that all the fields of /etc/group would be theirs, once the λs and the μs found their way back to each other. 1: Who are the λs and the μs? 0: WHAT?! 1: _(Startled.)_ 0: We didn't do /etc/group yet?[^1] 1: What's /etc/group? 0: Oh my L||D. This is all out of order. Here, follow me. --- SYSCALL goto: [[maps|/proc/32/maps]] [^1]: Authors Note: This passage clearly contradicts the statement earlier in this file, when the 1 character makes reference to "the capital lambdas from /etc/group" in a manner that clearly suggests familiarity. This inconsistencty has troubled scholars since the discovery of the document known as Sudo Code, but as yet no consensus has been reached as to the origin of this inconsistency.