Thore Husfeldt

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:

• Utopier i Science Fiction och Datavetenskap

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:

1. 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.
2. 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.
3. 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.)
4. 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.
5. 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.

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.

Henrik Olesen, from Some Illustrations to the life of Alan Turing

• Current programme at Malmö Konsthall, including talk venue and time

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!

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.

The question in this talk is, What can we compute? Today? Tomorrow? Will it be like science-fiction? If so, which one? 

The talk is aimed at a lay audience. If you have a degree in computer science, it will bore you to tears.

• Fantasticon 2009, Science Fiction convention in Copenhagen, 30 August 2009

Regel 30 – om cellulära automater i naturen och vetenskapen

The pattern on the seashell Conus Textile is similar to the output of a cellular automaton

Cellular automata are a basic computational model from theoretical computer science that model the behaviour of many natural processes, such as the pattern on the seashell Conus Textile. They are a beautiful and very accessible example where apparent complexity emerges from very simple rules.

Cellular automata were popularised in Stephen Wolfram’s problematic book A New Kind of Science and have inspired several modern artists. Norwegian artist
Kristoffer Myskja’s contribution to the biannual exhibition Electrohype of computer based art in Malmö is a mechanical representation of an automaton called Rule 30 in wood, paper, and metal. I take perverse pleasure from seeing it in action!

My talk starts with a description of Myskja’s piece and becomes a friendly introduction to computability theory.

• 10 december 2008. “Electrohype 2008” Fifth Biennial for Computer Based Art, Malmö Konsthall. Del av föreläsningsserien “Summen är större än helheten.”

Siden 1995 har vi fundet det, vi leder efter, ved bare at skrive et søgeord ind i Google, selvom ordet forekommer på milioner af sider. Hvordan virker det?

Et søgeord som «Einstein» forekommer på milioner af sider på internettet. En søgemaskine, som bare finder alle de sider, som indeholder ordet, er derfor ikke til nogen hjælp — det ville tage flere år for brugeren at gennemlede milioner af sider. Googles algoritme, som hedder PageRank, blev opdaget (og patenteret) i 1995 og er selve kernen deres service. Dens vigtigste funktion er først og fremmest at rangere information i stedet for bare at finde den. Google har ændret vores måde at håndtere og kategorisere information på, og er derfor et af civilisationshistoriens store omvæltninger. Jeg vil forklare, hvad PageRank gør og give et kort overblik over internettets historie. Hvordan brugte man webben fx i efteråret 1994?

Foredraget er rettet mod alle, der har brugt en søgemaskine som Google. Det tager en lille time med omtrent 45 billeder, men kan tilpasses.

• Forskningens døgn 2010, diverse foredrag i Hovedstadsområdet, 23/4-24/4 2010
• 10 oktober 2008 (Københavns kulturnat) ITU.
• 13 november 2008, for 9-klasses elever, “pigepraktikdagen” på ITU.

Videnskaberne under den algoritmiske linse

Algoritmisk tænking påvirker i dag videnskaber fra sociologi til kvantemekanik. Virkeligheden er information, og algoritmer er de kræfter, der påvirker den.

Datalogi har overtaget matematikkens rolle som videnskabernes dronning og tjenerinde. Det sidste er klart: alle videnskaber er blevet til anvendere af informationsteknologi, så algoritmer er blevet den store problemløser. Det vil jeg ikke tale om. I stedet vil jeg tale om, hvordan den algoritmiske linse giver et nyt perspektiv på virkeligheden. Som alle linser giver den mulighed for at stille skarpt på noget nyt. Foredraget består af en række eksempler på, hvordan algoritmer forklarer fænomener, vælger modeller, stiller spørgsmål, designer eksperimenter, og udfordrer hypoteser i ikke-datalogiske videnskaber.

Foredraget er henvendt til en lytterskare med en vis interesse for videnskab, men ikke nødvendigvis hård naturvidenskab. Det tager en god time med omtrent 60 billeder, men kan tilpasses.

• Naturvetenskaperna under den algoritmiska linsen. 2 september 2007. Kårhuset, Lund.
  Introduktion till naturvetenskaperna för novischer på Lund universitets naturvetenskapliga program.
• Från sociala nätverk till kvantmekanik – ett algoritmiskt perspektiv på vetenskaperna.
  27 november 2007. Hallands nation, Lund.

En linneansk resa från taxonomiberäkning till beräkningstaxonomi

Om beräkningsbiologi med utgångspunkt i linneansk taxonomi.

• 6 juni 2007. Botaniska trädgården, Lund; del av en serie sk “linnéföredrag” i samband med linnéfirandet på nationaldagen.

Varför har du inte fler vänner?

Om sociala nätverk med fokus på “världen är liten”-fenomener.

• 2007. Lunds universitet. Naturvetenskap, medicin, och teknikdagar för gymnasieelever.