Heidelberg Laureate Forum

As I write this column, I am in Heidelberg attending the first Heidelberg Laureate Forum (HLF). In short, this event is a convening of Turing, Fields, Nevanlinna, and Abel Prize honorees together with young researchers competitively selected from a large field of candidates. (For more details about HLF, see http://www.heidelberg-laureate-forum.org/.)

This inaugural Forum is sponsored by the Klaus Tschira Foundation, ACM, the International Mathematical Union, and the Norwegian Academy of Science and Letters. Six of our members, among others, were instrumental in organizing this Forum: ACM CEO John White, ACM Europe chair Fabrizio Gagliardi, ACM Europe Council member Gerhard Schimpf, Turing Award Committee chair Jennifer Chayes, and Turing recipients Juris Hartmanis (1993) and Joseph Sifakis (2007). Indeed, there are 27 Turing Award recipients here in Heidelberg participating in HLF.

The Forum, though not yet over, is already having an effect on my thinking about computability and computation. Giants in our field and in mathematics explored ideas of computability beginning many decades ago. I think of Gödel, Turing, Church, Scott, and von Neumann among many others who have wrestled with the question of decidability and its companion, computability. As a computer scientist and mathematician by training, but an engineer by profession, I struggle to bridge a cognitive gap I feel between the computing of a function and the behavior of large-scale systems such as the Internet and the World Wide Web, air traffic control systems, interactive computer games, and email services. It is one thing to ask whether there is a computation that will yield a specific number (for example, how many ways can you fold a piece of paper if limited to no more than N folds for some value of N?) and another to characterize what is being computed by an email service system.

Abstraction is a powerful tool that can reduce complexity sufficiently to render computable questions about the behavior of complex systems. Leonard Kleinrock’s work on the theory of networks of queues seems a fine example. Complex store-and-forward networks are reduced to their key skeletal components: traffic statistics, buffer space, capacity of links, and topology of nodes whose analysis yields estimates of delay and throughput in the form of averages or moments. Kleinrock’s famous Independence Assumption tamed complexity to yield useful results.

A recent announcement of an object called an amplituhedron (http://en.wikipedia.org/wiki/Amplituhedron) illustrates the power of abstraction. Without delving into details I do not understand well enough to articulate, suffice it to say this construct allows for the dramatically easier computation of the probabilities of fundamental particle interactions that had to be described earlier with a potentially unlimited number of Feynman diagrams (http://en.wikipedia.org/wiki/Feynman_diagrams). The amplituhedron abstraction simplifies the computation while apparently producing very accurate and testable results.

These observations reinforce in my mind the importance and power of well-chosen models and representations of problems. In mathematics, a change of variables can often reveal important symmetries or other properties inherent in complex problems that point the way to solution. Think about the difference in formulas that use polar coordinates rather then Cartesian coordinates for their expression. The former can often yield structural insights that, in the latter, are obscured.

These thoughts also lead me to wonder about the nature of quantum computation and whether there is more to this notion than merely the speeding up of conventionally computable results. A bit of Web searching yields the observation that classical Turing Machines can be related to Quantum Turing Machines (http://en.wikipedia.org/wiki/Quantum_Turing_machine) by means of stochastic matrices. Whether this means a classical Turing Machine can compute anything a Quantum Turing Machine can calculate is still unclear to me but I hope to find an answer at this Forum!

The HLF is a daring exploration into the relationship between computer science and mathematics, both of which have influenced one another over the course of several decades. I hope this exploration will continue at future Forums and that the insights derived by this process will stimulate new work by computer scientists and mathematicians. It may even result in the design of new kinds of computer architecture, taking advantage of the ideas exposed in this magical and historically significant city.

Oh, and if you get the chance, you should ask the attendees about the spectacular saxophone concert by four incredibly talented women presented during the opening ceremonies. The proceedings were recorded. If you like jazz, you will love the energy these performers generated!

Vinton G. Cerf, ACM PRESIDENT