bnh@wiis.wang.com (Bill Halchin) (01/03/91)
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. Bill Halchin
edgar@function.mps.ohio-state.edu (Gerald Edgar) (01/03/91)
In article <aymvgp.ibw@wang.com> 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? "Unpredictability and Undecidability in Dynamical Systems", Physical Review Letters, volume 64 (14 May 1990) pp. 2354--2357. According to Discover, one of the three noteworthy developments in mathematics for the year 1990. -- Gerald A. Edgar Department of Mathematics Bitnet: EDGAR@OHSTPY The Ohio State University Internet: edgar@mps.ohio-state.edu Columbus, OH 43210 ...!{att,pyramid}!osu-cis!shape.mps.ohio-state.edu!edgar
ilan@Gang-of-Four.Stanford.EDU (Ilan Vardi) (01/03/91)
In article <aymvgp.ibw@wang.com> 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 The Discover article also tries to give Fermat's last theorem as an example of a possible undecidable theorem. Apart from the fact that Fermat's last theorem is true if undecidable, the author couldn't distinguish between ``undecidable'' and ``not computable''. Moreover, another section of the article dealt with the factorization of 2^2^9+1, but never mentioned that the basic idea for the algorithm is due to Pollard. Since everyone must have mentioned this to the author of the article, one must conclude that not only does he not know any mathematics but he is also a bad reporter. It is strange that Discover magazine couldn't find someone able to do one of these things competently. Maybe they're following the example of Scientific American with their abysmal A.K. Dewdeney articles. In any case, any article on the major events in mathematics in 1990 should have mentioned the Fields medals.
john@hopf.math.nwu.edu (John Franks) (01/03/91)
In article <1991Jan2.181842.4221@zaphod.mps.ohio-state.edu>, edgar@function.mps.ohio-state.edu (Gerald Edgar) writes: |> |> "Unpredictability and Undecidability in Dynamical Systems", Physical Review |> Letters, volume 64 (14 May 1990) pp. 2354--2357. |> |> According to Discover, one of the three noteworthy developments in mathematics |> for the year 1990. |> |> |> |> -- |> Gerald A. Edgar |> Department of Mathematics Bitnet: EDGAR@OHSTPY |> The Ohio State University Internet: edgar@mps.ohio-state.edu |> Columbus, OH 43210 ...!{att,pyramid}!osu-cis!shape.mps.ohio-state.edu!edgar What were the other two? Also, if you have read the Physical Review Letters article, how about briefly telling us what is in it and your opinion of it significance? (N.B. Prof. Edgar is the author of "Measure, Topology, and Fractal Geomety", Springer-Verlag, 1990 -- an excellent book on these subjects) -- John Franks Dept of Math. Northwestern University john@math.nwu.edu
mikes@sylow.mscs.mu.edu (Michael Slattery) (01/03/91)
In article <aymvgp.ibw@wang.com> 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 Discover seems to feel that this was a significant discovery because it is a discrete system (and so has a precisely defined initial state and set of transition rules) and yet is unpredictable (in the Turing halting problem sense). These same properties are shared by any universal cellular automata space (including Conway's Game of Life). Does anyone know (esp. Moore if he's reading) whether there are features of Moore's system beyond these which are of general interest? -mike slattery, assoc prof Department of Mathematics, Statistics, and Computer Science
markv@bravo.Princeton.EDU (Mark VandeWettering) (01/05/91)
In article <aymvgp.ibw@wang.com> 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
cl@lgc.com (Cameron Laird) (05/13/91)
*La recherche*, mai 1991: numero special sur <<La science du desordre>>, y compris articles comme "La revanche du dieu Chaos" (un essai par P. Thuillier sur l'epistomologie), "La physique du desordre", "Henri Poincare, le precurseur", "Le chaos dans le systeme solaire", "Le chaos dans le system solaire", "Le chaos en biologie" (par R. M. May), ..., "Le hasard des nombres" (par G. J. Chaitin), ... *La recherche* est une revue populaire de la science, disponible dans le plupart des bibliotheques univer- sitaires americains. Pour moi, elle a plus de ... vivacite, disons, que *Scientific American*. Je la recommande a votre attention. -- Cameron Laird +1 713-579-4613 cl@lgc.com (cl%lgc.com@uunet.uu.net) +1 713-996-8546
BJK111@psuvm.psu.edu (Barbara J. Kratz) (05/14/91)
I took the liberty of translating the following post into English.
Please excuse my less-than-excellent French-to-English ability.
. From: cl@lgc.com (Cameron Laird)
.
. -----begin feeble translation-----
.
. *Research*, May 1991: special volume (?) of
. "The Science of Disorder", comprises articles like
. "The Revenge of The God Chaos" (an essay by P. Thuillier
. on epistemology), "The Physics of Disorder", "Henri
. Poincare, The Precursor", "Chaos in The Solar System",
. "Chaos in Biology" (by R. M. May), ..., "The [Chance?
. Randomness?] of Numbers" (by G. J. Chaitin), ...
.
. *Research* is a popular review of science, available in
. most American university libraries. For me, it has more...
. liveliness, one would say, than *Scientific American*.
. I recommend it to you.
.
. -----end feeble translation-----
.........................................................................
Barbara J. Kratz
Weather always looks worse Dept of Meteorology, Penn State
through a window bjk111@psuvm (bitnet)
bjk111@psuvm.psu.edu (internet)