I can recommend reading Logicomix, a graphic novel about Bertrand Russell and his work in mathematics. There are lots of other people making appearances, for instance Gödel who makes quite the splash (as one can imagine). I read it a couple of weeks ago and thoroughly enjoyed it.
So great to see an article about Godel incompleteness in the new yorker. I think in general Godel incompleteness and Turing incompleteness should get more press. Chaitin has written some good books about this, but there needs to be more. There are these fundamental limits to knowledge and this is an important fact that people should know about.
> “There is more to truth than can be caught by proof.”
Yup. These articles much more than their focus on Godel and his fan club would do us all a favor to focus on -
How do people day to day deal with ambiguity, where the truth is uncertain or unknowable?
The default action always is - they choose the truth they want to be true. And this has long term consequences. They should develop self awareness that it is a chosen truth and feel a sense of responsibility for its consequences.
The example I given students when I teach where things worked out well, is Thomas Jefferson's - "We hold these truths to be self-evident, that all men are created equal".
We still know 240 years later there is nothing self-evident or truthful about equality. We don't know if it will ever be.
Jefferson knew that. Yet he made a choice about what he wanted the truth to be. We face similar choices everyday in life. Choose well.
Although it's nice to see Gödel show up in the popular press, I didn't get what the point of this was. His Incompleteness paper is not that impenetrable. Sometimes it does pay to at least look at primary sources in addition to listening to others' efforts to summarize or dissect. I don't think the author of this article made much of an effort to understand what or who she was writing about. Sad, really, given Gödel's importance in understanding the beginnings of a science of computation (easily one of the most significant achievements in human history), where there is already too much myth-making and mischaracterizations.
Thank you for your Godel notes below! I'm going to check out the links.
I have the Brooklyn Institute for Social Research in my Facebook feed and they're mentioned in the article. I think the point of the article is to mark the work the teacher of the Godel class at the Institute did to digest the material for the students of his/her class.
The preliminary milestone of digestion of a subject for teaching is a syllabus, also mentioned in the article.
I agree that the article was a little thin (to be honest, it's shorter than most articles I bother to read, let alone repost) & that it's misleading in suggesting that incompleteness is difficult to understand.
That said, I'm very glad that the idea is finally popping up in the popular press: incompleteness, like special relativity & quantum superposition, is about a hundred years old & many people still don't have sufficient familiarity with it to understand the way that the philosophy of the field in appeared in was impacted. Where relativity meant that time was mutable & superposition meant that randomness was inescapable (in other words, breaking the "Newton's Calculator" model of physics), incompleteness means that self-description breeds undecidability & that the relatively common idea of an ultimate descriptive language is inherently doomed. These are important facts from a philosophical standpoint, even if they rarely directly interact with things that 'normal' people are trying to do (although 'normal' people bump up indirectly against relativity & incompleteness daily, in the form of (for instance) GPS devices).
Even without trying to follow the proof proper, the sub-sections of the second part are interesting on their own, particularly Gödel numbering and primitive recursive functions. Here is another translation that covers just this part:
It's true that if you know nothing about formal logic, history of metamathematics, and decidability, then it's going to be particularly hard going, but there are a lot of accessible resources for each of those topics and the paper is well structured (meaning you can concentrate on the pieces).
The encoding that Gödel used for formulas should be fascinating for anyone familiar with Turing work on decidability as well as how computers work generally. Primitive recursive functions don't handle computation generally, but seem to be a first step in understanding what it means. Anyone familiar with Alonzo Church, lambda calculus, functional programming, McCarthy's first paper on Lisp would probably be interested in this bit.
Of course, Gödel's result on formal systems shattered the idea of an axiomatic basis for mathematics, but I personally think its greater long-term impact is helping to usher in computation. It's worth recognizing both.
>I asked my classmates whether they had heard of the sci-fi writer Rudy Rucker’s book
Rudy Rucker was/is also one of the most prominent cellular automata researchers of recent history. I can highly recommend "Cellab" [1], which I first encountered as CA Lab. You may need to install a virtual machine to get it running properly [2].
[2]: [In the spring of 2010, the Cellab software became semi-obsolete---in that it won't run under Windows 7. The "good" news is that Windows 7 can in fact run a virtual machine in Windows XP mode, if you download and install some free Microsoft virtual XP software. I tried this just now, and it works pretty well. You get a little window or a full screen which is an XP desktop. And CELLAB runs fine in the XP window—to make it easy to find your files, you drag the CELLAB folder from your normal C: drive (if that’s where it lives) onto the desktop of the XP Virtual machine window.]
Probably worth mentioning that Russell's opposition to recursion which lead to him formulating "his" paradox offered type theory as a solution. Type theory also has quite the impact on computer science.
I think a more precise wording than "recursive" would be objecting to impredicative definitions; those which quantify over (something containing or pertaining to) themselves.
For example, it's fine to define an arithmetic function recursively; it's not so fine to define a set based on whether it contains itself.
