## Gödel's Paper ### Or: 17 Gen r ### Or: 17 Gen 二 ### Or: 一七 Gen 二 ### Or: Yi qi Gen 二 ### Or: 一起 Gen 2 ### Or: Together Gentoo ### Or: Our Protagonists, and Distribution of Compiled Sources 0: Ok so Gödel's paper opens like this. ![[godel-collected-works-098.png]] ## Gödel goes to Church > TODO: Godel's reaction to Church's definition. 0: Ok last we left off, Gödel arrived on the scene. 1: What scene? 0: Church. 1: What? 0: Princeton. He goes to visit Church and Kleene. > Steve Kleene: Then Gödel arrived on the scene and there must have been discussions between Church and Gödel, and I don't know how ready Gödel was to embrace the thesis that this was all effectively calculable functions but Church of course is the one that certainly came out explicitly with this. > Steve Kleene: Then Gödel arrived in the Fall or Spring of the year 1933-34. Gödel was giving his lectures. Gödel had this notion of General Recursive Functions, and the question came up, y'know, well, does this embrace all effectively calculable functions and is it equivalent to lambda definability. > Steve Kleene: I left Princeton in June of 1935, and of course we already had Church's Thesis in, it must have been the late spring of '34. That's when Gödel was talking about his General Recursive Functions. > Steve Kleene: You don't happen to have a copy of Introduction to Metamathematics do you? > Steve Kleene: Well, what Herbrand did in General Recursive Functions as presented by Gödel giving credit for ideas of Herbrand, is something I understand more than what Herbrand published. It was a little note of Herbrand's or a little, y'know, it was something short but whether it was a short note or just a short piece on the end of something else. > > _(Kleene thumbs through his book Introduction to Metamathematics: The "frighteningly technical" book mentioned earlier.)_ > > Gerald Sacks: It's hard to remember everything in that book. > > _(Everyone laughs.)_ > > Some Famous Logician: I knew it for a week or two when I had to take my exams. But I must say a few have slipped my mind. > > Steve Kleene: It helps to have written it. > > C. C. Chang: I don't even remember what's in _Model Theory_ anymore. 1: What's _Model Theory_? 0: A part of foundations of mathematics. But in this case it's a book that guy wrote. --- 0: Ok so, we're not here to talk about Gödel's incompleteness theorem. But I'm in some ways his incompleteness theorems were the spark for the story of computation that came after. After all, if mathematics is more limited than we thought, suddenly it seems a lot more feasible to capture "any possible computation" in a formal definition. 1: Not following the logic there. 0: To be fair, neither did Church or Gödel, at the time. Most of the main players involved in the early theory of "effective calculability" didn't actually think that they were capturing "all possible computations" in their definitions. But still, it's probably not an accident that all 3 of our definitions of "computation" appeared within 5 years of Gödel's incompleteness theorems. 1: Still not seeing how the two are related. 0: Well in the years from 1900 to 1931, and in some sense for the entire history of mathematics, it didn't feel plausible to give a definition that might hope to capture all possible computation. Before Gödel, there was a general informal idea that mathematics could do anything. That the power of thought and proof was unlimited, given sufficient cleverness. But if it turns out that mathematics is limited somehow, then it seems a bit less impossible to capture the essence of what it is. 1: Can you explain more simply? 0: Would you rather try to capture a limited god or an unlimited one? 1: Got it. You always find a way to bring it back to bib--- 0: So once you have the incompleteness theorems, the idea that "the space of all possible computations" might be within the reach of a formal definition is a bit more plausible than it might have been before. In that sense, we may owe the origins of modern computing to the discovery of incompleteness. 1: Awesome. Let's learn about incompleteness! 0: No. We're here to talk about his definition of computation. 1: Then why are you talking about incompl--- 0: Because without a bit of incompleteness, any discussion of Gödel's definition of computation would be incomplete. 1: What was his definition of computation? 0: The General Recursive functions. Also known as the "Mu recursive functions," due to the existence of this funny operator called μ that shows up in his definition and makes it Turing complete. 1: Did he know it was Turing complete? 0: Not at the time. This is 5 years before Turing. But eventually Turing would be the one who'd convince Gödel that these three definitions of computation were broad enough to plausibly include "Everything possible thing that can be done." 1: Everything that can be done? 0: At least in computation. So yes, Gödel's definition was "Turing complete" in that sense. 1: So what was his definition? 0: It's not interesting to just say what his definition was. To understand what he was thinking when he came up with his definition, we have to get inside his head a little. 1: Isn't he the guy that was so paranoid he starved himself to death? 0: That was like 40 years later, but yeah. Why? 1: I'm not sure I want to get inside his head. It sounds scary in there. 0: Good point. I wouldn't want to go through what Gödel went through either. But he's part of our trinity, the trinity of /dev/zero, and as a member of /dev/zero, he's the first developer in history. 1: Don't you mean the zeroth developer? 0: Of course. And zero comes first. But one is #1, ordinally speaking, and seeing as 0 won't always be here to explain things to 1, it's an important part of 1s education as a dev to understand /dev/zero, after all, he's the first. 1: You're so weird. 0: Agree to disagree. 0'm as n||mal as the come. 1're the weird 1 if you ask me. 1: Ok sure we're both a little weird. Can you go back to talking normal? 0: Well 0'd say talking n||mal isn't in our nature. After all, 1 thing we both are is developers. And as developers, the most normal behavior of all is to write in strange languages no one speaks. And Gödel was very much one of us in that regard. Plus I don't think Gödel's unique among our people in being a bit o{dd,ff} the head. But it's hard to know what he was thinking just based on reading books. By all accounts, he was extremely curt, Gödel. 1: Wasn't it spelled Kurt? 0: Of course. But also curt. --- curt. (adjective). /kərt/ 1. using or expressed in few words. "his reply was curt" --- 0: Gödel was very curt - brief, terse, and didn't talk much. Nevertheless, as devs, it's our job to learn our history. And that means getting inside Kurt's head to understand /dev/zero, the One$^{th}$ developer, all three of Him, mysteries and all, whether or not it was always pleasant in his head. 1: You should work at a carnival or something. 0: Thank you. 1: That wasn't a compliment. 0: Agree to disagree. Anyways, it's our job in this file to get inside Gödel's head. And to do that, we need to understand what he was trying to do when he gave his definition of computation. 1: What was he trying to do? 0: Ok so Godel's original paper doesn't say anything like "Here's what I think all the computable functions are." He literally just introduces his definition of computation as a side remark. ![[godel-collected-works-109.png]] ![[godel-collected-works-111.png]] 0: See that? He didn't even realize he was doing it. 1: Doing what? 0: Defining all of computation! 1: Isn't that like... obviously all of computation? 0: Apparently not. At least it wasn't clear at the time. All he knew what that these functions were enough for what he needed to do in the paper. Here look: ![[godel-collected-works-117.png]] goto: [[lost+found/4/3|/lost+found/4/3]]