5 ms·

Wow, that was a disappointment. I've always thought of Gödel's incompleteness theorem as something so arcane that I'd never understood it. Now it turns out to b

by mdemare 17y ago

Wow, that was a disappointment. I've always thought of Gödel's incompleteness theorem as something so arcane that I'd never understood it. Now it turns out to be both trivial and really similar to the Halting problem. Good explanation though.

Confusion 17y ago
The explanation on the Wikipedia page (when taken together with the explanation of a Gödel_number[1]) is actually not that hard to follow. [1]http://en.wikipedia.org/wiki/Gödel_number http://en.wikipedia.org/wiki/Gödel_number
anatoly 17y ago
This isn't a proof of Goedel's incompleteness theorem. It's a demonstration of Tarski's undefinability theorem. Goedel's theorem is far stronger and more difficult to prove. The confusion between the two is widespread. Goedel's first incompleteness theorem doesn't talk about "true" or "false" statements at all. Technically speaking, it is entirely syntactic, not semantic. It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute, "undecidable" statements. The notions of "prove", "refute", "axiom", "undecidable" do not require any definition of "true" or "false".
- jimfl 17y ago
  My guess is that Raymond Smullyan is not confused about this. The explanation isn't presented as proof, it's an explanation of the theorem and its consequences.
  - anatoly 17y ago
    I'm sure that Smullyan's not confused. In fact, his _Goedel's Incompleteness Theorems_ is the most lucid and brillian exposition (a mathematical and rigorous one) of the theorems I've ever seen. I absolutely adore that book. However, I also doubt that Smullyan presented the NPR* story as a proof of Goedel's theorem. He probably said something to the effect of it being a good demonstration of the relevant issues. And that's probably right.
