## Archive for the ‘**Popular science talks**’ Category

## Universal Computation Told in Quotes

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 extemiswith 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!

## Krig i den digitala världen — informationsteknologin som den nya fronten

Föreläsningar 11-13 november 2014 i Halmstad, Lund och Växjö i Folkuniversitets serie “I skuggan av krig — vetenskap och kultur före och efter skotten i Sarajevo” inom Teknik- och Naturvetarcirkeln.

Jag pratar om cyberkrig: vad det är, vad det inte är, och hur det fungerar. Föreläsningen innehåller lite teknologihistoria, olika scenarier för cyberattacker, lite om internets struktur och protokoller, och en minikurs i cybersabotage: hur man hittar lösenord, genomför ett fördelad överbelastningsangrepp samt kodinjicering.

Vidare läsning:

- En lättläst bok, på engelska, av tidigare ansvarig för landets säkerhet Richard Clarke: Cyber War (2010). Lite alarmistisk men i det stora ganska utmärkt, inte minst ur militärstrategisk och politisk synvinkel.
- Motsatta åsikten presenteras i Thomas Rids Cyber War Will Not Take Place (Oxford University Press, 2013) (har jag inte läst). Baserad på Rid (2012) Cyber War Will Not Take Place (PDF), Journal of Strategic Studies, 35:1, 5-32, DOI: 10.1080/01402390.2011.608939 (har jag läst).
- Alltid utmärkte Bruce Schneiers recensioner av dessa böcker samt mycket annat: Schneiers essays om cyberkrig.
- Det svenska totalförsvars forskningsinstitut FOIs sida om informationssäkerhet innehåller bl a en (lite alarmistisk) broschyr om Cyberattacker i praktiken (PDF).

## Democracy in the Digital Society (talk)

Talk given at the Association of Foreign Affairs, Lund. 22 November 2012.

### Abstract

Information technology impacts the foundations of democracy and the open society. For instance, algorithmic selection and filtering of information in search engines (Google) changes the forces underlying access to and control over information. Automatic and personalised news curation (the Filter Bubble) removes the open society’s prerequisite of an agora, *i.e.*, a public forum for discourse. Electronic voting (on the Internet, or even by mobile phone) changes the fundamental ritual of democratic institutions and is open to catastrophic abuse. Collaborative editing systems (Wikipedia, the open source movement) provides technological tools and social contracts for scalable and transparent conflict resolution.

### Related information

At least some of the issues covered in the presentation can be pursued using the following references:

- Wikipedia’s article about PageRank gives a good introduction to how Google’s original algorithm for ranking web pages works, and contains lots of good references for further reading.
- The most popular source for evangelism about the algorithmic news curation is Eli Pariser’s TED talk Beware online “filter bubbles”, based around his book
*The Filter Bubble: What the Internet Is Hiding from You*, Penguin Press (New York, May 2011) ISBN 978-1-59420-300-8. - The meme that “Code is Law” is coined by Lawrence Lessing, see for example Code is Law: On Liberty in Cyberspace in Harvard Magazine (2000) or Lessing’s homepage
- For more about the idea of programming as a civic virtue, see Douglas Rushkoff’s
*Program or Be Programmed: Ten Commands for a Digital Age*, Soft Skull Press (September 6, 2011). - Clay Shirkey’s TED talk How the Internet will (one day) transform government mentions many of the ideas about how to make the legislative process collaborative, scalable, transparent, and accountable by using ideas from the open source community.
- Democratic models based on graph algorithms for spectral ranking are from Boldi et al.,
*Viscous democracy for social networks*, Communications of the ACM, Volume 54 Issue 6, June 2011, pages 129-137.

## Impagliazzo’s Five Worlds on Swedish TV

In March 2012 Swedish TV recorded a popular science lecture of mine. It is now online.

I am an eager public speaker and have several crowd-pleasing talks that I can take off the shelf, say about how Google works. In March, I had the opportunity to record a lecture for Swedish TV’s educational channel *Utbildningsradion*. That audience is as “general” as it gets, so I wanted it to be broad and accessible. Something everybody immediately relates to. Something concrete and tangible.

What better choice than separation results for nonderministic polynomial-time computation? That’s right! In a fit of misguided ambition I decided to make a 20 minutes talks about honest-to-Karp theory of computation. P versus NP. Also, I did it in my fourth language: Swedish.

Here it is:

I haven’t had the guts to watch it yet, maybe I never will. But as far as I remember, it came out well.

Some comments:

