Mel was Real

tag:blogger.com,1999:blog-8082954141980125536.post-883887995714591362008-04-30T10:16:00.007-04:002008-04-30T10:51:34.074-04:00Mel was RealThings have been pretty crazy around here, so no new posts recently, but this caught my attention. James Grimmelmann <a href="http://laboratorium.net/archive/2008/04/28/a_few_facts_about_the_lgp30">reports</a> a few interesting facts about the Librascope/Royal McBee LGP-30. Specifically, <a href="http://www.pbm.com/~lindahl/mel.html">Mel</a> was real, and the hexadecimal digits were 0 1 2 3 4 5 6 7 8 9 F G J K Q W! I can't resist telling a story. James is now a professor at the New York Law School, but he and I were fellow computer science students in college. He was a TA for the undergraduate introductory theory course when I took it, and his duties included, among other more enjoyable tasks, grading the first problem set. The “challenge” problem asked for a proof that in any group of six people, there is either a group of three that all know each other (a clique) or a group of three that all don't know each other (an anti-clique). I didn't see how to prove it*, so I just wrote a simple C program to iterate over all 215 possibilities and verify that the condition holds. I wrote something about using brute force and attached the C program to the problem set. This problem set was just a warm-up in proof techniques, but the course is all about what can and can't be computed by various systems. The pinnacle result, of course, is Turing's proof that some problems are uncomputable and Cook's definition of NP-completeness. In that light, my brute force proof ran against everything the course was trying to teach. James was the grader for that question. Next to the comment about brute force, he wrote “Wait until the NP-completeness unit, Mr. Brute Force” At the end, he added, “Very, very clever. Such tricks will not avail you much where this course is headed.” I didn't appreciate it then, but in hindsight I find it very funny. * Truth be told, I still don't see how to prove it. You're supposed to use the pigeonhole principle, and the details have been explained to me in the past, but I can never reconstruct them on demand. The exhaustive search still feels easier, though perhaps less enlightening.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8082954141980125536-88388799571459136?l=research.swtch.com'/></div>rschttp://www.blogger.com/profile/09576271159839887762noreply@blogger.com9