Month: February 2015

Posted on

What was the most Geeky Event in History?

While I can’t get into the background here, I was recently asked to describe the most geeky event in history. Something like this is hard to bound and as I asked those around me I got lots of answers from moment the zero was invented (“without that, you got nothing”) to the first demo of the transistor (pretty good one) to the Trinity Test for the Manhattan Project. All of these were interesting, but “Geeky” implies not necessarily profound, but technical, funny, entertaining and weird. As I tried to put together my answers, I came up with the following goals:

  • geeky stuff is funny, so the moment should at least make you smile
  • geeky stuff is esoteric and should surprise and be a little weird to the general public
  • geeky stuff is technical; a geeky moment should be the culmination of a long technical slog and unveil a new tech in a novel way
  • geeky stuff is changing the world, so this moment should have at least a brush with history

So, I came up with four events: (1) A profound historical event, (2) A funny event, (3) a profound economic event, and (4) an tech awe-inspiring event.

The Profound Event

On 9 December 1932, 27 year old Marian Rejewski (a Polish mathematician) was given some German manuals and monthly keys for their Enigma. On top of his recently developed theory of permutations and groups, this enabled him to work out the Enigma scrambler wiring after he had the insight that the Nazi keyboard was wired to the entry drum, not in keyboard order, but in alphabetical order. He describes what happened next: “The very first trial yielded a positive result. From my pencil, as if by magic, begin to issue numbers designating the wiring”. By Christmas he was decoding nearly all German communications. Not only was this one of the greatest breakthrough cryptologic history, but it eventually resulted in the British capability listen to every conversation made between Germans. This played a big role in decimating a superior German Navy and Luftwaffe, and possibly swaying the war in favor of allies, in addition to starting the modern field of computer science.

The Funny Event

In the fall of 1971, the twenty-year-old Wozniak was inspired by Esquire to build a “Blue Box” that enabled him to create the 2600Hz tone to control the, then analog, phone network. He took the name “Berkeley Blue” while his 17 year old business partner Steve Jobs took the call sign “Oaf Tobar.” After a visit to the original phone phreak, Captain Crunch, and a short detainment by the Police, he decided to put his blue box to good use and do something both epic and geeky: crank call the Pope. Using his blue box he managed to route his call to the Vatican. “In this heavy accent I announced that I was Henry Kissinger calling on behalf of President Nixon. I said, ‘Ve are at de summit meeting in Moscow, and we need to talk to de pope.'” The Vatican responded that the pope was sleeping but that they would send someone to wake him. Woz arranged to call back in an hour.
Woz recalls, “Well, an hour later I called back and she said, ‘Okay, we will put the bishop on, who will be the translator.’ So I told him, still in that heavy accent, ‘Dees is Mr. Kissinger.’ And he said, ‘Listen, I just spoke to Mr. Kissinger an hour ago.’ You see, they had checked out my story and had called the real Kissinger in Moscow.”
Aside from the raw audacity required to prank world leaders, there is something very geeky about building a piece of hardware out of spare parts, mastering the world-wide phone system and roping in a key source of the modern desktop, desktop publishing, digital entertainment and mobile devices in the operation.

A Profound Geeky Economic Event

The moment when Dan Bricklin – wrote the original spreadsheet program, VisiCalc, on an Apple II. It is hard to overstate the impact spreadsheets have had on the modern economy and the PC industry . . . and it was written in assembler, which adds major geek cred.

Tech Awe-Inspiring Event

I’ve always been in awe of Von Neumann and his impact on science and defense technology. In particular, in May 1945, he hopped on a train from Aberdeen, Maryland to Los Alamos, New Mexico. At the time, he was solving some of the hardest problems on the Manhattan project and was traveling to go provide technical advise leading up to the trinity test. He had already established game theory, numerical analysis and a good bit of quantum physics. As a side project, he had just seen a demonstration of the ENIAC computer and had been asked to write a memorandum describing the project. I’ve written a lot of memos describing government projects, but von Neumann’s 101 page hand-written “The First Draft of a Report on the EDVAC” was finished by the time he arrived in Los Alamos. He mailed it to his colleague Herman Goldstine, who typed it up, got it reviewed, and published it the next month (without any patent). His memo described the architecture of the EDVAC, the follow-on to ENIAC which was to become the world’s first von Neumann machine and was the first published description of the logical design of a computer using the stored-program concept that formed the blue-prints for 50 years of computers.

Posted on

Halt!

You can’t work long in computer science until you have to understand the halting problem. The halting problem is concerned with determining whether a program will finish running or continue to run forever. It has a storied history. In 1936, Alan Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. His proof was made famous since in this paper, he provided a mathematical definition of a computer and program, which became known as a Turing machine and the halting problem is undecidable over Turing machines and is one of the first examples of a decision problem.

Programmers generally try to avoid infinite loops—they want every subroutine to finish (halt). In particular, in hard real-time computing, programmers attempt to write subroutines that are not only guaranteed to finish (halt), but are guaranteed to finish before the given deadline.

But isn’t it easy to avoid infinite loops? Why is the halting problem so important? Because a lot of really practical problems are the halting problem in disguise. For example, say you want a compiler that finds the fastest possible machine code for a given program. You have JavaScript, with some variables at a high security levels, and some at a low security level. You want to make sure that an attacker can’t get at the high security information. This is also just the halting problem. Or, for example, if you have a parser for your programming language. You change it, but you want to make sure it still parses all the programs it used to. This is one more example of the halting problem. If you have an anti-virus program, and you want to see if it ever executes a malicious instruction, this is another example of the halting problem in action.

Moreover, the Halting problem lets us reason about the relative difficulty of algorithms. It lets us know that, there are some algorithms that don’t exist, that sometimes, all we can do is guess at a problem, and never know if we’ve solved it. If we didn’t have the halting problem, we would still be searching for Hilbert’s magical algorithm which inputs theorems and outputs whether they’re true or not. Now we know we can stop looking, and we can put our efforts into finding heuristics and second-best methods for solving these problems.