Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Gödel, Escher, Bach: an in-depth explainer

alignmentforum.org

Post reply on HN
Print view View original

101–110 of 252 posts

Re: Gödel, Escher, Bach: an in-depth explainer

#101

Post by jcranmer »

red_trumpet wrote: post #51
jstanley wrote: post #39

> Gödel's Incompleteness Theorem: any sufficiently rich formal system, together with an interpretation, has strings which are true but unprovable. This is only half of it! Gödel's Incompleteness Theorem states that any sufficiently rich formal system, together with an interpretation, either has strings which are true but unprovable or has strings which are provable but untrue. Either is possible! In practice people p…

How can a statement that is unprovable be true? I always had the impression that unprovable means you could add either the statement or its negation as an axiom, and both resulting systems are as consistent as the system you started with

I'll explain it in a different way than normal.

We can define a notion of complexity for any given integer as being the size of the smallest program that returns that integer. Obviously, I'm being imprecise here, but it should hopefully be clear that it is possible to get the details right and the precise nature of those details aren't going to be relevant for what follows.

Now suppose we have a program that can find the complexity of a given integer. Then, we can write the following program:

  for (i = 0; ; i++) {
    if (complexity(i) > 2*K) {
      return i;
    }
  }
(where K is the size of this program). Now we have a contradiction: we've constructed a program of size K that computes an integer i, but the smallest program that can do so is of size 2*K. This means that one of our assumptions is wrong, and the only one that can be wrong is that we could write a program that computes complexity.

As a result, we have some integer that has a complexity--it's still well-defined (at least if you have the axiom of choice, but I'm not sure if that axiom is necessary)--but we can't necessarily prove that any integer has a given complexity.

Re: Gödel, Escher, Bach: an in-depth explainer

#102

Post by quantum_state »

mreid wrote: post #93
red_trumpet wrote: post #51

Earlier quoted context omitted.

How can a statement that is unprovable be true? I always had the impression that unprovable means you could add either the statement or its negation as an axiom, and both resulting systems are as consistent as the system you started with

It might be easiest to give a sense of what "unprovable but true" means by way of an imagined example. Goldbach's conjecture is that "every even number bigger than 2 is the sum of exactly two prime numbers", so 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, etc. For this statement to be *true* it just means that every even number there must exist two primes that add to that number. This is a statement about infinitely many integer…

what if the proofs cannot be described as finite or countable sets that does not render a straightforward application of diagonalization? What happens to Goedel’s theorem then?

Re: Gödel, Escher, Bach: an in-depth explainer

#103

Post by widowlark »

patcon wrote: post #99
widowlark wrote: post #66

Earlier quoted context omitted.

I have no problems with psychedelics or their use. I took issue with the implication that they are needed in order to think in the way Hofstadter does - it's kind of like asking what flippers Michael Phelps uses when he swims in the olympics.

thanks for responding! i might feel a bit differently, but I think I hear where you're coming from: that it does a disservice to great people when we flippantly imply their greatness originates from simplistic things outside themselves (if I'm still way off, feel free to correct, but pls don't feel obligated to engage :) )

That might be a good way of putting it. I think also that the question to me implied a cynicism about how people can be curious and creative while also being scientific, but the original commenter has already clarified they did not intend this interpretation at all

Re: Gödel, Escher, Bach: an in-depth explainer

#104

Post by davesque »

scrame wrote: post #30
davesque wrote: post #10

I've read GEB over many years rather in the way someone would read the Bible. I pick it up from time to time and enjoy chewing on one or two chapters of material. But I've yet to figure out if the book actually has a specific thesis. I know it's all about the power of interpretation and the way in which interpreting a formal system as self-referencing has the effect of completely blowing up the intended design of tha…

I think of it more as a survey of a bunch of disciplines, and some hopeful hypothesis of future AI research. He writes in an accessible way and touches DNA, poetry, fractals, video feedback, topographical systems, just... a whole bunch of things. It is for sure reaching, but his core conceit is about pattern recognition and emergent behavior and he throws everything he's got at the wall there through the eyes of his…

Yeah, awesome way to sum it up. I think I'm suffering from the nearsightedness of someone who now lives many decades after the 1970s.

Re: Gödel, Escher, Bach: an in-depth explainer

#105

Post by mxkopy »

widowlark wrote: post #100
mxkopy wrote: post #96

Earlier quoted context omitted.

I took a lot of psychedelics in my life, and in that period I also read GEB quite religiously. And in my experience, I think it could have taken me a lot longer to empathize with the book than if I weren't taking psychedelics; not because of a false sense of understanding but because of a similarity in mental context. I felt like on LSD, I could look behind the curtain, so to speak. This isn't the same feeling as whe…

