Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Don't read this without thinking about the questions first!

I tried to be short... there's a considerable amount of handwaving. I'll present two components to each of my answers. One that stays within mathematical logic and then one that expands a bit into philosophy.

1. Strictly mathematical logic: Godel's incompleteness theorems can be viewed as a limiting result on the absoluteness of mathematical induction (this is not strictly true, in fact we lose even more than absoluteness of induction, see e.g. Robinson's Q, but I'll leave that aside for now). Conway's Game of Life rules are complete in the context of a single step. That is for any step n, Conway's Game of Life rules completely determine step n + 1. The assumption that given a fixed starting state, this means that Conway's Game of Life is completely determined for all steps is exactly a statement of mathematical induction. In particular, we are piggy-backing off of the induction axiom of Peano arithmetic here. That's where Godel's incompleteness theorems get you.

One way of thinking about Godel's incompleteness theorems is that they attack the assumption that because we have defined every step transition we have defined the whole process. Hence certain "global" statements about potentially unbounded processes remain up in the air. Even if we rule by fiat with an induction axiom (or axiom schema) that this must be true, some ambiguity remains. "After a certain point once this square turns white it never turns black again" or "this square will never turn white" are both statements that are independent of Conway's Game of Life rules for certain squares and starting configurations.

Now this ambiguity is not observable because while we have ambiguity for unbounded questions, as soon as we place any bound, no matter how large the n (e.g. for the next 1000000 steps this square will not turn black), there is no ambiguity. Incompleteness hinges essentially on the ability to make unbounded statements which involve the words "eventually," "always," "never," etc.

Now the philosophical implications of this are interesting. This question is why I'm skeptical of naive attempts to talk about the incompleteness theorems' consequences for physical theories of the universe. Intuitively I view physicists as trying to find the "Game of Life" rules for the universe, and that if they did, that would be as good a candidate as any for a "theory of everything." In particular these rules would be local and finite, rather than global, infinite statements of the sort I outlined above. If you're willing to accept Conway's Game of Life as being complete enough for your purposes, I would argue you should accept a similar "theory of everything" as being "complete enough."

Now there's no reason why Mother Nature must be kind enough to furnish us with such a theory, but that's a different story.

Another interesting philosophical component here is whether this implies Godel's incompleteness theorems have any meaningful physical manifestation. I don't have the time at the moment to get into that discussion, but suffice it to say I generally think that these discussions usually go off the rails really really quickly without a deep understanding of the incompleteness theorems rather than informal overviews of them. In the philosophical context of Conway's Game of Life, you'd expect to find deviations in different implementations of the the rules "after an infinite amount of steps have passed." Whether you find that a coherent statement or not has implications for the applicability of Godel's incompleteness theorems to the physical universe.

EDIT: To tie this to the hints I gave, unbounded statements involving words like "eventually" or "never" are precisely those statements that can be independent of the "axioms" of the Game of Life. When we talk about the completeness of the Game of Life we are talking about it only at a per-step level.

2. Godel's incompleteness theorems are ultimately statements about natural numbers, or at least what the current logical system in question thinks is a natural number. The interpretation that this natural number represents some logical statement is a metalogical one and unjustified within the logical system itself. We can only make this interpretation as an outside observer. So S' produces a "number" according to the algorithm we use to represent the statement of inconsistency of S. However, within S' this is just a number. It doesn't know how to turn that number into a logical contradiction that it can then produce and use to prove things. As an outside observer then we are either free to agree with S' that indeed yes what you've produced is a number and then use that number to deduce the inconsistency of S or we can disagree with S' that this number represents an inconsistency of S (informally, you can imagine that S' is "hallucinating" a number that while might be a natural number according to the axioms of S', is not a natural number according to ours as an outside observer).

If we have a notion of what the "true" natural numbers are, as opposed to natural numbers are "hallucinated," we can talk about whether S' is right about the consistency of S. The assumption that S' is not "hallucinating" natural numbers is known as omega-consistency (https://en.wikipedia.org/wiki/%CE%A9-consistent_theory). Whether "true" natural numbers exist... well that brings me to the philosophical ramifications.

If you believe that there is one true set of natural numbers then it's easy to dismiss S' as a trick, useful for proofs and exploration, but ultimately simply an interesting tool rather than reflective of reality. If you believe that there is no such thing as "one true set of natural numbers" then consistency is simply a relative statement.

EDIT: To tie this to the hints I gave, Godel's arithmetization scheme only gives you numbers. It's up to you the reader to interpret those as proofs and logical statements. Within certain bounds, you are free to disagree that in your interpretation that this number represents a valid proof (or in equivalent phrasing that this "number" is truly a number).



Thanks! I'm bookmarking this to come back to for a while :-)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: