Xref: utzoo comp.theory:1368 sci.math:14516 alt.fractals:784 Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!dali.cs.montana.edu!uakari.primate.wisc.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!rpi!uupsi!njin!princeton!bravo!markv From: markv@bravo.Princeton.EDU (Mark VandeWettering) Newsgroups: comp.theory,sci.math,alt.fractals Subject: Re: chaos Keywords: chaos undecidability Message-ID: <5032@idunno.Princeton.EDU> Date: 4 Jan 91 18:44:08 GMT References: Sender: news@idunno.Princeton.EDU Reply-To: markv@bravo.Princeton.EDU (Mark VandeWettering) Followup-To: comp.theory Organization: Princeton University Lines: 27 In article bnh@wiis.wang.com (Bill Halchin) writes: > > In the January 1991 issue of Discover magazine, there is an article >entitled "Beyond Chaos". It describes research done by Crisopher Moore, >a physics graduate student at Cornell. The information in the article is >very skimpy. He apparently came up with an algorithm for a dynamic system >that is so chaotic it is undecidable (??). It consists of transformations >on triangles & is equivalent to a Turing Machine doing an opened-ended >search. There is enough in the Discover article to nake it very interesting, >but no references. Is there a paper published on this that somebody could >point me to? Post if you want, but please send e-mail to me also. Thanks. This was a nice exercise to figure out. I saw something like this written up in one of the Physica Letters journals a while back. The basic idea is that given a Turing Machine, you can express it as fairly simple tranformations on the unit plane, which form a dynamic system. Then, for this dynamic system, you might ask whether a given point will enter a particular region of space. But, this is identical to the question as to whether the Turing Machine will enter a halting state, which is (of course) undecideable. Very nice. I hope someone can post the reference, I can't seem to find my copy of the paper any more. mark Mark VandeWettering markv@acm.princeton.edu