In the words of George Bernard Shaw,

I often quote myself. It adds spice to my conversation.

The other day, while preparing a lecture on the impact of Alan Turing’s work, I had to opportunity to come up with the following deepism:

Nothing in information technology makes sense except in the light of universal computation.

—Thore Husfeldt, 2015

My formulation, of course, deliberately mimics a meme of evolutionary biology,

Nothing in biology makes sense except in the light of evolution.

—Theodosius Dobzhansky

from the eponymous essay ([Wikipedia]).

The claim I want to establish is that universal computation is to information technology what evolution is to biology: the single fundamental conceptual breakthrough that makes everything clear, and without which many phenomena become impossible to reason about.

The story about Turing’s result goes something like this: In the Olden Days, computation was domain-specific. Some of it was very sophisticated, and by the 19th century even programmable, such as the Jacquard loom or Babbage’s Analytical engine. But the insight of universal computation, formulated in Turing’s 1936 paper, comes only in section 6, mainly to give credence the validity of the computational model he just defined

It is possible to invent a single machine which can be used to compute any computable sequence.

A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc., 1936

To do this, Turing observes that the behaviour of a specific computational device (“the hardware”) can be turned into an algorithmic description and then fed as input to sufficiently strong other machine. By this conflation of “device”, “algorithm” and “data”, all computational models, provided they reach some minimal level of algorithmic power, are equally powerful (in a qualitative sense) in that they can simulate each other. The device operating Jaquard’s loom and Babbage’s analytical engine might as well be one and the same, namely the device we now call the universal computer. Bam!

In the Days of Yore, devices were appliances like washing machines and lawn mowers. They did one thing really well. But in the information age, there is only Turing’s universal computer

Like every conceptual breakthrough, once you’ve grasped it, it becomes mundane and trivial. Today, children have universal computers in their pockets (a smartphone), and the idea that of course this device is both a music player and a word processor and a calculator and a game is obvious.

To appreciate the change of mindset, consider what computer pioneer Howard Aiken said as late as 1956, two decades after Turing’s paper:

If it should turn out that the basic logics of a machine designed for the numerical solution of differential equations coincide with the logics of a machine intended to make bills for a department store, I would regard this as the most amazing coincidence that I have ever encountered.

Yet this is exactly how it turned out!

A splendid book that makes this point very strongly is Martin Davis’s Universal computation: The road from Leibniz to Turing. Highly recommended.

This is a good story, and I like telling it. In this framing, the contribution of Alan Turing stands next to that of Charles Darwin.

So there I was, eagerly preparing slides and rehearsing the timing of anecdotes for yet another public lecture about this – in fact, for a pre-premiere of the Turing drama The Imitation Game.

Alas, in the middle of my preparations, a trusted colleague pointed me to a paper by Copeland: B. Jack Copeland, “Unfair to Aiken”, IEEE Annals of the History of Computing, vol.26, no. 4, pp. 35-37, October-December 2004, doi:10.1109/MAHC.2004.36. It turns out that the Aiken quote above is taken grossly out of context—Aiken understood universal computation perfectly well and merely made a completely valid point about hardware optimisation!

Thus was a good story ruined for me.

So where to turn instead to find a solid demonstration of computational ignorance? Luckily, I had to look to further than in the news:

[W]e want to allow a means of communication between two people which even in extemis with a signed warrant from the home secretary personally that we cannot read? … My answer to that question is no, we must not.

David Cameron, January 2015

Thank you, David!

The problem with this statement, apart from the galling infringement of fundamental rights and a number of other points, is the technological incompetence: Encryption is an algorithmic process that requires the availability of merely some very basic computational fundamentals. Outlawing encryption is computationally equivalent to outlawing multiplication. Today we don’t have an appliance for e-mail (which Cameron could then, presumably, control from the government). Instead, we have a universal computer that does amazing things, including encrypted email.

Cory Doctorow phrased the question underlying the desires of people like David Cameron in a blog post a few years ago:

“Can’t you just make us a general-purpose computer that runs all the programs, except the ones that scare and anger us? Can’t you just make us an Internet that transmits any message over any protocol between any two points, unless it upsets us?”

Cory Doctorow, Lockdown: The coming war on general-purpose computing, 2011.

Well, no you can’t. Because Turing.

This angle fit my lecture perfectly, of course: The Imitation Game is a film about encryption and the struggle against totalitarianism and the fact that your own government may not have your own best interests at heart, so I was able to replace the slanderous Aiken quote with a current events angle that made Turing even more relevant!

I gave a popular science talk this morning about which computational world we live in. The main conceit was to couple the question about the existence of efficient algorithms for NP-hard problems to utopias in science fiction and the technological singularity. I think this worked out pretty well.

The talk was recorded by Swedish TV and will be broadcast somewhen during the Spring of 2012 on their education and facts channel Kunskapskanalen. Because of the potentially high impact I decided to apply a bit more spit and polish to the visual side of the talk. In particular, I made 5 posters to represent Impagliazzo’s five worlds of computation. These worlds provide a metaphor that I find more intellectually stimulating than the relatively stuffy formulation, “Is the complexity class P equal to the complexity class NP?”.

I think some of them came out well, even typographically. (Five points for guessing which typeface was used for Heuristica.) I hereby release them under the CC BY-SA 3.0 license; maybe somebody else can use them in a similar talk. The talk was in Swedish (or at least in whatever language I use to approximate Swedish); if an anglophone wants Kryptomanien changed to Cryptomania, or wants the PDFs, I’m happy to oblige.

Next up: mugs, mouse mats, lingerie, and a perfume series of five fragrances.

References

Five worlds of computation are from Russell Impagliazzo: A Personal View of Average-Case Complexity. Structure in Complexity Theory Conference 1995: 134-147. [online PS]

Image sources: The dice are by ed_g2s at Wikimedia Commons. HAL 9000 is by Cryteria at Wikimedia Commons.