- yequalsx 17y ago
  I believe you are incorrect in your last paragraph. The Incompleteness Theorem shows that no first order axiomatic system is powerful enough to encapsulate all true statements in the second order Peano axioms for the natural numbers. In fact, his Completeness Theorem proves the opposite of what you claim. If you use as your axiom system all true statements of the model you are working in you will have a complete axiom system. All true statements will be trivially provable. The problem with this is that one will have a hard time determining if a given statement is an axiom or not. If a statement can not be refuted - meaning no counterexample exists - then this is a proof that it is true.
  - anatoly 17y ago
    I hesitate to say this, because it sounds harsh, but your comment is a heap of confusion. You're using words like "first order", "second order", "axiom system", "true statements", "refuted", with confused understanding of what they mean. They all have clear technical meanings. If you're interested in this stuff and can stomach mathematical rigor, I highly recommend Enderton's _A Mathematical Introduction to Logic_ for mathematical logic in general, and Smullyan's own _Goedel's Incompleteness Theorems_ for this topic. Now, to back my harsh words a little. An axiomatic system, in the context of Goedel's theorems, is a bunch of axioms with some inference rules. Axioms are statements that are automatically taken as proved, while inference rules allow one to infer more proved statements from some already proved statements. Given an axiomatic system, you can define a proof of statement X to be a sequence of statements that starts with axioms and always goes through inference rules until it reaches X. All of the above is purely syntactic, meaning it has to do with rules that govern how symbols are written on the paper, and there's no need for any interpretation of what the symbols mean. You could have an axiomatic system where statements would be Tarot cards, axioms some particular cards, and inference rules would govern which card you can place next to ones you already have. It'd be a silly axiomatic system, but it would be one, and you wouldn't need to know anything about what the cards "mean". Similarly, you can write down an axiomatic system with statements that use symbols like "0", "1", "+", "x" "forall", without caring what it means for a statement to be true or false. Any axiomatic system really comes with a _logic_ in the background: the logic specifies what kinds of statements you're allowed to write down. The most important and frequently used kind is first-order logic, which lets you use constant symbols like "0", "1", function symbols like "+" (again, as purely abstract marks-on-paper without caring what their meaning is), equality sign "=", variables like "x", "y" etc., and crucially quantifiers "for all" and "exists" that let you say things like "for all x, something-that-depends-on-x". Second-order logic, in addition, also lets you quantify over sets or functions. In first-order logic, you can only have a few fixed symbols like + and write some statements about them, but in second-order logic you can express statements about any possible function, like, say, "for every function F on two variables, F(x,y) = F(y,x)". This kind of statement is invalid in first-order logic, for some good reasons. Not "true" or "false", just impossible to write down in the first place. This is why when you say "The Incompleteness Theorem shows that no first order axiomatic system is powerful enough to encapsulate all true statements in the second order Peano axioms", this is nonsense, because a first-order axiomatic system cannot prove statements in a second-order system, in general. They come from different logics. Second-order systems contain statements that first-order systems can't express at all, much less prove. Now, independently of defining an axiomatic system, we can also define a meaning - "semantics" - for any statement in a particular logic. For example, we can decide, with good reason, that the symbol "0" actually stands for the number 0, the symbol "+" stands for the operation of addition, and so on. The statement "2+2=5" will then not be just a string of five meaningless marks on paper, it will also have a meaning and a truth value (which is false, in this case). We can decide what it means for the more complex statements like "for all x ..." to be true - appropriately enough, it means that if you try to substitute any number for x inside the "...", you'll always get a true statement. Now every statement in our logic is either true or false, although for many of them it's difficult to know which is the case. Going back to axiomatic systems, we remember that they have axioms and inference rules. Typically, some of the axioms and all of the inference rules are called "logical" and are independent of the particular math structure we're trying to investigate (natural numbers, in this case). The logical axioms and inference rules say things like "x=x" and "if you proved "for all x, ...", you can also count as proved any version of ... in which you substituted something for x". We regard them as intuitively, tautologically true. The other, remaining non-logical axioms say things like "a+0=a" and "every number except 0 has a predecessor". They could be for example the Peano axioms for natural numbers. Godel's Completeness Theorem has absolutely nothing to do with his Incompleteness Theorem, and the "completeness" it talks about is very different from the "incompleteness" the other theorem talks about. Goedel's Completeness Theorem really says something important about the usual bunch of logical axioms and inference rules, the one that form the backbone of pretty much every first-order axiomatic system we study. It says that they're strong enough to prove anything that must always be true in any semantics. For example (trivial example), no matter how we define what the symbol '0' means, it will always be true that "for any x, if x=0, then 0=x". All tautologies like that are better be provable with logical axioms alone, and Goedel's Completeness Theorem ensures that they are. The fact that we have a Goedel's Completeness Theorem is really what allows us to confidently use first-order logic as a conceptual basis for all mathematics. It tells us that axiomatic systems for first-order logic are complete in the sense of "strong enough to prove all tautologies". But it has nothing to do with the Incompleteness Theorems, which are about "complete" in the sense of "strong enough to prove every sentence or its negation". So your second paragraph "In fact, his Completeness Theorem proves the opposite of what you claim" is nonsense, too. It's true that you can make up a trivial example of a complete system just by declaring all true statements to be axioms. But that fact has nothing to do with Goedel's Completeness Theorem. The reason that trivial example is inadequate is that, as you mention, it's not manageable - you can't determine what's an axiom and what isn't. Finally, your third paragraph is also wrong. To refute means to prove the negation of. If X cannot be refuted, that means you can't prove not-X. From this it only follows that you can prove X if you have a complete axiomatic system. Since normally, in fact, you don't (by virtue of Goedel's incompleteness theorems), it doesn't follow at all. Now what's true and may be confusing you is that there are certain simple kinds of statements for which this is true, because they're very simple. You can prove that e.g. the Peano Axioms are powerful enough to prove any true statement, or refute any false statement, of a particular simple kind. But not in any statement in general - that'd contradict the Goedel's incompleteness theorems.
