Archive for April, 2011

CS timeline voting: the results are in!

Thursday, April 28th, 2011

The top ten:

1. Euclid’s Elements: 116 votes
2. Turing’s “On Computable Numbers”: 110 votes
3. Gödel’s Incompleteness Theorem: 107 votes
4. Gödel’s P vs. NP Letter to von Neumann: 106 votes
5. George Boole’s Logic: 88 votes
6. Shor’s Algorithm: 88 votes
7. Wikipedia: 85 votes
8. Claude Shannon’s Digital Logic: 82 votes
9. PRIMES in P: 82 votes
10. Cook-Levin Theorem: 80 votes

The rest:

Al-Khwarizmi’s “On the Calculation with Hindu Numerals”: 79 votes
Bardeen, Brattain, and Shockley Invent Transistor: 79 votes
Babbage’s Analytical Engine: 77 votes
Tim Berners-Lee Invents WWW: 75 votes
Fast Fourier Transform: 73 votes
Brin and Page Create Google: 73 votes
von Neumann Architecture: 71 votes
RSA: 70 votes
Hilbert Calls for Mechanization of Mathematical Reasoning: 69 votes
Simplex Algorithm: 69 votes
Claude Shannon Formalizes Cryptography: 68 votes
Dijkstra’s Algorithm: 68 votes
Gaussian Elimination Described in Ancient China: 67 votes
Quicksort: 65 votes
UNIX and C: 65 votes
Newton’s Method: 64 votes
Leibniz Describes Binary Notation, Calculus Ratiocinator: 64 votes
First Program written by Ada Lovelace: 64 votes
Gauss’s Disquisitiones Arithmeticae: 62 votes
Monte Carlo Method: 62 votes
“Bit” Coined: 62 votes
TeX Typesetting: 62 votes
Ginsparg Creates arXiv: 61 votes
Kleene Invents Regular Expressions: 61 votes
McCarthy Invents LISP: 59 votes
“The Art of Computer Programming”: 59 votes
TCP/IP Protocol: 58 votes
Strassen’s Algorithm: 58 votes
PCP Theorem: 56 votes
Turing Test: 55 votes
Randomized Primality Testing: 55 votes
IP=PSPACE: 55 votes
Scott and Rabin’s Paper on Nondeterminism: 54 votes
Jacquard Loom: 54 votes
Colossus Begins Operation at Bletchley Park: 53 votes
Integrated Circuit: 53 votes
Chomsky Hierarchy: 52 votes
Pascal Builds Arithmetic Machine: 51 votes
First Genome Sequenced: 51 votes
Reed-Solomon Codes: 50 votes
Time Hierarchy Theorem: 50 votes
ARPAnet: 49 votes
Four Color Map Theorem Proved: 49 votes
Linux: 49 votes
Diophantine Equations Proved Undecidable: 46 votes
Feynman Suggests Quantum Computing: 46 votes
Deep Blue Defeats Kasparov: 46 votes
Solomonoff-Kolmogorov-Chaitin Complexity: 44 votes
Lempel-Ziv Data Compression: 43 votes
GPS: 42 votes
Marian Rejewski’s “Bombe” + Alan Turing’s Improvements: 41 votes
Diffie-Hellman Public Key Exchange Protocol: 41 votes
Zuse’s Z1: 40 votes
Viterbi Algorithm: 40 votes
First Email Message: 38 votes
Pseudorandom Generators: 37 votes
Oughtred Invents Slide Rule: 36 votes
FORTRAN: 36 votes
ENIAC: 35 votes
Semaphores: 35 votes
Gottlob Frege’s “Begriffsschrift”: 34 votes
Grace Murray Hopper Creates A-O Compiler: 34 votes
Conway’s Game of Life: 34 votes
Xerox Parc’s Alto With First GUI: 33 votes
Kuttaka Algorithm from Ancient India: 32 votes
Scientific Computing During Manhattan Project: 30 votes
Wilkes, Wheeler, and Gill Define Closed Subroutines: 29 votes
Stroustrup creates C++: 28 votes
Zimmermann creates PGP: 28 votes
Dartmouth Conference Popularizes Term “AI”: 27 votes
Moore’s Law: 27 votes
Boosting in Machine Learning: 27 votes
Codd Proposes Relational Databases: 26 votes
Ethernet Invented: 26 votes
Valiant Proposes PAC-Learning: 26 votes
Stallman Writes GNU Manifesto: 25 votes
Wiesner Proposes Quantum Money and Multiplexing: 24 votes
Antikythera Mechanism: 23 votes
BitTorrent: 23 votes
Low-Density Parity Check Codes: 23 votes
McCulloch and Pitts’ “A Logical Calculus Immanent in Nervous Activity”: 22 votes
Engelbart and English Invent Mouse: 22 votes
Dijkstra’s “Go To Statement Considered Harmful”: 22 votes
Back-Propagation: 22 votes
MIT SAGE Creates First Large-Scale Computer Network: 21 votes
Vannevar Bush Creates First Large-Scale Analog Calculator: 20 votes
IBM Introduces Hard Drive: 20 votes
Checkers Solved: 20 votes
First Packet-Switching Network: 20 votes
Atanasoff and Berry’s Vaccum-tube Computer: 19 votes
Vannevar Bush’s “As We May Think”: 19 votes
Hollerith’s Electromechanical Counting Machine: 18 votes
MIT Builds First Time-Sharing System: 18 votes
First Computer Virus: 18 votes
IEEE Floating-Point Standard: 18 votes
IBM PC: 18 votes
“Spacewar!”, First Computer Game: 17 votes
RISC Architecture: 17 votes
Intel’s 8086: 17 votes
al-Jazari’s Water Clocks and Musical Automata: 17 votes
Edward Lorenz (Re)discovers Chaos Theory: 16 votes
Apollo Guidance Computer: 16 votes
CAPTCHAs: 16 votes
VC Dimension: 16 votes
Macsyma    Computer Algebra System: 15 votes 15 votes
UNIVAC I: 13 votes
DaVinci Surgical Robot: 13 votes
Mark II Incident Popularizes Word “Bug”: 12 votes
Weizenbaum Creates ELIZA: 12 votes
ASCII: 11 votes
TI Handheld Calculator: 11 votes
Simula 67: 11 votes
MIT Whirlwind I Displays Graphics: 10 votes
Sketchpad, First CAD Software: 10 votes
NCSA Mosaic: 10 votes
Robert Morris’ Computer Worm: 9 votes
Pixar Releases “Toy Story”: 9 votes
Stuxnet Worm: 9 votes
IBM System/360: 8 votes
Mac Hack Chess Program: 7 votes
Microsoft Windows: 7 votes
Sojourner on Mars: 7 votes
BASIC: 6 votes
Apple Macintosh: 6 votes
SETI@home: 6 votes
IBM’s Watson Wins At Jeopardy!: 5 votes
Atari’s Pong: 4 votes
Atlas Computer in Manchester: 4 votes
Norbert Wiener Founds Cybernetics: 3 votes
First ATM in Tokyo: 3 votes
Youtube Launched: 3 votes
VisiCalc: 2 votes
Jevon’s Logic Piano: 1 vote
Apple II: 1 vote
Adobe PostScript: 1 vote
SABRE Travel Reservation System: 0 votes
Fischer-Lynch-Paterson Theorem: 0 votes
Facebook, Twitter Use in Egypt Revolution: 0 votes
First Machine Translation Demonstration: -1 vote
Usenet: -1 vote
Akamai: -2 votes
TX-0: -3 votes
CDC 6600: -3 votes
Compact Disc Invented: -3 votes
Aiken’s Mark I: -4 votes
CM-1 Connection Machine: -4 votes
Whirlwind I Displays Graphics: -5 votes
Floppy Disk Invented: -6 votes
MITS Altair Microcomputer and Microsoft BASIC: -6 votes
Axelrod’s “The Evolution of Cooperation”: -7 votes
Microsoft Office: -7 votes
Pentium FDIV Bug: -7 votes
EDSAC: -8 votes
UNIMATE, First Industrial Robot: -9 votes
CLU Programming Language: -9 votes
1ESS Switching System: -11 votes
UNIVAC Predicts Presidential Election: -12 votes
Stanford Arm: -13 votes
“2001 A Space Odyssey” Introduces HAL: -15 votes
“Spam” Coined: -16 votes
First Denial-of-Service Attack: -17 votes
Y2K Bug: -18 votes
Facebook Launched: -18 votes
Nintendo’s Donkey Kong: -19 votes
“Robot” Coined: -21 votes
CSIRAC    -21
Apple’s iPhone: -21 votes
Slashdot: -27 votes
Godwin’s Law: -29 votes
Asimov’s Three Laws of Robotics: -32 votes -34 votes
de Vaucanson’s Mechanical Duck: -39 votes
von Kempelen’s Mechanical Turk: -52 votes

