Evolving systems: Gödel's theorem and its significance

Notes for an Evolving Systems conversation related to Chance: Its meaning and significance
Paul Grobstein
20 April 2010

(on line forum at /exchange/evolsys/chance10)

The place I would like to get to and why ...

It is provably NOT the case that a full understanding of the universe, including the participation of humans trying to understand it, can be achieved by a any description in terms of an underlying set of initial principles and deterministic rules of interaction (contra Wolfram and the agendas, conscious or otherwise, of many disciplines).  The problem has to do not solely with complexity or numbers of variables or time or human proclivities but reflects as well inherent characteristics of the explanatory capabilities of logic, computability, and formal systems.  Such systems by their nature are limited in the range of understandings they can elaborate and explore. 

It follows from this that there is a need for a less constrained approach to characterizing the objectives and methods of inquiry.  Evolving systems, with their fundamental dependence on some degree of randomness, seem to provide an example of such a less constrained approach, one that if clarified might provide a reasonable alternative to existing conceptions of the nature of inquiry. 

Gödel's contribution (as Paul makes sense of it, borrowed/elaborated from link 1 below )

Imagine a machine that MINDLESSLY generates statements including statements about itself (self-referentiality).  MINDLESSLY means the machine must have follow a strict (deterministic) set of rules (axioms and procedures, "properties and rules").  It can start with any set of axioms or any statement that has previously been generated starting with some set of axioms. 

Among the statements the imaginary machine can generate are

P*x      which means "this machine will print x"
NP*x     which means "this machine will never print x"
PR*x     which means "this machine will print xx"
NPR*x     which means "this machine will never print xx"

Consider the state NPR*NPR* which means "this machine will never print NPR*NPR*"

If the machine never prints NPR*NPR* then there is a true statement that the machine never prints (the operation of the machine is "incomplete").

If the machine prints NPR*NPR* then the machine prints statements that aren't true (the operation of the machine is "inconsistent". 

Any machine that prints only true statements must fail to print some true statements (logical systems that include self-referential capability can be either consistent or complete but not both). 

It follows that any "mindless" system, one that works in terms of fixed axioms and procedures, must either generate contradictory statements (be "inconsistent"  or must fail to generate some true statements (be "incomplete").  And hence that any approach to making sense of the universe (including the role of efforts to achieve that) must make use of something in addition to logical or "formal" processes.

The key point here (as per discussion with Greg) is not that paradoxical sentences exist; their existence has long been known.  What's important is that the paradoxical sentence is a necessary consequence of a logical or formal process of reasonable power.  In Gödel's proof, the relevant sentence is "This statement is not true." [see Alan's comment in yellow box]

[This brief sketch illustrates central elements of Gödel's proof as they seem to me relevant to the current discussion.  It in no way should be taken as a complete characterization of the  proof (notably missing is "arithmetization" as per link 2 below), nor of the context in which it was developed (link 3 and refs 4-6 below), nor of other ways the significance of the proof can be characterized (link 3 and refs 4-6) below.  By wide consensus, the single best description of the proof for a general audience is ref 4 below]

1. World's shortest explanation of Gödel's Theorem
2. Kenny's overview of Hofstadter's explanation of Gödel's Theorem
   
3. Gödel and the limits of logic (adapted from an article with the same name/author in Scientific American, June, 1999)
4. Gödel's Proof by Ernst Nagel and James R. Newman, 1958
5. Incompleteness: The Proof and Paradox of Kurt Gödel by Rebecca Goldstein, 2005
6. A World Without Time: The Forgotten Legacy of Gödel and Einstein by Palle Yourgrau, 2006