HN Books @HNBooksMonth

Does either (claims to) explain the proof itself in it's full glory? I had read "Godel's Proof" by Ernest Nagel et al [1] and it fell short.

[1] https://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/08147583...

⬐ denton-scratch

I'm not sure about "claims to". I have misplaced my copy of the Penrose book. Hofstadter's book is humorous, despite its weight. It doesn't purport to be a canonical explanation of the theorem.

Both books are ultimately focused on the nature of consciousness, although from quite different perspectives. In both cases, the theorem is presented as one element of an argument.

It's interesting that two sophisticated writers with wildly different opinions about consciousness have both leaned on Gödel to back their arguments. There's nothing in the theorem that shouts "This is about consciousness!"

⬐ alok-g

Penrose's argument linking consciousness to Godel's theorems makes little sense to me.

https://en.m.wikipedia.org/wiki/Penrose–Lucas_argument

Thanks for answering my question. I am guessing that neither book would explaim the proof in detail.

Does it explain the proof itself in it's full glory? I had read "Godel's Proof" by Ernest Nagel et al [1] and it fell short.

[1] https://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/08147583...

⬐ truth_

You mention in another comment that it skipped some part of the proof and that you were disappointed. Do you still recommend the book?

⬐ alok-g

If you are mathematically-inclined and are looking forward to understanding the proof itself, the book won't do much better than the following video [1] taken from a comment in this thread [2]. Disappointed, I attempted to read Godel's original papers. That has it's own challenge as it refers to Principia Mathematica. I started reading that. Only to fimd that it uses older mathematical notation not in use today.

In short, I haven't found any source that explains the proof in reasonable detail.

If you want to understand the thought process of axiomatic reasoning (and with less extrapolations to consciousness et al) it is a good book.

Note: I had read a long time back, so do not remember the details.

[1] https://www.youtube.com/watch?v=HeQX2HjkcNo

[2] https://news.ycombinator.com/user?id=littlecranky67

There is a little great book called "Godel's proof" by Nagel and Newman[1]. And definitely requires some focus but readable nevertheless.

[1] https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081...

Edit : removed a line

⬐ ruste

I second this! I spent a few days of summer vacation in highschool slowly working my way through this and it was mind expanding.

⬐ alok-g

A good book as such. However, whereas the authors claim that they outline the proof in chapter 6, that chapter fell short of it with key aspects of the proof missing. Overall, I was disappointed.

⬐ rottc0dd

There is a great book called "Godel's proof" by Nagel and Newman[1]. And definitely requires some focus but readable nevertheless.

[1] https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081...

Edit : removed a line

For a detailed perspective on how the proof works, I highly recommend Ernest Nagel and James Newman's book Gödel's Proof [0], mentioned in the article. Alternatively, Gödel Escher Bach by Douglas Hofstader is a classic which serves as a great (and more accessible) introduction to the proof [1].

[0] https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081...

[1] https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden...

Just read this book, IMO https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081...

It's only 160 pages and gives what seems to be a good explanation of the basics.

⬐ novalis78

Currently reading Morris Kline’s “Loss of certainty” - a beautiful very readable work that elucidates the relationship of Mathematics with concepts of ‘truth’ and ‘reality’ throughout mathematical history.

https://www.amazon.com/dp/0195030850/ref=cm_sw_r_cp_api_i_aJ...

Here's a good adjacent read that I thought was a much clearer and relatively accessible tour through the Proof - https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081... - it's more of a pamphlet than a book, really.

⬐ jerf

GEB is fun, but it's definitely a bad introduction to the idea itself. It's a lot more fun if you already understand the subject matter and can enjoy the tone of the book.

I couldn't make it through GEB, but I read a good concise explanation in a book called Godel's Proof: https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081...

A few recommedations:

1. Black Like Me - John Howard Griffin - https://en.wikipedia.org/wiki/Black_Like_Me

2. More Matrix and Philosophy - William Irwin (ed) - https://www.amazon.com/More-Matrix-Philosophy-Revolutions-Re...

3. Godel, Escher, Bach: An Eternal Golden Braid - Douglas Hofstadter - https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach

