Talk given at the GoCAS workshop Existential Risk to Humanity, Gothenburg, 7 Sep 2017.
Talk given at the GoCAS workshop Existential Risk to Humanity, Gothenburg, 7 Sep 2017.
Föredrag den 20 september 2016 i Sällskapet Heimdall, Malmö.
Föredrag den 28 februari 2017, arrangerad av Lund Sustainable Engineers and Code@LTH, 12.15–13.00, LTH, Lunds Universitet, E-huset, E:A (eller E:B).
Under föredraget hoppas jag att bl a kunna förklara hur olika former för artificiell intelligens fungerar – hur bygger man en schackdator och hur en pratbot, hur fungerar maskininlärning i motsättning till god, gammaldags symbolisk AI, hur fungerar maskinöversättning baserad på stora datamängder, vad är ett artificiellt neuronnät, etc.
Är några av dessa tekniker en bit på vägen till artificiell generell intelligens? Och hur ser en värld med artificiell superintelligens ut? Kan och bör vi skydda os? Hur?
Lite AI-historia blir det nog också, så både Ada Lovelace, Jon von Neumann och Alan Turing kommer at nämnas.
Perspektivet är algoritmteoretisk och kunskapsoptimistiskt.
In the words of George Bernard Shaw,
I often quote myself. It adds spice to my conversation.
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.
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!
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.
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.
At least some of the issues covered in the presentation can be pursued using the following references:
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.
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.
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]