I truly am not intending this upcoming statement as an insult: I did not struggle with 'looking behind the curtain' while reading GEB, nor did I find the concepts silly - I was rapt with curiosity the whole reading and came to many profound conclusions about the book and it's ideas - and I was not on LSD. Whatever helps you personally understand the world in a more meaningful light is wonderful, but it certainly was…

I don't find that insulting. It's wonderful for you.

What I find insulting is saying that calling GEB trippy is an insult. It's genuinely trippy and there's nothing wrong with that.

Re: Gödel, Escher, Bach: an in-depth explainer

#106

Post by gerdesj »

Kranar wrote: post #77
gerdesj wrote: post #69

Earlier quoted context omitted.

"This statement is false". GEB is a marvellous work that is accessible to anyone with reasonably good school grade maths. I chanced upon it by accident in the school library one day and was hooked after a few pages. Anyway the crux of the matter is that you can very carefully construct a statement about a system that can't be either proven or disproven by that system! I don't have anything like the formal knowledge t…

>"This statement is false". Close but not quite as that's an inconsistent statement. "This statement is unprovable." is the approach Godel takes and eliminates the inconsistency. Either that statement is true, in which case it's unprovable, or it's false in which case there exists a proof of a false statement.

It obeys all the "laws" (OK vagaries) of English grammar. There is nothing in the rules of grammar that requires a statement in English to actually be self-consistent. The problem only surfaces once you attach the associated meanings to the various components.

I just picked a classic to start off my prior comment which morphed more into praise for GEB than Goedel's brain breaker.

I have dim memories of a cracking constructive argument starting off with some very basic axioms where one was written as S, and two as SS and so on, then it all went a bit mad but the genius of Hofstadter is to make all that impenetrable palava nigh on accessible to the layman (with a bit of effort from the reader).

The horrendous thing about Goedel is that the final flourish is clearly correct (I assume that responsible adults have filled in the formal bits, I'm sticking to the lies to children version). It is both terrifying and perhaps obvious at the same time. I can imagine the sense of dread when mighty edifices such as Herr Hilbert's suddenly looked a bit shady and then anger, followed by disbelief and finally acceptance as the big hitters really got to grips with it. The world hasn't come to an end because of Goedel but it certainly got a bit more interesting.

I think that it is almost comforting that we have a system that can be complicated enough be to capable of saying things about itself that can't be proven within itself. I think that there is a good chance that our system of mathematics will eventually become complicated enough and no more. Obviously there will always be spherical cows and some absolutely mad numbers and when I say eventually - that will take forever (nearly).

Re: Gödel, Escher, Bach: an in-depth explainer

#107

Post by mtreis86 »

ozay wrote: post #71
Judgmentality wrote: post #15

Earlier quoted context omitted.

https://www.smbc-comics.com/index.php?db=comics&id=2245 There are several famous mathematicians known for their avid use of amphetamines.

Amphetamines aren't psychedelics. Like nicotine or caffeine they increase performance.

In large doses over extended periods of time, they do change how someone thinks and perceives the world, perhaps for the worse. See stories of amphetamine psychosis. Those somewhat mirror a type of extended bad experience after using psychedelics, often called dark nights.

Re: Gödel, Escher, Bach: an in-depth explainer

#109

Post by dtgriscom »

dinobones wrote: post #56

Am I the only one who did not find this book that interesting? I studied CS so it just felt like reading my class textbooks again, except with random trippy stories in between that try to shoehorn theory into a poor metaphor. The fundamentals of CS (strings, automata, graphs) are elementary building blocks. This is by design. You can apply them to almost anything. Almost everything "is a graph", or "recursion" if you…

I plowed my way through about two thirds of it. Lots of interesting stuff, but I finally gave up because it seemed just too self-involved and self-referential. Building up this enormous edifice, just to be able to say "Hey! Check out my edifice!"

I guess I'm just too much of an applied engineering kinda guy.

Re: Gödel, Escher, Bach: an in-depth explainer

#110

Post by frimsah »

fao_ wrote: post #59
red_trumpet wrote: post #51

Earlier quoted context omitted.

How can a statement that is unprovable be true? I always had the impression that unprovable means you could add either the statement or its negation as an axiom, and both resulting systems are as consistent as the system you started with

Without a telescope I can't prove to you that andromeda is a galaxy, but it is.

following this analogy: is it possible with the proper instrumentation, or axioms, that a mathematical statement might become provable?
Post reply on HN