4. The New Jim Crow - Michelle Alexander - https://en.wikipedia.org/wiki/The_New_Jim_Crow

5. Capitalism: The Unknown Ideal - Ayn Rand - https://www.amazon.com/dp/0451147952/ref=sspa_dk_detail_4?ps...

6. The Fountainhead - Ayn Rand - https://en.wikipedia.org/wiki/The_Fountainhead

7. The Book of Why: The New Science of Cause and Effect - Judea Pearl - https://www.amazon.com/Book-Why-Science-Cause-Effect/dp/0465...

8. The Education of Millionaires - Michael Ellsberg - https://www.amazon.com/Education-Millionaires-Everything-Col...

9. The Silent Corner, The Whispering Room, and The Crooked Staircase - Dean Koontz - http://www.deankoontz.com/book-series/jane-hawk

10. Godel's Proof - Ernest Nagel & James Newman - https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081...

11. After Dark - Haruki Murakami - https://www.goodreads.com/book/show/17803.After_Dark

https://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/08147583...

Can be read in a couple of hours and you'll know as much about Goedel's work as any GEB reader. Nowadays even comes with a Hofstadter intro but no bulk or talking animals.

I'd highly recommend "Gödel's Proof" by Ernest Nagel and James Newman (https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081...). It'll probably require a bit of patience to go through, but should be fairly accessible to reader without an extensive mathematics background.

⬐ sidcool

What are the practical implications of the incompleteness theorem?

⬐ fusiongyro

There will always be more math to be discovered, because there will always be theorems you can state but not prove within the confines of the existing systems.

⬐ ben_w

You cannot ever know for sure that your software is bug free, because no finite system of logic is both true and complete.

At least, that’s my understanding of it.

⬐ thathappened

Afaik this is all related to relativity. No good or bad unless unrelated like ++ or -- and we're in a system where, at least humans, only perceive reality as it relates to us. You need air, so do I, together we have a similar need but also together we occupy each other's space and resource

⬐ dsr_

Not exactly.

For any sufficiently powerful system (Turing completeness is definitely powerful enough) there are statements which are true but cannot be proven by that system. Secondarily, no system can demonstrate its own consistency.

However, if you limit your software enough, you can prove that every possible input is handled correctly. That involves removing Turing completeness. E.g. once you accept a language as a configurator, you can no longer prove that. CSS3 is Turing complete. JSON is not.

One requirement is limiting the size of inputs.

⬐ EtDybNuvCu

Mathematics is postmodern; there's no single formal system which is the concrete bedrock of mathematics, and there will always be some true-but-unprovable theorems in consistent formal systems.

Cynics might take this to mean that maths is meaningless. On the contrary, I'd like to suggest that maths is the canonical emergent pattern; any formal system with sufficient complexity to represent itself will automatically exhibit some algebraic structure, and maths emerges naturally from there.

The biggest implication for computer scientists is that, combined with results of Church and Tarski, we should expect that meta-languages are more powerful than object-languages, whether this is by preprocessing and macros like in C/C++ and CL, or by avoiding using meta-features except when necessary like in Python and Ruby.

⬐ aaroninsf

Whole-heartedly seconded. I went through the proof twice, once in a math context and once a philosophical one. This work was referenced in both.

I don't mean to be rude, but this objection only seems handwave-y if you don't understand Gödel's proofs (common), or you have some refutation of them (obviously uncommon, but definitely interesting).

