When a lake freezes over, how do trillions of randomly oriented
water molecules know at almost the same time to align themselves into
crystalline form? Similarly, when iron becomes magnetized, how do trillions of
atoms know to align themselves almost instantly?
The best-studied model in science to discuss these phase changes and,
indeed, a wide variety of changes in state (neural networking, protein
folding, flocking birds, beating heart cells, questions of economics, and
more) is the Ising Model, developed by Ernst Ising in 1926 as part of his
Ph.D. dissertation.
Now computational biologist Sorin Istrail at the Department of Energy's
Sandia National Laboratories has shown that the solution of Ising's model
cannot be extended into three dimensions for any lattice, and so exact
solutions can never be found.
Ising conceived of a linear chain, composed of particles like little
magnets able to take an up or down position. The position of each magnet
influences the positions of the magnets bordering it. The conception was
expanded almost 20 years later into two-dimensional lattices of upward or
downward magnets (actually magnetic moments or spins), each magnet influencing
the behavior of magnets near it. The lattice had a wider application in the
material world than the simpler chain.
The model also can be expanded into three dimensions and its properties
figured out numerically with a high degree of accuracy. But not exactly. Not
for the general case. As opposed to the known mathematical solutions for one
or two dimensions, no one has been able to find an exact solution to any
three-dimensional lattice problem in terms of elementary equations you could
look up in a math book.
Yet the continued application of Ising's model -- more than 8,000 papers
published between 1969 to 1997 -- has tempted many scientists to extend the
grid's usefulness by developing a proof in three dimensions, the realm in
which most real-world problems take place. (...)
Other researchers who have tried read like a roll call of famous names
in science and mathematics: Onsager, Kac, Feynman, Fisher, Kasteleyn,
Temperley, Green, Hurst, and more recently Barahona.
Says Istrail, "What these brilliant mathematicians and physicists failed
to do, indeed cannot be done." Istrail, who has just taken entrepreneurial
leave from Sandia to accept the position of Senior Director of Informatics
Research with Celera Genomics Corporation, says his paper will be published in
May in the Proceedings of the Association for Computing Machinery's (ACM) 2000
Symposium on the Theory of Computing. (...)
To prove that the solution could not be extended, Istrail resorted to a
method called computational intractability, which identifies problems that
cannot be solved in humanly feasible time. There are approximately 6,000 such
problems known in all areas of science. Because they are all mathematically
equivalent to each other, a solution to one would be a solution to all -- an
infeasible result.
Says Istrail, "I showed the Ising problem, for any lattice, is one of
these problems. Therefore, it is computationally intractable."
As for Ising, whom Istrail describes as "a genius," the young
German-Jewish scientist was barred from teaching when Hitler came to power.
The modeler was restricted to menial jobs and, though he survived World War II
and taught afterwards in the United States, never published again.