A few comments:

  1. It’s (just-barely) conceivable that the results could have been slightly skewed by the quantum- and complexity-loving readership of this blog.
  2. Voters really didn’t like fiction/pop-culture references, mechanical contrivances, or anything that sounded like a publicity stunt.  They were much keener on conceptual advances (even to the extent of putting Gödel well ahead of the transistor).

I need to catch a plane to give the Buhl Lecture at Carnegie Mellon tomorrow, so I’ll leave you to draw any further conclusions.

Three museum reviews

Thursday, April 21st, 2011

The American Museum of Natural History has two temporary exhibits that are drawing large crowds.  One, Brain: The Inside Story, I can attest is worth a visit the next time you’re in NYC.  From the New York Times review, I’d been worried that the exhibit would be full of la-de-da generalities: “how marvelously complicated is the brain!  how little we understand about it!”  But it turned out that was just the review.   The exhibit itself does a pretty good job of summarizing what’s known about how the brain is organized, how it develops, how various drugs affect it, and more.  One highlight for me was a model brain that you can take apart to see how the brain stem, limbic system, and cerebral cortex fit together—something that 2D images had never successfully conveyed to me.  The other exhibit, The World’s Largest Dinosaurs, was sold out for the entire day when we tried to go there, so we had to content ourselves with the smaller dinosaurs in the rest of the museum.