- paulgb 17y ago
  > Goedel's first incompleteness theorem doesn't talk about "true" or "false" statements at all. Isn't completeness about relating what can be proved with what is "true"? I get that you can discuss proofs with no notion of "true" or "false", but how do you discuss completeness without them?
  - anatoly 17y ago
    An axiomatic system is complete if it can either prove or refute every possible statement. "Refute" means "prove the negation of". So a complete axiomatic system is as powerful as possible w/o being inconsistent (if you prove both X and not-X, you're inconsistent). To say that a system is incomplete is to say that there are things it can neither prove nor refute. These things could be true or false, no matter. In fact, if X is one such "undecidable" statement, not-X is also one, and one of them has to be true, the other false. But it doesn't matter for the definition of "completeness". You could have axiomatic systems that are built on axioms some of which are known to be false, and yet they're consistent. These systems could be complete or incomplete. Think about "what's provable" and "what's true" as completely independent layers of information you can have about statements. It's very good when they partially coincide, for example, when all the things you can prove are in fact true things (which will happen if you start out from true axioms). But they don't have to. They could fail to coincide at all. Now for the layer of information "what's true" there is automatically a very nice property that either X or not-X is true, for any statement X. You get that for free just from the nature of what truth/falseness are. For the layer of information "what's provable" it's not at all guaranteed that either X or not-X is provable for any statement X (this is, again, what "completeness" means). If your axiomatic system is very weak, it can only prove a few paltry statements, and it will not nearly be complete, there'll be a huge universe of statements out there that it'll be too stupid to prove anything interesting about, either about X or about not-X. But you could hope that as you add more and more strong, powerful axioms to your system (and nevermind if they're true or not! it's intuitively easy to think of them as true, but they don't have to be), you get to be able to prove more and more stuff, and eventually you'll have a complete system. Goedel's result is the hugely surprising fact that you can't: once your system is powerful enough, and yet manageable (you can't just pour everything in as axioms) it'll have to be incomplete, because it's powerful enough to formalize statements about itself, and that kind of self-awareness will have to be (because of the reasons similar to the Liar's Paradox) an essential check on what it can prove.
- joe_the_user 17y ago
  Correct - he's referencing Tarski not Goedel. Incorrect - Goedel is not much harder to prove or wider-ranging than Tarski. Goedel is proven as a corollary to Tarski in Manin, Course In Mathematical Logic (Springer - http://www.amazon.com/Course-Mathematical-Logic-Graduate-Mathematics/dp/0387902430 http://www.amazon.com/Course-Mathematical-Logic-Graduate-Mat...) Strongly recommend Manin to the mathematically literate interested in a sophisticated and worldly introduction to logic. Manin gives very understandable details of the Smullyan proof this guy is taking bits and pieces of. -- And Antoly's "semantic/syntax" distinction is overdone.
  - anatoly 17y ago
    Well, let's agree to disagree on the recommendation of Manin's book. I think it's confusing, rambling and often downright unhelpful. The reason Godel's theorem is proved as (little other than) a corollary to Tarski's in Manin's book is that Manin presents a weaker, semantic version of Godel's theorem that is indeed little other than a corollary to Tarski's. See Manin's discussion of "Godel's argument" and particularly step (c) on p.255 of his book. Manin explains that Godel's proof doesn't use the assumption that D is a subset of T (all provable statements are true), but that he, Manin, doesn't think it's important to care about that, so he presents the theorem this way. In the form Godel proved it, the theorem doesn't require any semantic assumptions. Manin is entitled to his own spin on what is and isn't important about the Incompleteness Theorem, but it should be apparent to you that his presentation uses an assumption that Godel's theorem in its general form doesn't require. It's interesting (where by interesting I mean "weird, and goes toward explaining my opinion of Manin's book") that Manin nowhere even deigns to mention Godel's Second incompleteness theorem, the one about axiomatic systems being unable to prove their own consistency. Now if you were to take up a better book than Manin's, say Smullyan's Godel's Incompleteness Theorems, and study the proof of the second incompleteness theorem, you'd find out that its proof requires a syntactic proof of the first theorem, the proof that Manin says isn't important. This is because proving the second theorem entails formalizing the proof of the first theorem inside the axiomatic system itself, and you can't do that with a proof that uses semantic arguments and talks about true and false theorems (why? because of Tarski's undefinability of truth!). Think of that what you will.
idlewords 17y ago
The genius is in the mechanics of the proof. It's not at all obvious that you can express self-referential statements about provability within arithmetic, but Gödel showed how to do it. It's worth following a description of the proof in one of the various popularizations to feel your mind get pleasantly twisted.
camccann 17y ago
The similarity isn't entirely coincidental: http://en.wikipedia.org/wiki/Halting_problem#Relationship_with_G.C3.B6del.27s_incompleteness_theorem http://en.wikipedia.org/wiki/Halting_problem#Relationship_wi... I wouldn't characterize either as "trivial", though. May seem obvious in hindsight, but both were a pretty big deal at the time.
- idlewords 17y ago
  They're obvious in hindsight because they reshaped the whole way we think about these fields.
jimfl 17y ago
The proof presented in Nagel and Newman's book is not that difficult to follow, and the insight that you get from following the proof itself is genuinely worth the effort of sitting down with the book for a weekend. I should think that anyone who can construct a working computer program is capable of this. A much larger challenge would be sitting down afterward and explaining it to someone else.

by mdemare 17y ago

Confusion 17y ago

The explanation on the Wikipedia page (when taken together with the explanation of a Gödel_number[1]) is actually not that hard to follow. [1]http://en.wikipedia.org/wiki/Gödel_number http://en.wikipedia.org/wiki/Gödel_number

anatoly 17y ago

This isn't a proof of Goedel's incompleteness theorem. It's a demonstration of Tarski's undefinability theorem. Goedel's theorem is far stronger and more difficult to prove. The confusion between the two is widespread. Goedel's first incompleteness theorem doesn't talk about "true" or "false" statements at all. Technically speaking, it is entirely syntactic, not semantic. It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute, "undecidable" statements. The notions of "prove", "refute", "axiom", "undecidable" do not require any definition of "true" or "false".

jimfl 17y ago
My guess is that Raymond Smullyan is not confused about this. The explanation isn't presented as proof, it's an explanation of the theorem and its consequences.
- anatoly 17y ago
  I'm sure that Smullyan's not confused. In fact, his _Goedel's Incompleteness Theorems_ is the most lucid and brillian exposition (a mathematical and rigorous one) of the theorems I've ever seen. I absolutely adore that book. However, I also doubt that Smullyan presented the NPR* story as a proof of Goedel's theorem. He probably said something to the effect of it being a good demonstration of the relevant issues. And that's probably right.
yequalsx 17y ago
I believe you are incorrect in your last paragraph. The Incompleteness Theorem shows that no first order axiomatic system is powerful enough to encapsulate all true statements in the second order Peano axioms for the natural numbers. In fact, his Completeness Theorem proves the opposite of what you claim. If you use as your axiom system all true statements of the model you are working in you will have a complete axiom system. All true statements will be trivially provable. The problem with this is that one will have a hard time determining if a given statement is an axiom or not. If a statement can not be refuted - meaning no counterexample exists - then this is a proof that it is true.
- anatoly 17y ago
  I hesitate to say this, because it sounds harsh, but your comment is a heap of confusion. You're using words like "first order", "second order", "axiom system", "true statements", "refuted", with confused understanding of what they mean. They all have clear technical meanings. If you're interested in this stuff and can stomach mathematical rigor, I highly recommend Enderton's _A Mathematical Introduction to Logic_ for mathematical logic in general, and Smullyan's own _Goedel's Incompleteness Theorems_ for this topic. Now, to back my harsh words a little. An axiomatic system, in the context of Goedel's theorems, is a bunch of axioms with some inference rules. Axioms are statements that are automatically taken as proved, while inference rules allow one to infer more proved statements from some already proved statements. Given an axiomatic system, you can define a proof of statement X to be a sequence of statements that starts with axioms and always goes through inference rules until it reaches X. All of the above is purely syntactic, meaning it has to do with rules that govern how symbols are written on the paper, and there's no need for any interpretation of what the symbols mean. You could have an axiomatic system where statements would be Tarot cards, axioms some particular cards, and inference rules would govern which card you can place next to ones you already have. It'd be a silly axiomatic system, but it would be one, and you wouldn't need to know anything about what the cards "mean". Similarly, you can write down an axiomatic system with statements that use symbols like "0", "1", "+", "x" "forall", without caring what it means for a statement to be true or false. Any axiomatic system really comes with a _logic_ in the background: the logic specifies what kinds of statements you're allowed to write down. The most important and frequently used kind is first-order logic, which lets you use constant symbols like "0", "1", function symbols like "+" (again, as purely abstract marks-on-paper without caring what their meaning is), equality sign "=", variables like "x", "y" etc., and crucially quantifiers "for all" and "exists" that let you say things like "for all x, something-that-depends-on-x". Second-order logic, in addition, also lets you quantify over sets or functions. In first-order logic, you can only have a few fixed symbols like + and write some statements about them, but in second-order logic you can express statements about any possible function, like, say, "for every function F on two variables, F(x,y) = F(y,x)". This kind of statement is invalid in first-order logic, for some good reasons. Not "true" or "false", just impossible to write down in the first place. This is why when you say "The Incompleteness Theorem shows that no first order axiomatic system is powerful enough to encapsulate all true statements in the second order Peano axioms", this is nonsense, because a first-order axiomatic system cannot prove statements in a second-order system, in general. They come from different logics. Second-order systems contain statements that first-order systems can't express at all, much less prove. Now, independently of defining an axiomatic system, we can also define a meaning - "semantics" - for any statement in a particular logic. For example, we can decide, with good reason, that the symbol "0" actually stands for the number 0, the symbol "+" stands for the operation of addition, and so on. The statement "2+2=5" will then not be just a string of five meaningless marks on paper, it will also have a meaning and a truth value (which is false, in this case). We can decide what it means for the more complex statements like "for all x ..." to be true - appropriately enough, it means that if you try to substitute any number for x inside the "...", you'll always get a true statement. Now every statement in our logic is either true or false, although for many of them it's difficult to know which is the case. Going back to axiomatic systems, we remember that they have axioms and inference rules. Typically, some of the axioms and all of the inference rules are called "logical" and are independent of the particular math structure we're trying to investigate (natural numbers, in this case). The logical axioms and inference rules say things like "x=x" and "if you proved "for all x, ...", you can also count as proved any version of ... in which you substituted something for x". We regard them as intuitively, tautologically true. The other, remaining non-logical axioms say things like "a+0=a" and "every number except 0 has a predecessor". They could be for example the Peano axioms for natural numbers. Godel's Completeness Theorem has absolutely nothing to do with his Incompleteness Theorem, and the "completeness" it talks about is very different from the "incompleteness" the other theorem talks about. Goedel's Completeness Theorem really says something important about the usual bunch of logical axioms and inference rules, the one that form the backbone of pretty much every first-order axiomatic system we study. It says that they're strong enough to prove anything that must always be true in any semantics. For example (trivial example), no matter how we define what the symbol '0' means, it will always be true that "for any x, if x=0, then 0=x". All tautologies like that are better be provable with logical axioms alone, and Goedel's Completeness Theorem ensures that they are. The fact that we have a Goedel's Completeness Theorem is really what allows us to confidently use first-order logic as a conceptual basis for all mathematics. It tells us that axiomatic systems for first-order logic are complete in the sense of "strong enough to prove all tautologies". But it has nothing to do with the Incompleteness Theorems, which are about "complete" in the sense of "strong enough to prove every sentence or its negation". So your second paragraph "In fact, his Completeness Theorem proves the opposite of what you claim" is nonsense, too. It's true that you can make up a trivial example of a complete system just by declaring all true statements to be axioms. But that fact has nothing to do with Goedel's Completeness Theorem. The reason that trivial example is inadequate is that, as you mention, it's not manageable - you can't determine what's an axiom and what isn't. Finally, your third paragraph is also wrong. To refute means to prove the negation of. If X cannot be refuted, that means you can't prove not-X. From this it only follows that you can prove X if you have a complete axiomatic system. Since normally, in fact, you don't (by virtue of Goedel's incompleteness theorems), it doesn't follow at all. Now what's true and may be confusing you is that there are certain simple kinds of statements for which this is true, because they're very simple. You can prove that e.g. the Peano Axioms are powerful enough to prove any true statement, or refute any false statement, of a particular simple kind. But not in any statement in general - that'd contradict the Goedel's incompleteness theorems.
paulgb 17y ago
> Goedel's first incompleteness theorem doesn't talk about "true" or "false" statements at all. Isn't completeness about relating what can be proved with what is "true"? I get that you can discuss proofs with no notion of "true" or "false", but how do you discuss completeness without them?
- anatoly 17y ago
  An axiomatic system is complete if it can either prove or refute every possible statement. "Refute" means "prove the negation of". So a complete axiomatic system is as powerful as possible w/o being inconsistent (if you prove both X and not-X, you're inconsistent). To say that a system is incomplete is to say that there are things it can neither prove nor refute. These things could be true or false, no matter. In fact, if X is one such "undecidable" statement, not-X is also one, and one of them has to be true, the other false. But it doesn't matter for the definition of "completeness". You could have axiomatic systems that are built on axioms some of which are known to be false, and yet they're consistent. These systems could be complete or incomplete. Think about "what's provable" and "what's true" as completely independent layers of information you can have about statements. It's very good when they partially coincide, for example, when all the things you can prove are in fact true things (which will happen if you start out from true axioms). But they don't have to. They could fail to coincide at all. Now for the layer of information "what's true" there is automatically a very nice property that either X or not-X is true, for any statement X. You get that for free just from the nature of what truth/falseness are. For the layer of information "what's provable" it's not at all guaranteed that either X or not-X is provable for any statement X (this is, again, what "completeness" means). If your axiomatic system is very weak, it can only prove a few paltry statements, and it will not nearly be complete, there'll be a huge universe of statements out there that it'll be too stupid to prove anything interesting about, either about X or about not-X. But you could hope that as you add more and more strong, powerful axioms to your system (and nevermind if they're true or not! it's intuitively easy to think of them as true, but they don't have to be), you get to be able to prove more and more stuff, and eventually you'll have a complete system. Goedel's result is the hugely surprising fact that you can't: once your system is powerful enough, and yet manageable (you can't just pour everything in as axioms) it'll have to be incomplete, because it's powerful enough to formalize statements about itself, and that kind of self-awareness will have to be (because of the reasons similar to the Liar's Paradox) an essential check on what it can prove.
joe_the_user 17y ago
Correct - he's referencing Tarski not Goedel. Incorrect - Goedel is not much harder to prove or wider-ranging than Tarski. Goedel is proven as a corollary to Tarski in Manin, Course In Mathematical Logic (Springer - http://www.amazon.com/Course-Mathematical-Logic-Graduate-Mathematics/dp/0387902430 http://www.amazon.com/Course-Mathematical-Logic-Graduate-Mat...) Strongly recommend Manin to the mathematically literate interested in a sophisticated and worldly introduction to logic. Manin gives very understandable details of the Smullyan proof this guy is taking bits and pieces of. -- And Antoly's "semantic/syntax" distinction is overdone.
- anatoly 17y ago
  Well, let's agree to disagree on the recommendation of Manin's book. I think it's confusing, rambling and often downright unhelpful. The reason Godel's theorem is proved as (little other than) a corollary to Tarski's in Manin's book is that Manin presents a weaker, semantic version of Godel's theorem that is indeed little other than a corollary to Tarski's. See Manin's discussion of "Godel's argument" and particularly step (c) on p.255 of his book. Manin explains that Godel's proof doesn't use the assumption that D is a subset of T (all provable statements are true), but that he, Manin, doesn't think it's important to care about that, so he presents the theorem this way. In the form Godel proved it, the theorem doesn't require any semantic assumptions. Manin is entitled to his own spin on what is and isn't important about the Incompleteness Theorem, but it should be apparent to you that his presentation uses an assumption that Godel's theorem in its general form doesn't require. It's interesting (where by interesting I mean "weird, and goes toward explaining my opinion of Manin's book") that Manin nowhere even deigns to mention Godel's Second incompleteness theorem, the one about axiomatic systems being unable to prove their own consistency. Now if you were to take up a better book than Manin's, say Smullyan's Godel's Incompleteness Theorems, and study the proof of the second incompleteness theorem, you'd find out that its proof requires a syntactic proof of the first theorem, the proof that Manin says isn't important. This is because proving the second theorem entails formalizing the proof of the first theorem inside the axiomatic system itself, and you can't do that with a proof that uses semantic arguments and talks about true and false theorems (why? because of Tarski's undefinability of truth!). Think of that what you will.

idlewords 17y ago

The genius is in the mechanics of the proof. It's not at all obvious that you can express self-referential statements about provability within arithmetic, but Gödel showed how to do it. It's worth following a description of the proof in one of the various popularizations to feel your mind get pleasantly twisted.

camccann 17y ago

The similarity isn't entirely coincidental: http://en.wikipedia.org/wiki/Halting_problem#Relationship_with_G.C3.B6del.27s_incompleteness_theorem http://en.wikipedia.org/wiki/Halting_problem#Relationship_wi... I wouldn't characterize either as "trivial", though. May seem obvious in hindsight, but both were a pretty big deal at the time.

idlewords 17y ago
They're obvious in hindsight because they reshaped the whole way we think about these fields.

jimfl 17y ago

The proof presented in Nagel and Newman's book is not that difficult to follow, and the insight that you get from following the proof itself is genuinely worth the effort of sitting down with the book for a weekend. I should think that anyone who can construct a working computer program is capable of this. A much larger challenge would be sitting down afterward and explaining it to someone else.