This is a good not-too-technical but not-condescending explanation https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081... (it does get into the technical details; it just doesn't go line by line as you would if you wanted to recreate the proofs).

As long as you have the expressive power of Peano arithmetic (which all programming languages ought to, and definitely all proof systems ought to), you can find a Gödel sentence in the system and thus prove that it can't prove, of itself, "x is consistent".

It's worth looking into, if only for the enjoyment.

⬐ hinkley

Have you ever written a compression algorithm?

You do know that Shannon proved that general purpose compression is impossible, right? Why bother if that 75% compression ratio is provably impossible?

⬐ ahelwer

It isn't at all obvious that "a theorem prover proving itself correct" and "an axiomatic system proving its own consistency" are the same thing, beyond both being in the category of things which refer to themselves in the domain of mathematical proofs. Software correctness isn't the same as consistency. A program is correct if it refines its specification, and an axiomatic system is consistent if it does not lead to contradiction. Before doing a deep dive into Gödel we need to firmly establish we're actually looking at the right problem.

Even if Gödel is shown to apply in the strict generalized theoretical sense, it might be irrelevant to practice. Theory and practice often differ enough for practice to be very useful; we easily prove halting for most programs we care about, compute solutions to average-case NP-Complete problems without a noticeable rise in CPU temp, and (as the other poster at this level said) write compression algorithms which work well on all relevant inputs. This is poor analogous reasoning, of course, but I include it because demonstration of universal practical pitfall would be very interesting in much the same way specific manifestations of availability loss in fault-tolerant consensus algorithms are interesting.

Really though, I am tired of the above exact exchange playing out in every thread I've seen here on formal verification. Someone raises the obvious concern of bugs in the theorem prover. Someone else raises the bootstrapping solution, cribbed from compilers. Someone else raises the Gödel objection; and there the conversation dies. Dig deeper.

⬐ simondedalus

I understand the frustration, but the Gödel objection will always be raised as long as someone asks for a prover that can prove itself correct (read "proves false statements or fails to prove true statements," which just is consistency). To put a finer point on it, once you get how "an axiomatic system [can't prove] its own consistency," it actually is rather obvious that "a theorem prover [can't prove] itself correct." How would it? Without axioms or classical logic? What's it doing for the things that aren't it itself?

Notice though, Gödel's incompleteness didn't end formal logic (all the better for Gödel). I know we're in a public forum, but I would note that your "But what about the practical applications!?" is misplaced (though not poor analogous reasoning--I think you're hitting the nail on the head, honestly). Formal verification is not futile because of Gödel's proof. However, a self-verifying formal system is--which is a useful insight, especially for those interested in formal verification.

As an aside, I don't think you need to convince anyone that's actually recreated Gödel's proofs to approve of continued work on formally verified code. We would get excited about that stuff even if it weren't practical.

⬐ nickpsecurity

Good write-up. I hear you about the patterns of debate that prop up in these threads. My favorites are the ones where people show up with specific logics, techs, or R&D suggestions that others and I learn from. Such an approach might lead to people solving hard problems over time.

My favorite counter to the Godel thing, esp about termination, was sklogic showing how far from reality these concerns were by illustrating that a while loop counting down toward zero with "stop if zero" condition will guarantee a termination of any algorithm working piece-by-piece in inner loop so long as hardware functions. No magic math at all required to defeat the termination requirement in real-world. I added watchdog timers or even shelf-life of modern parts can do the same.

I did something similar when I was concerned about infinite loops or DOS attacks from malicious input. Just box it up in something I know will work with something checking up on it. Another was algorithm theory telling me QuickSort performed better but choose HeapSort if worst-case is a problem. A smarter programmer told me to just time average for QuickSort, run it with a watchdog, kill it on any instance it takes too long, and use HeapSort for that instance. Those are the kind of tips I appreciate about these terrible problems the theoretical side brings me. Hell, if only theory people would find, generalize, and expand on all the effective cheats in engineering instead of idealistic or abstract stuff. :)

⬐ simondedalus

But doesn't the constant Gödel reference push people, exactly, to work toward effective cheats? Imagine if the people putting in effort to make real systems instead spent their time trying to create the self-verifying prover.

⬐ nickpsecurity

No it distracts people by making them think some legend in math showed verification was provably a waste of time. The number that show up to keep saying it on reputable forums like this one leads to increased belief it's true via repetition effect. So, it's overall bad vs mentioning something relevant to practical verifications.

Plus, hardly anyone is making a self-verifying prover. Someone just asked about that. I tried what I hope is the proper response of simply linking to a self-verifying prover that succeeded in that goal up to first-order logic. So, that's already done with us just needing similar ones for checkers of HOL, Coq, ACL2, etc. Contrary to your implication, the Milawa techniques are based on and supporting some of most practical verification work to ever be done. So, one of few times someone totally ignored Godel in what non-experts would consider Godel's domain led to one of best results in formal methods.

