cutrell@cogsci.ucsd.EDU (Doug Cutrell) (03/16/90)
In article <2475@quiche.cs.mcgill.ca> utility@quiche.cs.mcgill.ca (Ronald BODKIN) writes: >I am very curious as to whether or not current physics does or >does not describe functions which are turing computable... I know of two possible ideas from modern physics that may be of interest: 1) Truly non-computable equations: the equations of special relativistic quantum mechanics can be considered to do a sum over all possible pathways for events (the "Feynman integral"). The extension to general relativity would call for a sum over all possible space-time manifolds. It is known that the class of all four dimensional manifolds is not recursively enumerable (this is ONLY true for four dimensions). Therefore this sum would be formally non-computable. It is therefore possible that the equations of the "GUT" covering both QM and gravity are formally non-computable. 2.)Penrose has suggested that the crystal growth of pseudo-random crystals may violate Church's hypothesis. The growth of such crystals can proceed only via global interactions over the entire crystal -- each successive cell must know about all of the rest of the crystal. Penrose suggests that this may proceed via a quantum "non-deterministic" computation involving the collapse of the wave function describing the superposition of all possible crystal structures. It has been a point of contention as to whether such crystals are truly perfect non-periodic lattices, or simply disordered approximations to them. Recent atomic tunneling microscopy of these crystals supports the former -- the lattices appear to be in perfect non-periodic tiling. This may represent the first example of a physical phenomena which computes an exponentially complex function with linear or better analog resources. While I agree that this discussion has strayed afield of the AI mainstream, these results are still of relevance to the computational scientist. Although such matters are not relevant to present day computational possibilities, it is impossible to say how far away applications may be. ================================================= Doug Cutrell Dept. of Cog. Sci. D-015 UCSD La Jolla, CA 92093 cutrell@cogsci.ucsd.edu (internet)