Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!samsung!think.com!snorkelwacker.mit.edu!bloom-beacon!dont-send-mail-to-path-lines
From: cgl@t13.Lanl.GOV (Chris Langton)
Newsgroups: comp.theory.cell-automata
Subject: Re:  meta-life
Message-ID: <9105091418.AA03565@t13.lanl.gov>
Date: 9 May 91 14:18:58 GMT
Sender: daemon@athena.mit.edu (Mr Background)
Distribution: inet
Organization: The Internet
Lines: 19

stu@sct60a.sunyct.edu (Stu Card) writes:

> If Life is 'universal', I think that means it is also 'complete' in the sense
> of Goedel's Theorem, and therefore inconsistent; otherwise it must be 
> 'incomplete' (although perhaps 'nearly complete'?!) to keep it consistent.

No - LIFE belongs to the class of formalisms that is consistent but incomplete. 
LIFE's universality implies that it is subject to the same undecidability
problems as a universal Turing machine, which is the basis for incompleteness. 

   Cheers!

   Chris Langton

   Complex Systems Group
   MS B213, Theoretical Division	Phone: (505) 667-9471
   Los Alamos National Laboratory	Email: cgl@t13.lanl.gov
   Los Alamos, New Mexico, USA		FAX:   (505) 665-3003
   87545