From: David A Molnar Subject: Re: Math as Science (Math as processing?) Date: 3 Dec 2000 19:37:50 GMT Newsgroups: sci.math,comp.theory Summary: [missing] In comp.theory Mike N. Christoff wrote: > David A Molnar wrote in message > | Heh. Although dealing with that from the point of view of complexity > | theory seems to require dealing with real-valued Turing machines > | (if x is in R). Which I don't understand very well yet... > | > I didn't know real-valued TMs existed. Do you have any links? I'd be > interested to read up on them. The theory I have in mind is due to Blum, Shub, Cucker, and Smale. They have a book from Springer-Verlag called "Complexity and Real Computation" which systematically develops the theory and shows its application to questions like "is the Mandlebrot set decidable?" "what is the complexity of the Nullstellensatz?" and the ever popular "so, what about that linear programming problem, eh?" http://www.wargaming.net/Programming/48/Complexity_Real_Computation.htm has a link to the amazon page. A manifesto is online and linked from http://citeseer.nj.nec.com/blum95complexity.html A workshop on the subject is profiled at http://www.cs.rhbnc.ac.uk/events/realwork.shtml This isn't the only branch of complexity theory to deal with real numbers; there's several results in Algebraic Complexity Theory which deal with the exact difficulty of computing polynomials over various fields, including R. The reference for that is either the book by Borodin and Cook or the Burgisser, Clausen, Shokrollahi _Algebraic Complexity Theory_. These aren't usually framed in terms of Turing machines, though; they are more often phrased in terms of circuits. There's also a formalism for complexity on real-valued functions which was worked on by Du I-Ko, Harvey Friedman, and others. I don't know much about it or if it's absorbed by the Blum, Shub, Cucker, and Smale formalism. -David Molnar