stu@sct60a.sunyct.EDU (Stu Card) (05/09/91)
The responses to I.J. Palmer's question raise the following possibility: is it possible to define a problem, the solution to which requires an INFINITE regress up these meta-life simulation levels? I suspect so. 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. I am not mathematically heavy enough to know if I am making sense. Anyone out there with a good understanding of Goedel's Theorem who would be willing to enlighten me on how it applies to the universality of a computing scheme in general, and Life in particular? stu@sct60a.sunyct.edu Stu Card
cgl@t13.Lanl.GOV (Chris Langton) (05/09/91)
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