The Nature and Limits of Computation: A Celebration of Alan Turing

As a figure of speech we sometimes describe advances in math and science as “celebrated results,” but rarely does that mean that an actual celebration took place. Well, this time we mean it.

Alan Turing (1912- 1954) is widely regarded as the “Father of Computer Science.” To commemorate the 100th anniversary of his birth, 2012 has been named the “Alan Turing Year.” In honor of his landmark contributions to science and humanity, events are being held throughout 2012 and across the globe. But you won’t have to travel far to be a part of the celebrations: within these pages of XRDS is our tribute to Alan Turing.

Turing was fascinated,
among many things, by
two questions: “What is the
nature of computation?”
and “What are the limits of
computation?” Turing, along
with his advisor Alonzo
Church, answered the
former with his development
of the Universal Turing
Machine and answered
the latter with his proof of
the undecidability of the
halting problem. Both of
these breakthroughs have
stood the test of time. (It is
astonishing that the Turing
machine is still one of the
basic models of abstract
computation since it
predates the modern digital
computer.)

—Arefin Huq, Issue Editor