The Mark Twain House and Museum in Hartford, Connecticut, should be avoided at all costs.  On a recent visit, I and my family of Twain fans were snidely turned away since we hadn’t booked a tour—a requirement buried in the website, which someone googling for the opening hours would almost certainly miss.  (This despite the fact that the museum wasn’t crowded, and we could have easily joined a tour that was starting as we arrived.)  So don’t suffer the petty bureaucrats who curate Twain’s legacy, and treat the town of Hartford the way they’d apparently like you to: as a bathroom stop along the highway from New York to Boston.  Twain would’ve been amused. Jeffrey Nichols, Executive Director of the Mark Twain House, left me a personal apology in comments section.  I thank him warmly for that, and maybe I will visit again sometime—though it will help if I have some way of knowing I won’t just be turned away again! 🙂

The Yad Vashem Holocaust History Museum in Jerusalem has been redesigned since the last time I was there, in 2002.  In the old Yad Vashem, you walked around more-or-less randomly looking at the exhibits; in the new one, you proceed in a more linear order (similar to the US Holocaust Memorial Museum in Washington DC): from the rise of Nazism to the first anti-Jewish laws to the ghettoes to the gas chambers and crematoria.  The tour ends powerfully, with the Hall of Names (a large circular room with photos of victims and bookshelves of data about 3.8 million of them), followed by a balcony with a spectacular view of West Jerusalem—as if the building itself is trying to explain why the country it’s in exists.  I recommend a visit, even if you’ve been to Yad Vashem before its redesign in 2005.  But be careful to check the opening hours: the first time my family and guests tried to visit, the museum was closing, we were turned away, and we ended up going instead to a rest stop full of Elvis statues, where people lined up to use the bathroom and bought Elvis t-shirts.  (I thought that belonged in some anthology of Jewish humor.)

Summary: While the world’s museums have a great deal to teach us, they ought to devote more of their attention to the fundamental tasks of being open and letting people in.  People turned away from a museum are not just lost customers: they’ve often spent hours getting to an unusual place, and may be so annoyed by the wasted trip that they won’t want to return, even if they have the opportunity to do so.  In two of the cases above, I checked the website beforehand and that didn’t suffice, since the key information I needed wasn’t there or was buried.  Yeah, I suppose I could call ahead before every museum visit, but I hate doing that.  If someone wants to start, it could be a fantastic way to not make any money.

Top 150 computer science events to be decided once and for all

Monday, April 11th, 2011

Today I break Shtetl-Optimized‘s long radio silence with a relatively-exciting announcement: you remember my timeline of computer science history?  Well, MIT students Jason Zhu and Ammar Ammar have now kindly created a website where you can vote on each of the entries, as well as new entries suggested by commenters.  It’s pretty simple: you just register (by entering an email address, username, and password), then upvote each entry you like and downvote each entry you dislike (you can also abstain on any entry).

The voting site arrives just in time for the MIT symposium “Computation and the Transformation of Practically Everything”, which is happening today and tomorrow.

For reference, here are the 17 new contenders added by popular demand:

150BC Chinese text describes Gaussian elimination
499 Indian mathematician Aryabhata describes the “kuttaka” algorithm for solving Diophantine equations
1206 al-Jazari builds elaborate water clocks and musical automata
1801 The Jacquard loom uses punched cards to control textile manufacturing
1951 Wilkes, Wheeler, and Gill describe the concept of closed subroutines
1956 Stephen Kleene invents regular expressions
1962 The Atlas computer begins operation in Manchester
1962 Robert Gallager introduces low-density parity check codes
1968 First deployed packet-switching network
1969 Strassen’s algorithm for fast matrix multiplication
1969 Stephen Wiesner conceives of quantum money and multiplexing
1971 Vapnik and Chervonenkis introduce VC dimension
1982 PostScript
1992 The PCP Theorem
1999 SETI@home
2006 DaVinci surgical robot performs the first unaided operation
2007 Checkers solved

Update: A new feature has been added that lets you rank four randomly-selected entries—click “Done” on the bottom of the page to access it.

Update: You can now undo a vote by clicking twice on the same arrow.