We don't need Godel at all in these discussions. We just need to explain what formal methods are, their successes, their limitations, how to properly use them, and ideas for new projects.

I always found the study of logic to be very interesting. What I highly recommend reading first, however, is a layman's introduction to Gödel's Incompleteness Theorem [1]. The essential idea is, much like the conclusion in this article, that axioms are chosen and theorems are proven within the systems they create. The caveat is that no system can be proven to be complete.

[1] http://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/081475837...

GEB was a considerable waste of time and contributed nothing to my understanding of intelligence or AI. The time would have been be better spent elsewhere.

If you want to understand Godel's proofs then I recommend the book "Godel's Proof" by Ernest Nagel and James R. Newman:

http://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/081475837...

Instead of Hofstadter's GEB, read some of his papers, e.g., "Analogy as the Core of Cognition" http://prelectur.stanford.edu/lecturers/hofstadter/analogy.h...

But there are others who have focused longer on analogy, e.g., George Lakoff:

"Metaphors we Live by"

http://www.amazon.com/Metaphors-We-Live-George-Lakoff/dp/022...

"Where Mathematics Come From: How The Embodied Mind Brings Mathematics Into Being":

http://www.amazon.com/Where-Mathematics-Come-Embodied-Brings...

"Women, Fire, and Dangerous Things"

http://www.amazon.com/Women-Fire-Dangerous-Things-Lakoff/dp/...

⬐ carbocation

I don't agree with your dismissal of the work, but this is a very constructive comment on the whole with many interesting references and should not have been downvoted.

⬐ giardini

I added the references later so that's the cause for down voting.

I didn't really dismiss the book: I read it attentively in it's entirety and, as anyone who has read it knows, that is a big book. But in the end I found nothing new or thought-provoking. Entertaining, yes; enlightening, no. "Where's the beef?" came to mind over and over as I moved through the text.

Hofstadter is certainly bright, has a voluminous memory and can be an entertaining writer but GEB is not IMO a contribution to AI. My expectations were undoubtedly too high.

⬐ cgh

GEB's purpose wasn't to provide a comprehensive understanding of Godel's proofs. Nor was it trying to explain AI. It was a very personal book of thinking about thinking, basically. If you aren't a native English speaker then the book might have been less effective.

I own the Nagel and Newman book and probably read it every two years or so.

I also own the FARG book which summarises the work of the Fluid Analogies group. I don't think these papers are as interesting or exhilarating as GEB so I have to disagree with you there.

For anyone looking for a brief, accessible explanation of the proof itself, I cannot recommend the Nagel and Newman [1] highly enough.

[1] http://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/081475837...

⬐ alok-g

