Babbage Session 1-5/27/98
back to home
NOTE: these notes are incomplete and disorganized because they were reconstructed from a blackboard. In the future the attendees will be armed with laptops, and links from the main page for each session will include links to group members home pages.
Members include (in alphabetical order) Edward Boyden, Rich Devaul, Ebeth Haley, Yael Maguire, Bernd Schoner, Ben Vigoda.
What is computation? Over the course of the next month we'll discover current models and comprehend them, hopefully in physical terms.
Central to today's discussion was the concept of nonlinearity. It is believed by some members of the group that nonlinearity is essential to computation, although this has not been well-defined. The question of the resources of linear computation was raised, and it was resolved that the resources are polynomial (N2) in the dimension N of the system at hand. This precludes all NP-complete problems, for example, and therefore forbids universal computation.
A brief discussion of models of linearity ensued: orthogonality (wrt Gaussian/exponential/unity), bases, Jordan form, eigenvalues/modes/states/vectors, the matrix representation of beams of light (as processed by mirrors, lenses, etc.), systems theory, causality, hysteresis, quantum mechanics, the use of matrices and coefficients, wavelets, and time were all mentioned. The convenience of frequency and Fourier modes as a basis was mentioned. Time is unusual in that there is no time operator; canonical quantization gives no indication of the order of operations; the Dyson time-ordering operator from quantum field theory must be used to organize the structure of certain RQFT computations.
Another question that was raised was what a computation requires: one picture was that there is creation of a state, some processing, and readout, using finite resources (time, energy, precision, entanglement), following the rules of physics. Many languages for discussing computation were mentioned, including Turing machines, dynamics, recursion theory, complexity theory, automata theory, statistics; their extensions to quantum mechanics and neurobiology were also mentioned. We also mentioned some interesting dichotomies: discrete vs. continuous (e.g., discrete systems have spontaneous order in 2 dimensions or higher, but continuous systems have spontatneous order only in 3 dimensions or higher!), extensive vs. intensive vs. exponential, time vs. space, linear vs.nonlinear, active vs. passive, intentional vs. natural, entropic vs. extropic, reversible vs. irreversible, universal vs. specific, classical vs. quantum, deterministic vs. nondeterministic, and so on.
The question of dynamics arose. It was concluded that fundamental to computation is a notion of decision, or threshold, or comparator. In fact, the Kleene schemes suggest that these are essential, since the function that introduces the halting problem, Turing completeness, indecidability, etc. is the mu operator, which I'll discuss next time.
tr. by Ed Boyden
babbage@media.mit.edu· 20 Ames St· Cambridge, MA 02139 USA · 617.253.2383