baez@x.ucr.edu (john baez) (04/08/90)
In article <39oH02W8981q01@amdahl.uts.amdahl.com> kp@amdahl.uts.amdahl.com (Ken Presting) writes: >Any real quasicrystal must of >course be finite, and except for growth, is a static structure. But >the existence of objects which can be non-periodic over arbitrary spatial >scales suggests the possiblity of processes which are non-periodic over >arbitrarily long intervals of time. The growth of a quasicrystal itself >might serve as an example, but it is not clear that quasicrystals can be >grown to large sizes. It is also non-standard(!) to suppose that atomic >processes can be deterministic, but in the context of quasicrystals the >non-local hidden variable theories are more appealing than usual. I haven't managed to get ahold of it - does Penrose's book really suggest that the growth of quasicrystals, which seems to require "forethought" or nonlocal correlations to make the quasicrystal come out exactly right, indicates that there are nonlocal hidden variables, or that quantum computers can exceed the powers of Turing machines? What does he say about this? I've heard rumors... in my opinion, the obvious way out would be that real-world quasicrystals are not perfect but have defects when they get "stuck" in "solving the jigsaw puzzle". As for quantum mechanics and chaos, it's worth remarking that quantum systems in a *bounded* region of space almost always (i.e. except for cooked-up pathological mathematical examples) have discrete spectrum hence evolve almost periodically. This is the famous "absence of quantum chaos."
schumach@convex.com (Richard A. Schumacher) (04/09/90)
See the article "Quasicrystal Clear", Sci. Am Jan 1990, which discusses the "entropic" theory. This uses Penrose tiles but without the requirement of matching rules or any non-local effects, and still generates quasicrystals with the usual non-periodicity and five-fold symmetries.
turpin@cs.utexas.edu (Russell Turpin) (04/09/90)
----- In article <5328@ucrmath.UCR.EDU>, baez@x.ucr.edu (john baez) writes: > I haven't managed to get ahold of it - does Penrose's > book really suggest that the growth of quasicrystals, > which seems to require "forethought" or nonlocal correlations > to make the quasicrystal come out exactly right, indicates > that there are nonlocal hidden variables, or that > quantum computers can exceed the powers of Turing machines? Someone wrote a paper describing how Penrose tilings can result from local rules. I forget who this was. Perhaps someone else can provide a reference? I do not know if local rules have been extended to the 3-d case. Russell
kp@uts.amdahl.com (Ken Presting) (04/14/90)
In article <5328@ucrmath.UCR.EDU> baez@x.UUCP (john baez) writes: >In article <39oH02W8981q01@amdahl.uts.amdahl.com> kp@amdahl.uts.amdahl.com (Ken Presting) writes: > >I haven't managed to get ahold of it - does Penrose's >book really suggest that the growth of quasicrystals, >which seems to require "forethought" or nonlocal correlations >to make the quasicrystal come out exactly right, indicates >that there are nonlocal hidden variables, or that >quantum computers can exceed the powers of Turing machines? (Penrose' book, _The Emperor's New Mind_, is terrific. I recommend it highly for anyone interested in computation, physics, or AI, especially for anyone who has formal training in one or two of those subjects, and is curious about applications to the others) Penrose does not say much about the growth of quasicrystals. He does pay some attention to the problem of deciding whether a given set of tiles will non-periodically cover the plane. I have seen (but not read) a book called _The Mathematics of Quasicrystals_, so there may be some serious attention being paid to the issues. Penrose does cite David Deutch, "Quantum thoery, the Church-Turing pinciple, and the universal quantum computer", Proc. Roy. Soc. (1985) A400, 97-117. Apparently, a quantum device can exhibit some of the *speed* properties of a non-deterministic TM. As far as I know, there is no (well-founded) suggestion that non-recursive functions can be computed by these devices. > >What does he say about this? I've heard rumors... in >my opinion, the obvious way out would be that real-world >quasicrystals are not perfect but have defects when they >get "stuck" in "solving the jigsaw puzzle". That is probably the most reasonable position to take at the moment. The Sci. Am. note, "Quasicrystal Clear" (Jan 1990) supports it. It reports the hypothesis that quasicrystal growth is guided by entropic phenomena (the hypothesis is not explained in detail). This does not sound like a good idea to me. Thermodynamic variables are defined non- locally themselves. Furthermore, a thermodynamic explanation of a phenomenon ought to have an underlying mechanical explanation. Whether Brownian motion will do the job depends on the strength of the evidence for perfect tiling in quasicrystal structure. > >As for quantum mechanics and chaos, it's worth remarking that >quantum systems in a *bounded* region of space almost >always (i.e. except for cooked-up pathological mathematical >examples) have discrete spectrum hence evolve almost >periodically. This is the famous "absence of quantum chaos." This is very interesting. Discreteness in the spectrum of energy states is not by itself sufficient - there is no problem in having a denumerable infinity of discrete states within a finite interval. If a real system can depend in a macroscopically observable way on how close it gets to (eg) an ionization energy, then chaotic behavior might be observable in QM. How are the mathematical examples constructed? Ken Presting ("Clap your hands if you believe in hidden variables")
aboulang@bbn.com (Albert Boulanger) (04/14/90)
In article <965p02gf9cNw01@amdahl.uts.amdahl.com> kp@uts.amdahl.com (Ken Presting) writes:
Penrose does cite David Deutch, "Quantum thoery, the Church-Turing
pinciple, and the universal quantum computer", Proc. Roy. Soc. (1985)
A400, 97-117. Apparently, a quantum device can exhibit some of the
*speed* properties of a non-deterministic TM. As far as I know, there
is no (well-founded) suggestion that non-recursive functions can be
computed by these devices.
Well, Deutch does suggest that a quantum computer could determine
once-and-for-all that the Many Worlds interpretation is the correct
interpretation. I have not figured out whether this implies that it
computes a non-recursive function -- but probably so since all
recursive-functions obey classical causality. To put it another way,
the "extra" power of a quantum computer would come from its ability to
use non-local interactions and is not just an issue of computational
speed else one could use a normal TM to determine that the Many Worlds
interpretation is corect.
This is very interesting. Discreteness in the spectrum of energy states
is not by itself sufficient - there is no problem in having a denumerable
infinity of discrete states within a finite interval.
If a real system can depend in a macroscopically observable way on
how close it gets to (eg) an ionization energy, then chaotic behavior
might be observable in QM. How are the mathematical examples constructed?
The issue of chaos in the correpondence limits of quantum systems is a
hot topic. For those interested in the issue of quantum chaos, I
strongly suggest:
"Classical Mechanics, Quantum Mechanics, and the Arrow of Time"
T. A. Heppenheimer, Mosiac, Volume 20, No 2, Summer 1989, 2-11
Also, Rod Jensen has been doing work on the stadium problem in the
quantum domain. Very intersing stuff.
Still pondering nonlocality,
Albert Boulanger
BBN Systems & Technologies Corp.
aboulanger@bbn.combaez@x.ucr.edu (john baez) (04/15/90)
In article <54872@bbn.COM> aboulanger@bbn.com writes: >In article <965p02gf9cNw01@amdahl.uts.amdahl.com> kp@uts.amdahl.com (Ken Presting) writes: > Penrose does cite David Deutch, "Quantum thoery, the Church-Turing > pinciple, and the universal quantum computer", Proc. Roy. Soc. (1985) > A400, 97-117. Apparently, a quantum device can exhibit some of the > *speed* properties of a non-deterministic TM. As far as I know, there > is no (well-founded) suggestion that non-recursive functions can be > computed by these devices. Computing NP-complete things in polynomial time would be interesting and mildly believable, though I'd be inclined to believe that the NP nature would simply be pushed off into some other aspect. Someone at Princeton showed you could solve some NP complete problems fast using "mechanical computers" (imaginary machines made of gears and such), but I am inclined to believe that in this case the machines must be tooled with accuracy rapidly growing as a function of the size of the problem. I very much doubt that any real-world system can *repeatably* compute a non-recursive function. Of course, if quantum mechanics is truly random, alternately measuring an electron's spin along two orthogonal axes should produce a non-recursive sequence of bits. But this isn't a repeatable "calculation" in my opinion. Try out: John Baez, Recursivity in Quantum Mechanics, Trans. Amer. Math. Soc., {\bf 280} (1983), 339 - 350. Pour-El, Marian B. (Marian Boykan), 1928- Computability in analysis and physics / Marian B. Pour -El, J. Ian Richards. Berlin ; New York : Springer Verlag, c1989. > This is very interesting. Discreteness in the spectrum of energy states > is not by itself sufficient - there is no problem in having a denumerable > infinity of discrete states within a finite interval. To be more precise, quantum systems in bounded regions of space can be expected to have Hamiltonians with pure point spectrum, so their motion will be "almost periodic" in the technical sense, not chaotic. > If a real system can depend in a macroscopically observable way on > how close it gets to (eg) an ionization energy, then chaotic behavior > might be observable in QM. How are the mathematical examples constructed? That's right, chaos might appear near ionization (continuous spectrum), but systems in a "box" don't really have continuous spectrum. There could be some residual vestiges of chaos lurking about though if one could find a good mathematical way of identifying them. One typical bogus way of getting continuous spectrum for a quantum system in a bounded region is to take Schroedinger's equation on R^n and apply a map from R^n onto an open ball of finite radius, say, to get a differential equation on the open ball with continuous spectrum. One might also be able to do it by using potentials that are sufficiently nastily unbounded below. >The issue of chaos in the correpondence limits of quantum systems is a >hot topic. For those interested in the issue of quantum chaos, I >strongly suggest: > >"Classical Mechanics, Quantum Mechanics, and the Arrow of Time" >T. A. Heppenheimer, Mosiac, Volume 20, No 2, Summer 1989, 2-11 Arrow of time, oh-oh! :-)