Mail to a friend · Print this article · Previous Columns 
Tony PhillipsTony Phillips' Take on Math in the Media
A monthly survey of math news

This month's topics:

Math on the Wild Side

Olivia Judson's weekly New York Times blog "The Wild Side" is being taken over for three weeks by the Steven Strogatz of Cornell, who refers to himself as "(gasp!) a mathematician." Strogatz has posted two columns so far, on May 19 and May 26, 2009.

 

"Intimidatingly awesome" knot theory project

Last April 7 Cory Doctorow posted on the "boingboing" blog ("a directory of wonderful things") an item with a link to Sana Raoof's presentation of her Intel-award winning project, "Computation of the Alexander-Conway Polynomial on the Chord Diagrams of Singular Knots." Ms. Raoof, then a Senior at Jericho High School on Long Island, now at Harvard and presumably a Sophomore, won an Intel Foundation Young Scientist Award at the Intel International Science and Engineering Fair in Atlanta, May 2008. Her amazingly articulate 3-minute presentation sketches her result (the Delta-polynomial, the formal logarithm of the Alexander-Conway polynomial, can be used as a complete invariant of singular knots whose chord diagram is a complete bipartite graph -- see Michael Luby's explanation on the NSF-supported National Science Digital Library website) and emphasizes possible applications to the biology of tangled molecules. Sana Raoof is in fact awesome, and worth watching.

Beyond Turing machines

Nature for May 20, 2009 carries a "News and Views" piece by Philippe Binder (University of Hawaii, Hilo and Kavli Institute) entitled "Computation: The edge of reductionism." The question is: to what extent can the behavior of a physical system be computed, e.g. modeled accurately on a digital computer? It is motivated by the recent publication of "More really is different" by Gu, Weedbrook, Perales and Nielsen (Physica D 238 835-839) which proves "that many macroscopic observable properties of a simple class of physical systems (the infinite periodic Ising lattice) cannot in general be derived from a microscopic description." Binder goes over the distinction between irreducible and undecidable systems, taking up work of Stephen Wolfram. A system is reducible if there is a mathematical shortcut, for example a closed formula, predicting its behavior (Binder mentions the cosine function for a simple harmonic oscillator). As an example of an undecidable system Binder gives the 1-dimensional cellular automaton "elementary rule 110" ("two states are allowed ('0' or '1'), and any cell will evolve to 0 if either its state and that of its right-neighbour cell are 0, or if its state and those of both its immediate neighbours are 1 -- otherwise it will evolve to 1.") with a very simple program but with the property (established by Wolfram and Matthew Cook) that it is universal (equivalent to a Turing machine), so as a system it is indecidable. What Gu et al. have achieved is to map an undecidable cellular automaton onto a physical model (an infinite, periodic Ising system) and to deduce that the long-term behavior of that system is also undecidable.

One does not often encounter "Alas" in Nature but here it is: "Alas, their results apply only to infinite lattices, and hence seem of limited use." Nevertheless Binder is optimistic "that finite objects may, after all, have undecidable properties." One of the hints he sees is related to work of Lenore Blum, Stephen Smale, and Mike Shub (Bull. Amer. Math. Soc, 21 1 (1989)), which describes computations over the real numbers.

Tony Phillips
Stony Brook University
tony at math.sunysb.edu