Crossroads
The ACM Magazine for Students
SPRING 2012 VOL. 18 • NO. 23
The Legacy of Alan Turing: Pushing the Boundaries of Computation
begin
features
end
03 LET TER FROM THE EDI TOR
04 INBOX
08 FEATURE
What is Computation?
By Ian Hor wsill
43 HELLO WORLD
Simulating a Turing Machine
By Malay Bhattacharyya
05 INI T: ISSUE IN TRODUC TION
The Nature and Limits of
Computation: A Celebration of Alan
Turing
By Arefin Huq
06 BENEFIT
ACM Student Chapters
By Daniel Gooch
06 ADVICE
Public Relations for Computer
Science Students
By Vaggelis Giannikas
07 UPDATES
Spreading Knowledge: Talks
and Lectures from ACM Student
Chapters
By Ben Deverett
15 INTERVIEW
An Interview with Robert Soare
By Arefin Huq
18 FEATURE
An Invitation to Complexity
By Oded Goldreich
23 FEATURE
The Tale of the PCP Theorem
By Dana Moshkovitz
27 FEATURE
Pseudorandomness and
Derandomization
By Luca Trevisan
32 FEATURE
Why Now is the Right Time to Study
Quantum Computing
By Aram Harrow
46 LABZ
Bletchley Park
By Vaggelis Giannikas
47 BACK
Turing’s Bombe
By James Stanier
49 EVENTS
51 POINTERS
51 ACRONYMS
52 BEMUSEMENT
Cover Illustration by James Joyce
38 FEATURE
Future of Computing: Inspiration
from Nature
By Dennis Shasha
40 PROFILE
Dickie George: Looking Back On 40
Years at the NSA
By Robert Simmons
The cover is inspired by Alan Turing’s Bombe, an
electromechanical device used by British cryptologists
to decipher German Enigma-machine-encrypted signals
during World War II. The drums mounted on the front panel
of the Bombe are illustrated in detail.