While I loved the first few chapters of the book, and they were mind-opening, I found the explanation of the proof unsatisfactory. As I recall, it was mentioned in the preface that the book will give a complete outline of the actual proof. I did not find this to be the case, the outline seemed to jump quite a bit from one thought to another leaving me with more questions about the proofs than answers. I still do not understand the proofs (though I now nearly understand an analogous result in computer science via Jeff Ulmann's book).

⬐ jfb

I has been a few decades since I read it for the first time, so I may be glossing it in my mind.

Oh wow! This is a great write up on Godel's work. Anybody who even vaguely cares about fundamentals of computer science should definitely give it a read, and if possible a thorough read.

Slightly related: Although a more technical/deeper discussion, but the book "Godel's Proof"[1] by Nagel and Newman is a very approachable text in this domain, and explains many aspects of the incompleteness theorems.

[1] http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814...

⬐ chriswarbo

I found it quite approachable and thorough, although it throws the the diagonal lemma out there without any real explanation even though it's crucial to the reasoning that follows it.

Also I disagree with the completely unfounded assumptions at the end that the (terribly named) Reals have something to do with reality. The Reals are a Mathematical curiosity at best, but more often than not they complicate the understanding of subjects to which they have no relevance, eg. fractions (especially their decimal notation), calculus, physics, computing (especially floating point) and so on.

It's fine to treat infinite constructs like the Reals declaratively, eg. as functions which can be composed, but it's meaningless to reason about doing things to their 'final results', since there are no such things by definition. In more precise terms, it makes sense to reason about the output of co-terminating functions (which loop forever, spitting out, for example, a never-ending sequence of digits) but not diverging functions (which loop forever without ever getting as far as their first digit).

⬐ stiff

The real numbers have no relevance to calculus? Is there a way of doing calculus without real numbers that is simpler? What are you talking about?

⬐ None

None

⬐ hobs

Honorable mention for http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach which has been mentioned many times on HN. Has many different ways of explaining Godel's genius. Though to be fair you could just read this article and be good.

⬐ hamiltonkibbe

GEB is awesome.

David Foster Wallace's Everything and More: A Compact History of Infinity covers Cantor and is an interesting read about... you guessed it.. Infinity.

Re: Turing http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html

⬐ tekromancr

+1 for GEB. I have been reading it on and off for about 2 years. It's a fun book, but every time I finish a reading session, I am exhausted. I am about 25% through.

⬐ hobs

Yeah it took me about 7 months to finish it, and you are right, every time I just felt beat and my mind was racing, what a great book.

⬐ laxatives

IMO just finish chapter 14 and you've basically finished the Godel portion of the book. The rest felt more like Hofstadter's random musings on AI, DNA and some other topics (some of which felt outdated). There's some crazy anecdotes of Ramanujin that I had never heard elsewhere though.

⬐ pachydermic

Well the structure of the book is supposed to be like a JS Bach song - so in the end, what you get is a combining of all the familiar themes and sometimes it feels a bit repetitive and boring. But if you've read that far, it's worth reading the rest. It's much easier to get through than when you're seeing stuff for the first time and really trying to wrap your head around it.

After reading the book, would I have some understanding of the actual proof, or learn mostly the historical context around it?

Note: I have felt deceived after reading Godel's Proof [1] since the authors claimed in the preface to have given an outline of the complete proof in the last chapter but did not (it was grossly incomplete). I am still indebted to the book though for teaching me how to think about pure mathematics.

[1] http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814...

⬐ ColinWright

A popular science book about Fermat's Last Theorem will certainly not give you any kind of real understanding of the proof. It will give you some historical context.

It is a difficult proof, and some of the underlying basic concepts are already deep in their own right, deeper than will be covered in an advanced undergraduate degree.

There are some attempts at higher level overviews on the web, and they are slowly getting fleshed out.

Thanks for the recommendation, this sounds fascinating. By any chance have you also read "Godel's Proof" by Ernest Nagel and James Newman? http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814... It sounds very similar in scope.

Haven't read that one, but I try to re-read Nagel and Newman's at least once a year: http://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/081475837...

One thing I love about N&N is that it's short (160 pages) and the paperback is cheap ($7.65) so that I have no compunctions in lending it out.

⬐ edanm

Yes, I've read that one as well. It was a while ago, but from what I remember, it was higher-level than the Smith book. The Smith book is basically a normal mathematics curriculum book, not a "pop science" book (not to say that N&N is), which works out theorem after theorem to get to Godel's proof. Also, it starts off with computer-science proofs instead of the original Godel proofs, which many in this audience will probably prefer.

You're doing exactly what you need to do, you are putting extra effort into it.

My feeling is the "bad" cs grads usually did not put in that extra effort. Reading GEB is rarely a required par of any CS degree but reading it is an incredibly useful thing in my view. It's a thick book and takes commitment to read.

Side note: Check out this book (http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814...) on Godel's proof. It's been updated by Doug Hofstadter the author of GEB. I found it pretty good. Read it slowly, two three time if needed. It will make sense.

⬐ baddox

Thanks for the recommendation. I've actually been looking for a new book.

I read this little gem over the summer: Godel's Proof (http://www.amazon.com/Godels-Proof-Ernest-Nagel/dp/081475837...)

At 160 pages, it's the ideal size to carry with you everywhere you go. All summer long, any time I had an extra half an hour, I would take it out and read/re-read a chapter.