- P and NP are the worst complexity class names ever invented, maybe the worst named concepts in all of science. I found it
*much*easier to talk about Impagliazzo’s five worlds and focus on the dichotomy between Cryptomania and Algorithmica. These are meaty, sexy, fuzzy concepts rich with association and*meaning*. This is what we should talk about to the public. P and NP are just very cold, different, specific, nerdy instantiations of the same basic question. - Puzzles are good when explaining algorithms and their absence. I have a bunch of these talks, using paper folding, sudoku, or (as in this case) tiling puzzles. It gives you something
*tangible*in a talk, and when you talk about something as abstract as computational complexity, you need all the tangibility you can get. - Science Fiction is our friend. I used various tropes from SF to ground the talk in a shared cultural space, and as an underlying theme. Here: the existence of hard artificial intelligence and the
*Singularity!*. (I always say*Singularity!*in a booming voice. Hence the italics and exclamation point.) - The Singularity focus (sorry,
*Singularity!*focus) was largely inspired by some transhumanistic alarmism on the blogs of Chalmers maths professor Olle Häggström (Okunnigt om artificiell intelligens och mänsklighetens framtid) and fantasy author R. Scott Bakker (The Posthuman Paradox). For some reason, the*Singularity!*exerts a strange attraction (ha!) on brilliant people like Olle and Scott. I simply can’t get myself worked up about it, and assume it’s simply the result of nonalgorithmic thinking that assails people who work in formal, possibly even quantitative, but nonalgorithmic settings. (Scott is a philosopher, Olle a statistician.) Alternatively, they could be right and I could be wrong. Still, it’s certainly fun to think about, and a great conduit for evangelising about algorithms to the public. The point of the talk is that the*Singularity!*is morally equivalent to P = NP. I think I manage to convey this point pretty well, given the constraints of the setting. In some sense, this is the maximally ambitious core of the talk. Neither Olle or Scott will be convinced by the argument, but the production values sure outshine their puny blog entries! Proof by intimidation. - I think I made the rhetorically correct decision of leaving the talk by moving the dystopias down to Earth in the end, with a bit of “algorithms are everywhere” internet evangelism.

In summary, the *Singularity!* is far. But then, the time-travelling nanobots paid me to say that, promising me a simulated eternity filled with cybervixens and Nutella.

Edit to add: I have been informed that I shouldn’t say “NP-hårt” in Swedish, but “NP-svårt.” Thanks, these things are beyond my linguistic intuition.

Related: Views of Impagliazzo’s Five Worlds.

## Views of Impagliazzo’s Five Worlds

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.

## Alan Turing Art (Talk at Malmö Konsthall)

The occasion is a current exhibition of Henrik Olesen, one of Denmark’s most important contemporary artists according to the programme.

My presentation is based on a talk I gave in the Fall 2010 Teknik- och Naturvetarcirkeln for *Folkuniversitetet*, but for the art museum I tone down the technical aspects and instead build the talk around a presentation of verious artworks featuring Turing, including:

*Some Illustrations to the life of Alan Turing*, 2008, 16 computer printouts on newsprint. This piece is part of the exhibition in Malmö.- Alan Turing memorial at Manchester, whose themes resonate well with Olesen’s
- Stephen Kettle’s Alan Turing at Bletchley Park.
- John M. Mill’s statue in Surrey.
- Eduardo Paolozzi’s series Turing Collection, see also Andrew Hodges’s comments.

There is more, including theatre plays, stamps, and scientific and political awards.

See you there!

## Alan Turing (talk)

Popular science talk about Alan Turing, father of Computer Science, intellectual giant of the 20th century, persecuted by his own government despite helping to win the war a few years earlier.

The talk describes the intellectual environment for Turing’s work, going back to the formalist endeavours of Russel and Hilbert and culminating in Turing’s definition of the “Univerval Machine,” known today as the Turing machine and the birth of the computer; the cryptoanalytic work of Turing’s group at Bletchley Park for breaking the German coding machine Enigma; and a brief appraisal of the role of Computer Science in today’s technological and scientific reality to establish the importance of Turing’s work.

- 5-7 October 2010,
*Alan Turing – människan som maskin*, Teknik- och Naturvetarcirkeln, lectures in Halmstad, Lund, and Växjö. In Swedish. - 19 January 2011, 19.00 Malmö Konsthall, lecture in connection with an exhibition of Danish artist Henrik Olesen. In Swedish.

**Further reading**

- At Wikipedia: Alan Turing, Enigma Machine, Foundational crisis of mathematics
- On Youtube: Turing Machine
- Hodges, Andrew (1983).
*Alan Turing: The Enigma.*New York: Simon & Schuster. A splendid biography of Turing. - Doxiadis, Papadimitriou, Papadatos, and Di Donna.
*Logicomix: An epic search for truth.*Very good comic about the foundational crisis of mathematics, focussing on Bertrand Russel.