Xref: utzoo rec.puzzles:8232 sci.math:15544 comp.theory.cell-automata:310 Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!decwrl!asylum!osc!jgk From: jgk@osc.COM (Joe Keane) Newsgroups: rec.puzzles,sci.math,comp.theory.cell-automata Subject: Re: How Intelligent are the Winning Ways? Summary: They know what they're doing. Keywords: undecidable Message-ID: <4654@osc.COM> Date: 5 Mar 91 11:49:47 GMT References: Reply-To: jgk@osc.COM (Joe Keane) Followup-To: rec.puzzles Organization: Versant Object Technology, Menlo Park, CA Lines: 22 In article bagchi@eecs.umich.edu (Ranjan Bagchi) writes: > Anyway...some of the initial proofs I have no problem with, >until the author mentions some wonderful things which a Life computer >could do, if there were some kind of closed form way to determine what >a given Life configuration would stabilize out to. This is where I >balked... seeing that a Turing Machine is definitely constructable in Life >if you can do a computing machine, then the author just described the >Halting Problem, and treats it like it's something decidable. I think you're misinterpreting them. They're just emphasizing the point that the decision problem for Life is undecidable. They claim that a Life computer can be programmed to spit out the first solution to Fermat's Last Theorem, if one exists. I wouldn't bet my life on their construction, but i don't see any problem with it. Then, if you had a decision procedure for this computer, you'd know if FLT were true or false. Some problems are undecidable in a contrived or artificial way. Their point is that Life is not like that, since it can include arbitrary Turing machines, including universal ones. If there were a decision procedure for Life, then you could solve any mathematical problem.