Magazine: Spring 2012 | Volume 18, No. 3
2012 has been designated the "Alan Turning Year." Celebrations on both sides of the pond are being held to commemorate Alan Turing's legacy. His contributions to not only computer science, but society as well, are vast. In this special issue of XRDS, we explore what we mean by computation; consider the relevancy of Turing's work today; discuss computational complexity, while taking a detour into cryptography; and wrap up with what the future holds for computing. If Turing is the "Father of Computer Science,” we as his descendants must continue to push the boundaries of computing science.
Download
- Digital Edition web-based magazine available for subscribers – sign in
- PDF via ACM’s Digital Library
SECTION: Features
What is computation?
Our culture is in the process of renegotiating what it thinks computation and computer really mean.
By Ian Horswill
An interview with Robert Soare
University of Chicago's Robert Soare, the Paul Snowden Russell Distinguished Service Professor of Mathematics and Computer Science, offers his reflections on Alan Turing.
By Arefin Huq
Invitation to complexity theory
Complexity theory provides new viewpoints on various phenomena that were considered by past thinkers.
By Oded Goldreich
The tale of the PCP theorem
How the search for the limits of computing led to the discovery of the unexpected power of proofs.
By Dana Moshkovitz
Pseudorandomness and derandomization
The computational theory of pseudorandomness and cryptography.
By Luca Trevisan
Why now is the right time to study quantum computing
Quantum computing is not merely a recipe for new computing devices, but a new way of looking at the world.
By Aram Harrow
Future of computing
The intersection of biology and computer science is pushing computation beyond its traditional limits---forget algorithms think evolution.
By Dennis Shasha
Profile Dickie George
looking back on 40 years at the NSA
By Robert J. Simmons
SECTION: Online features
FREE CONTENT FEATURE
A conference to promote undergraduate research in the Arab World
By Qusay H. Mahmoud, May AlTaei, Leon Jololian