Hard Problems and How To Figure Them Out

Explained using only the ten hundred words people use most often.

What is a good way of figuring out a problem?

First: it must be so simple and clear that we can explain it to a computer. (Or a Human. That’s not so different.)

Second: it must be fast enough so that it is done before lunch. (Or before the sun burns out. that’s not so different.)

Since people started using computers, lots of people get paid to think about ways to figure out problems. that’s what i’m doing.  Today we understand that some problems are hard, and others are pretty easy.

I want to help us becoming better at talking about what makes a problem hard.

So far, most of the people who think about this stuff look only at the size of the problem.

But some of us feel that you can think more clearly about problems when you not only look at their size, but at some other things as well. Sometimes, this way of thinking even helps us to come up with better ways to figure out problems!

 

small1.png

small2.pngsmall3.png

Two other people and myself have come up with a way to finish the game for all five-letter words — as long as you are forced to visit only around ten words. Or maybe twenty. So we found out that the number of words all-in-all was not so important. instead, what makes the problem hard is how many you are forced to visit. We can even find the shortest such path!

small4.png

Read more here: Another man, myself, and a woman, ‘Shortest path through stuff you didn’t choose’, place where people who care about this kind of question meet each year (the name sounds like a soft drink),  year twenty-hundred and ten and two.


Appendix

The above is a summary of a poster I made for a research sharing day at ITU.

hard-problems-poster (draft) in pdf (designed for printing in A0)

I loathe poster sessions, partly because of the unclear concept of who the audience is, and mainly because the social interaction exhausts me.

But to motivate me I gave myself the challenge to design a poster in the style of  Randall Munroe’s Up-Goer Five: Use only the 1000 most used words of English, be concrete, whimsical, accessible, and informative. Munroe has since made a whole book in this style: Thing Explainer, which is quite lovely.

I did the whole thing in Omnigraffle Professional 5, which is hard pressed to handle a document with almost 6000 elements. Drawings are free-hand in Keynote (basically because I don’t have a good way of digitising my free-hand drawings — I am a competent artist, but Munroe’s style is sufficiently simple.) The font is xkcd-font from the iPython project, licensed under CCANC 3.0.

As a starting point I used a 2012 paper of Andreas, Nina, and myself that presents an efficient FPT-algorithm for shortest Steiner cycle. That’s as accessible a result as I have. The big drawing at the end shows a path from TEARS to SMILE passing through seven intervening emotions (WORRY, SPITE, etc.) This is a highly nontrivial result and a cute story that I’m insanely happy with, I haven’t found a good way of expressing this fact in only 1000 words.

Andreas Björklund, Thore Husfeldt, and Nina Taslaman, Shortest cycle through specified elements, Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms (SODA 2012),  January 17–19, 2012, Kyoto, Japan, SIAM, pages 1747-1753. [PDF].

Artificiell intelligens – ett hot mot mänskligheten?

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).

480px-hal9000-svgSammanfattning: Nej.

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.

Referenser:

  • Olle Häggström, Here Be Dragons – Science, Technology and the Future of Humanity, Oxford University Press, 2016. [Hos förlaget.] [På Olle Häggströms blog]
  •  Nick Boström, Superintelligence, Oxford University Press, 2014. [Hos förlaget]
  • David Deutsch, »Creative blocks«, Aeon Magazine, oktober 2012. [Onlineartikel]
  • »AI och existentiell risk«, samtal med Olle Häggström och Dag Wedelin (datavetenskap, Chalmers), 16 april 2016. [Online på UR Play]
  • Alan M. Turing, »Computing machinery and intelligence«, Mind 59:433–460, 1950.
  • Thore Husfeldt, »Monstret i Turings bibliotek«, Filosofisk tidskrift 36(4):44-53, 2015. [Engelsk översättning på min blogg]

Løsning til nr. 32

Løsning til min danske kryptokryds nr. 32

Definitioner er understregede.
* angiver omkastning, < angiver omvending.

Vandret

2 Retsforfølge og lede efter vrøvl igen. (7)
SAGSØGE. SØGE (=lede) efter GAS (vrøvl) retur (=igen)

7 Lyd fra endetarm i avlssvin. (4)
MIAV. Gemt i endetarMIAVlssvin

10 Anret sumak-arrangement fra vestafrikansk land. (10)
MAURETANSK. ANRETSUMAK*

11 To kilo i vinen gør beruset. (7)
DRUKKET. KK (to kilo) i DRUEN

13 Afsætning af glas går tilbage. (4)
SALG. GLAS<

14 Propagere for EU? Bed DR om skrivelse. (7)
UDBREDE. EUBEDDR*

15 Stagnation i Liechtenstein er tidsbegrænset. (6)
INTERTI. liechtensteINERTIdsbregrænset

16 Lige fra regnvejr til robåd. (4)
ENER. Hvert andet bogstav fra REGNVEJR

17 Svovl-ledning har forskinket hvad der blev afsat seks dage til. (9)
SKABELSEN. S(vovl) + KABEL + SEN

21 Vi pirater til søs, hvor offentlighed er uønsket. (9)
PIRATERI. VIPIRATER*

25 Storme fra gale aser. (4)
RASE. ASER*.

27 Skinger tuba afbryder stilhed uden at holde tempoet. (6)
RUBATO. TUBA* i (afbryder) RO (stilhed).

29 Gøre hastværk når man restaurerer voliere. (7)
OVERILE. VOLIERE*

30 Dyr fadæse leverer indhold. (4)
ÆSEL. fadÆSELeverer

31 Var fx Finland under den kolde krig et område med god akustik? (7)
LYDLAND. Kryptisk definition, indikeret ved “?”.

32 Besvær i knoglerne, de er slemt betændte! (10)
LEDSMERTER. DEERSLEMT*

33 Klokken er forkert. (4)
URET. Dobbelt definition.

34 Dekanen, efter omorganisation, er den, der genoptager sagen. (7)
ANKENDE. DEKANEN*.

Lodret

1 Gid prishop skaber en vred kunde, fx. (10)
HIDSIGPROP. GIDPRISHOP*

2 Svagt fra sangerinder fra sjællandsk akademi. (7)
SORANER. SOPRANER uden P (“svagt”).

3 At mule over magisk smykke. (6)
AMULET. ATMULE*.

4 Overførselsindkomst til husdyr i form af tørret frugt. (5)
SUKAT. SU + KAT.

5 Finde på nyt navn til agenda: køber flås. (7)
GENDØBE. aGENDa kØBEr flået (dvs. uden det yderste lag.)

6 Opret selvstændighedsbevægelse og Belgien griner. (7)
ETABLER. ETA + B + LER.

7 Malker forbløffende fisk. (6)
MAKREL. MALKER*

8 Medrivende og ophidsende tennis. (6)
INTENS. TENNIS*.

9 Gav kærtegn, omkring et sekund, men anstrengte sig. (5)
ASEDE. AEDE omkring S.

12 Dejlig forvirret om skingert horn er lavet stål, fx. (10)
JERNHOLDIG. DEJLIG* omkring HORN*

18 Hinduistisk princip om kulde og udstråling. (7)
KARISMA. KARMA om IS.

19 Lot vendte sig godt en halv meter omkring for at se øen. (7)
ATOLLEN. ALEN omkring LOT<

20 To gange en tønde efter aftale. (7)
ENTENTE. EN T(ønde) (to gange) E(efter)

22 Denise, efter et par øl, forbliver meget kølig. (6)
ISENDE. DENISE*

23 Vitser om Puccini, fx. (6)
VERIST. VITSER*.

24 Hård på den gamle måde, indeholder lille risiko. (6)
HASARD. HAARD omkring S (small)

26 Fiskerihavn erhverver delvist skaller. (5)
AVNER. fiskerihAVNERhverver

28 Syntes at nogen fortjente grundtemaets kerne. (5)
UNDTE. grUNDTEmaets.

Lyd fra endetarm i avlssvin (4)

no28

Mit fjerde forsøg på en dansk kryptisk krydsogtværs i den engelske »bjælkede« stil. Nogle nøgler er udmærkede, andre lidt kluntede.

Som PDF: no32.  Løsning til nr. 32

Vandret
2 Retsforfølge og lede efter vrøvl igen. (7)
7 Lyd fra endetarm i avlssvin. (4)
10 Anret sumak-arrangement fra vestafrikansk land. (10)
11 To kilo i vinen gør beruset. (7)
13 Afsætning af glas går tilbage. (4)
14 Propagere for EU? Bed DR om skrivelse. (7)
15 Stagnation i Liechtenstein er tidsbegrænset. (6)
16 Lige fra regnvejr til robåd. (4)
17 Svovl-ledning har forskinket hvad der blev afsat seks dage til. (9)
21 Vi pirater til søs, hvor offentlighed er uønsket. (9)
25 Storme fra gale aser. (4)
27 Skinger tuba afbryder stilhed uden at holde tempoet. (6)
29 Gøre hastværk når man restaurerer voliere. (7)
30 Dyr fadæse leverer indhold. (4)
31 Var fx Finland under den kolde krig et område med god akustik? (7)
32 Besvær i knoglerne, de er slemt betændte! (10)
33 Klokken er forkert. (4)
34 Dekanen, efter omorganisation, er den, der genoptager sagen. (7)

Lodret
1 Gid prishop skaber en vred kunde, fx. (10)
2 Svagt fra sangerinder fra sjællandsk akademi. (7)
3 At mule over magisk smykke. (6)
4 Overførselsindkomst til husdyr i form af tørret frugt. (5)
5 Finde på nyt navn til agenda: køber flås. (7)
6 Opret selvstændighedsbevægelse og Belgien griner. (7)
7 Malker forbløffende fisk. (6)
8 Medrivende og ophidsende tennis. (6)
9 Gav kærtegn, omkring et sekund, men anstrengte sig. (5)
12 Dejlig forvirret om skingert horn er lavet stål, fx. (10)
18 Hinduistisk princip om kulde og udstråling. (7)
19 Lot vendte sig godt en halv meter omkring for at se øen. (7)
20 To gange en tønde efter aftale. (7)
22 Denise, efter et par øl, forbliver meget kølig. (6)
23 Vitser om Puccini, fx. (6)
24 Hård på den gamle måde, indeholder lille risiko. (6)
26 Fiskerihavn erhverver delvist skaller. (5)
28 Syntes at nogen fortjente grundtemaets kerne. (5)

English statistician is positive to a degree (5)

The occasion of this cryptic crossword was the workshop Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms (Nov. 2 – Nov. 6, 2015, Simons Institute for the Theory of Computing, Berkeley, California, United States) that I had the pleasure of co-organising.

The grid is a bit more difficult than usual, with several entries less than 50% checked, and two 15-letter words. Some of the clues (and jokes) make little sense if you’re not the in target group of theoretical computer scientists.

no33

Across

9 School on a graph isomorphism base. (9)
10 Who does the grading in Greek? (5)
11 Maybe a forest is better. (7)
12 Bizarre airlines ignoring N. Alon, say. (7)
13 Indian author of assumption about finding 14 across fast. (4)
14 Idiot workers take gin cocktail to first job. (10)
16 They fight to restore Rosamond’s section. (7)
17 Matrix transform vanishes when v → 0. (7)
19 Circuit complexity, typically, sounds like a religious habit (10)
22 Father of parameterised and polynomial-space algorithms, originally. (4)
24 Two-player game about encrypted mail token. (7)
25 Free variable turns leading proof assistant around. (7)
26 Additional seconds of Keynote experiments stymie brilliant talk. (5)
27 Compute |AB| as |A| + |B| like Dracula’s former girlfriend? (9)

Down

1 Maybe 20 down is a hammer made of carbon fibre? (9,6)
2 Beethoven wrote one functor in homological algebra; maybe addition. (8)
3 English statistician is positive to a degree. (5)
4 Introduces P.I.T. problem in linearly independent sets. (8)
5 Family of degree |C|. (6)
6 Tree decompostion of Sat is near. (4,5)
7 Letters from Nerode let Erdös blank out. (6)
8 Laugh at an optimal hint solving a problem. (11,4)
15 Maybe a2 + b2 + c2 challenge keeps Naor up. (9)
17 Optimal scheduler spent day and performed many tasks. (8)
18 Where identity is unique, altogether. (2,1,5)
20 More than 64 kilobyte Nintendo retro characters. (6)
21 Neglected flow algorithm starts confusingly. (6)
23 Threaten unruly spy with hierarchy. (5)

Annotated solution

Secret Sartre


(Trigger warning: this is satire intended to lampoon the two cultures currently dividing academic politics. It is also a fully playable social deduction game in the tradition of Werewolf, Mafia, The Resistance, and Avalon. In fact, Secret Sartre is a straighforward re-theming of the upcoming game Secret Hitler by Max Temkin (2016). Re-theming is a euphemism for theft, but no infringement of intellectual property is intended. Since this satire is about postmodernsim, intent is all that matters. The print-and-play edition of the original, including the rules, is available on-line; Secret Hitler is an extremely well-designed game with brilliant mechanics and a splendid theme.)

LogoSecret Sartre

In Secret Sartre, the faculty members of an unnamed university department battle for ideological supremacy. A fragile alliance of upstanding rationalists, logical positivists, empiricists, liberal humanists, scientists and other fetishizers of the Enlightenment must work together to stem the rising tide of postmodernism. Watch out, though – there are closet postmodernists among you, and someone is Secret Sartre.

Overview

At the beginning of the game, each player is secretly assigned to one of three roles: Science, Postmodernism, or Sartre. Sartre plays for the postmodern team, and the postmodernists know who Sartre is, but most of the time Sartre does not know who his fellow postmodernists are. The Scientists are far out on the autism spectrum and don’t know who anyone is.

The scientists win by enacting five rational policies or having Sartre fired. The postmodernists win by enacting six postmodernist policies, or if Sartre is elected Head of Studies late in the game. As postmodernist policies are enacted, the Department Chair gains new powers. Even scientists may find themselves tempted to enact postmodernist policies that help them control the table and fire their enemies. At the same time, the postmodernists conspire to construct a shared narrative space in which the social construction of their allegiance becomes the perceived Truth. Language is a weapon!

Set Up

Give each player a pair of cards, one identity and one allegiance. Both of these cards are secret and may never be shown to any other player, except (i) if Sartre is fired he immediately reveals it, ending the game in victory for the scientists, or (ii) if the Department Head investigates the loyality of a faculty member enacting the Diversity Training postmodern policy.

The composition of faculty is given by the following table:

Players 5 6 7 8 9 10
Science 3 4 4 5 5 6
Po-mo 1+S 1+S 2+S 2+S 3+S 3+S

Here are the faculty members’s identities. Except for Sartre, none of the names have any bearing on the game.
Identities.png
You also need an allegience card for each player. This is the cards that you show when you’re under ideological investigation from the Department Chair. You need 4 po-mo cards (for Derrida, Foucault, Rorty, and Sartre), and 6 science cards (for the rest).

Allegience.png

Put each pair of cards in a separate envelope, shuffle, and deal.

Each player looks at their identities, making sure that nobody else sees it. The player with the highest academic degree in real life is the first Department Chair candidate. If several players hold the same degree, spend some time discussing the merits of the degree-granting institutions, possibly using a recent ranking of universities. If this does not resolve the issue, another player with an MBA can break the tie using the player’s h-index.

The Department Chair candidate now enacts the following ritual. For 5–10 players:

Everybody close your eyes. Postmodernist and Sartre, open your eyes and acknowledge each other. [Take a long pause.] Everyone close your eyes. Everyone can open your eyes. If anyone is confused or something went wrong, please tell the group now.

For 7–10 players:

Everybody close your eyes and extend your hand into a fist in front of you. Sartre, keep your eyes closed but put your thumb out into a thumbs-up gesture. All postmodernists who are not Sartre, open your eyes and acknowledge each other. Postmodernists, take note of who has extended their thumb – that player is Sartre. Think about the relationship between the signifier and the signified. [Take a long pause] Everyone close your eyes and put your hands down. Everyone can open your eyes. If anyone is confused or something went wrong, please tell the group now.

Game play

Secret Sartre is played in rounds. Each round has an Election of new faculty leardership, a Faculty Meeting to enact a new policy, and an Executive Action where the Department Chair exercises his or her power.

Election

Each round, faculty members elect a new Department Chair and Head of Studies. These are shown as two placards (cut them out and fold as shown.)

Placards

  1. At the beginning of a new round, the Department Chair placard moves clockwise to the next player. This player is the new Department Chair candidate.
  2. The Department Chair candidate chooses a Head of Studies candidate by passing the Head of Studies placard to any other eligible player. (The two players who enacted the last policy are not eligible. In a five-player game, only the last active Head of Studies is not eligible.)
  3. Once the Department Chair candidate has chosen a Head of Studies candidate, all players (including the candidates) votes on the proposed government. You need some kind of ballot card for this for each player, such as a white and black stones form some other game, matchsticks, or the Ja! and Nein! cards from the original Secret Hitler. Players indicate readiness to vote by extending their chosen ballot card in front of them (or holding a coloured stone in a fist); discussion continues until every player is read to vote. Once every player is ready to vote, reveal your votes simultaneously so that everyone can see how you voted.

If more than 50% of the group votes yes, the candidates become Department Chair and Head of Studies, respectively. If three or more postmodernist policies have already been enacted, ask the new Head of Studies if he is Sartre; if he is Sartre, he must reveal himself and the game immediately ends in a postmodernist victory. Otherwise, proceed to the Faculty Meeting.

If the vote is a tie, or if most players vote no, the Department Chair placard moves clockwise to the next player and the election tracker is advanced by one election. (The election tracker is at the bottom of the Science policy board, see below. Use a coin or something similar.)

Student Reps

If faculty rejects three proposals in a row, the student representatives take matters into their own hands. Student policies are completely random: Reveal the policy on top of the Policy Draw Deck and enact it. Any power granted by this policy is ignored, but all players become eligible for Head of Studies for the next Election. Reset the Election Tracker after a policy is enacted by the populace or a government is successfully elected.

Faculty Meeting

You need 6 rational policy cards and 11 postmodernist policy cards. These are shuffled and placed face-down as the Policy deck.

Policies

The Department Chair draws the top three cards from the Policy deck,
looks at them in secret, and discards one Policy face down into the discard pile. The Chair passes the remaining two cards to the Head of Studies who looks in secret, discards one Policy card face down, and enacts the remaining Policy card by placing it face up on the corresponding track.

This is the track for the scientist’s policies:

Science policies

None of these policies has any effects on game play or real life, their role is only to mantain the status quo of male white dominance of Academia (includig Marie Curie as a token woman). The scientists win after enacting the fifth rational policy.

Depending on the number of players, one of three boards is used for postmodernist policies:

pomo-policies

 

Postmodern policies may have effects on game play, see below.
The sanctity of the faculty meeting is of the utmost importance! Once it begins with the Head drawing three Policy cards, faculty members stay silent until a policy has been enacted. Discarded policy cards may never be revealed; you must rely on the word of faculty leadership, who are allowed to lie.
If there are fewer than three cards remaining in the Policy deck at the end of a legislative session, shuffle them with the discard pile to create a new Policy deck. Unused policies should never be revealed, nor may they simply placed on top of the new Policy deck. If the government enacts a rational policy or a postmodernist policy that grants no power, begin a new round with a new Election. If the government enacts a postmodernist policy that grants power to the Department Chair, proceed to the Executive Action.

Executive Action

Whether by fate or choice, the faculty meeting may have adopted a postmodernist policy, moving the department away from excessive reductionism and granting the Deparmental Chair new powers to enforce collectivist fidelity. The Departmental Chair must enact the power granted in this round. Look at the Postmodernism policy track to determine which power, if any, has been granted.

  1. Diversity/harassment Training. The Department Chair investigates another player who has not yet been investigated by saying “I suggest [player name] be sent to a mandatory diversity/harassment training seminar”. The purpose of such a seminar is to ascertain the player’s ideological fidelity. That player passes his Allegiance Card (not his Identity!) to the Department Chair who checks that player’s allegiance in secret and then returns the card to the player. The Department Chair may share (or lie about!) the results of his investigation at his discretion, but may not show the card.
  2. Affirmative Action. The Department Chair chooses any other player at the table to be the next Department Chair candidate by passing that player the Department Chair placard. That player nominates a Head of Studies and the election proceeds as usual. After an Affirmative Action, the Departmental Chair returns to its original order.
  3. Adapt new Values Statement. The Department Chair secretly looks at the top three cards in the Policy deck and then returns them to the top of the deck without changing the order.
  4. Smear Campaign. The President fires one player at the table by saying “I fire [player name] because of [unreasonable charge of the player’s choice, excluding lack of academic excellence].” If that player is Sartre, he reveals his Identity Card and the game ends in a victory for the scientist. If the executed player is not Sartre he does not reveal his role or his loyalty. He is removed from the game and may not speak, vote, or run for office.
  5. Veto Power. After five postmodernist policies have been enacted, rational discourse among faculty members has been silenced, and departmental leadership gains much broader power over which policies are enacted. The Departmental Chair draws three policies, discards one, and passes the remaining two to the Head of Studies as usual. The Head of Studies may, instead of enacting either policy, say “This policy disadvantages [underprivileged group of player’s own choice, but not white males or Jews].” If the Departmental Chair consents, both policies are discarded and the Presidency placard passes to the left as usual. If the Departmental Chair does not consent, the Head of Studies must enact one of the two policies handed to him. Each use of the veto power represents an inactive leadership and advances the election tracker by one.

Løsning til nr. 31

Løsning til kryptokryds nr. 31.

Vandret

2 Småfed kvinde, travlt besat.
KVABSET (=småfed)
Ordspil: KV (fork. for kvinde), anagram (travlt) av BESAT

7 Drej knækket krus. (4)
SKRU (= drej)
Ordspil: anagram (drej) af KRUS

10 Tilpasning af dato: Patina ændres. (10)
ADAPTATION ( = tilpasning)
Ordspil: anagram (ændring) af DATOPATINA

11 Anarkistisk junta tilbageholder strøm d. 24. december. (7)
JULENAT (= d. 24. december)
Ordspil: Anagram (anarkistisk) af JUNTA  omkring LE (strøm “el”, omvendt)

13 Atter skjult i lykkelig ensomhed. (4)
IGEN (= atter)
Ordspil: Skjult i lykkelIGENsomhed

14 Ungt rådyr går frem og tilbage efter plante. (7)
KIDDIKE (en plante i korsblomstfamiljen)
Ordspil: KID (ungt rådyr) + DIK (KID baglæns, ordet “går frem og tilbage”) + E (“efter”)

15 Nu ses vrede efter Cæsars første folketælling. (6)
CENSUS (= folketælling)
C (Cæsars første bogstaf) + anagram (vrede) af NU SES

16 Eremit vaskede spejlet. (4)
ENER (= eremit)
Ordspil: RENE (= vaskede, adj.) baglæns

17 Omorganiseret natolager bruges til kommunikation. (9)
TALEORGAN (bruges til kommunikation)
Anagram (omorganiseret) af NATOLAGER

21 Oprørt generer de dem, der bestemmer. (9)
REGERENDE (= dem, der bestemmer)
Anagram af (oprørt) GENERER DE

25 En klovn tilbage til landet. (4)
IRAN (et land)
I (en) + NAR (= klovn) baglæns

27 Handles kort efter dyrket mark. (6)
AGERES ( = handles)
AGER (dyrket mark) + ES (et kort)

29 Betragt i fuglekæbe en del af skelettet. (7)
NÆSEBEN (del af skelettet)
SE (betragt) indeholdt i NÆB (fuglekæbe) + EN

30 Hvor man kan mødes omkring sagnvæsen. (4)
CAFE (hvor man kan mødes)
CA (omkring) + FE (et sagnvæsen)

31 Hvad siger det lille lam i skrift til europæer. (7)
RUMÆNER (europæer)
MÆ (hvad det lille lam siger) i RUNER (skrift)

32 Omdanne sær, opdyrket jordart. (10)
MORÆNESAND (jordart)
Anagram (opdyrket) af OMDANNESÆR

33 Angrib rent ud. (4)
ENTR (angrib)
Anagram (ud) af RENT

34 Tømt glas for hastig dukkert. (7)
DRUKKET (tømt glas)
Anagram (hastig) af DUKKERT

Lodret

1 Afvisning af smykke efter skaldyr på tog. (10)
REJICERING (= afvisning)
RING (smykke) efter IC (tog) i REJE (skaldyr)

2 Tænk nu gedens indvolde klemte. (7)
KNUGEDE (=klemte)
Indeholdt (“indvolde” af) tænKNUGEDEn

3 Slagmarken tabes i begyndelsen passivt. (6)
VALENT (= passiv)
VALEN (asernes slagmark) + T (første bogstav af “tabes”)

4 Fx zulu, beta, alfa, november, tango, uniform. (5)
BANTU (en gruppe af sprog som indeholder zulu)
B + A + N + T + U (ifølge i det internationale flyveralfabet)

5 Måske Gråbøl returnerer en frokost. (7)
ETTIDEN (frokost)
DITTE (Gråbøl) bagfra (“returnerer”) + EN

6 Julemad i kristendommen fx, den sidder fast i munden. (7)
TANDROD (sidder fast i munden)
AND (julemad) i TRO (kristendommen, fx) + D (den, fork.)

7 Station lever af større byer. (6)
STÆDER (større byer)
ST (station, fork.) + ÆDER (= lever af)

8 Se rundt om min horisont. (6)
KIMING (= horisont)
KIG (= se) omkring MIN

9 Flytte bruskfisk. (5)
ROKKE (= flytte) (en bruskfisk)

12 Åbner udstilling: Firserne er misforstået. (10)
FERNISERER = åbner udstilling
Anagram (misforstået) af FIRSERNE ER

18 Bredt stykke stof gør din barm gyngende. (7)
ARMBIND (bredt stykke stof)
Anagram (gyngende) af DINBARM

19 Organ findes og yder. (7)
LEVERER (= yder)
LEVER (organ) + ER (findes)

20 Lincoln, mellem venner, pruttede til vildt gilde. (7)
ABEFEST (vildt gilde)
ABE (Abraham Lincoln) + FES (pruttede) + T (til, fork.)

22 Gammelt ømtåleligt helium fx. (6)
GASART (helium, fx)
GA (gammelt, fork.) + SART (= ømtåleligt)

23 Bære en rådden frugt. (6)
ENEBÆR (frugt)
Anagram (rådden) af BÆRE EN

24 Promovere dansk kulturradikal uden ende. (6)
BRANDE (= promovere)
(Georg) BRANDES (dansk kulturradikal) uden sidste bogstav

26 Fornuft er mærkelig baglæns på engelsk. (5)
RÆSON (= fornuft)
SÆR (= mærkelig) baglæns + ON (på, engelsk)

28 Mesterskaber i vanvid i soveværelse fx. (5)
GEMAK (soveværelse, fx)
EM (mesterskaber) i GAK (vanvid)

Fx zulu, beta, alfa, november, tango, uniform. (5)

no28

Mit tredje forsøg på en dansk kryptisk krydsogtværs i den engelske »bjælkede« stil, som man kan finde hos Guardians Azed eller Times’ Listener.

Jeg finder det fortsat uhyre svært at komponere naturlige kryptiske nøgler på dansk, og resultatets kvalitet er langt under, hvad man kan finde en en almindelig engelsk avis.

Jeg prøver stadig at holde mig inden for de etablerede engelske regler, som nedfældet af mesteren Ximenes (What are Ximenean clues?).

Ikke mindst har jeg forsøgt at være nogenlunde stringent med at indikere definition ved eksempel. Hvis jeg fx vil beskrive HUND kan jeg gøre det ganske ligefremt ved en kategori (»Husdyr (4)«). Men hvis jeg vil indikere HUND ved at angive et eksempel, så skal jeg indikere det med »fx« eller »måske« eller lignende. Jeg kan altså skrive »Måske en schæfer (4)« eller »Lassie, fx (4)« men ikke bare »Grand Danois (4)«. Jeg finder selv, at de resulterende nøgler virker ganske kluntede i forhold til de tilsvarende engelske konstruktioner, men i første omgang bestræber jeg mig på at sætte så enkle kryptiske kryds og tværser som muligt, så æstetik og elegance må forblive underordnet indtil jeg bliver dygtigere.

Jeg har brugt samme gitter som til nummer 28.

PDF-udgave: no31. Løsning.

Vandret
2 Småfed kvinde, travlt besat. (7)
7 Drej knækket krus. (4)
10 Tilpasning af dato: Patina ændres. (10)
11 Anarkistisk junta tilbageholder strøm d. 24. december. (7)
13 Atter skjult i lykkelig ensomhed. (4)
14 Ungt rådyr går frem og tilbage efter plante. (7)
15 Nu ses vrede efter Cæsars første folketælling. (6)
16 Eremit vaskede spejlet. (4)
17 Omorganiseret natolager bruges til kommunikation. (9)
21 Oprørt generer de dem, der bestemmer. (9)
25 En klovn tilbage til landet. (4)
27 Handles kort efter dyrket mark. (6)
29 Betragt i fuglekæbe en del af skelettet. (7)
30 Hvor man kan mødes omkring sagnvæsen. (4)
31 Hvad siger det lille lam i skrift til europæer. (7)
32 Omdanne sær, opdyrket jordart. (10)
33 Angrib rent ud. (4)
34 Tømt glas for hastig dukkert. (7)

Lodret
1 Afvisning af smykke efter skaldyr på tog. (10)
2 Tænk nu gedens indvolde klemte. (7)
3 Slagmarken tabes i begyndelsen passivt. (6)
4 Fx zulu, beta, alfa, november, tango, uniform. (5)
5 Måske Gråbøl returnerer en frokost. (7)
6 Julemad i kristendommen fx, den sidder fast i munden. (7)
7 Station lever af større byer. (6)
8 Se rundt om min horisont. (6)
9 Flytte bruskfisk. (5)
12 Åbner udstilling: Firserne er misforstået. (10)
18 Bredt stykke stof gør din barm gyngende. (7)
19 Organ findes og yder. (7)
20 Lincoln, mellem venner, pruttede til vildt gilde. (7)
22 Gammelt ømtåleligt helium fx. (6)
23 Bære en rådden frugt. (6)
24 Promovere dansk kulturradikal uden ende. (6)
26 Fornuft er mærkelig baglæns på engelsk. (5)
28 Mesterskaber i vanvid i soveværelse fx. (5)

Hearthstone Algorithms Design Exercises

Exam time again. I’ve tried to produce exam questions for my current algorithms design class themed after Blizzard’s collectible card game Hearthstone. For a variety of reasons I decided to abandon the idea for the exam, but the ideas are cute enough for a blog post. Here are the first three. The target audience are algorithms design students struggling with Chapters 1–8 of Kleinberg and Tardos’s Algorithms Design book (so: graph traversal, greedy, divide and conquer, dynamic programming, network flow, NP-hardness). Enjoy!

Hearthstone Basics

Each card in the game Hearthstone depicts a minion. Each minion has 3 values: Attack, Health and Cost, given as integers a, h, and c. Here’s a minion with Attack 3, Health 2, and Cost 4:

xMBCWkKf

For the purpose of these exercises, these values are unbounded, positive integers. During the game, both players have a number of minions in play. In a turn of Heartstone, the player assigns his minions to fight enemy minions. Each minion gets to target a single enemy minion, initiating a fight between the two minions. When a minion with Attack A fights a minion with Health H, the other minion’s Health is reduced to max{0,H-A}. Note that both minions fight, and each deals damage to the other, regardless of who initiated the fight. Also note that an enemy minion can be involved in many fights each turn, when it is repeatedly targeted. When a minion’s Health is reduced to 0, it is removed from play.

For each of the problems below, state which algorithmic design technique should be used, or if the problem is NP-hard. Also give the best asymptotic worst-case running time.

Cleanup

You and ZombieMage02 both have the same number of minions in play. It is your turn. Can you take them all the enemy minions in one sweep?

Input:
The enemy minions (a1,h1),…,(an,hn) ∈ N2 and your minions (a1′,h1′),…,(an′,hn′) ∈ N2

Output: “Yes,” if your minions can take out all enemy minions this turn. “No,” otherwise.

Tanks

TwoOrcsOneCup has two minions in play. Both completely overpowered and powerful enough to wipe out your hero when it becomes TwoOrcsOneCup’s turn again. You have n minions in play. Can you take out both minions this turn?

EPfTXn7N FmSMUX1Z

Input: The enemy minions (a1,h1),(a2,h2) ∈ N2 and your minions (a1′,h1′),…,(an′,hn′) ∈ N2

Output: “Yes” if your minions can take out both enemy minions this turn.

Charge!

Showdown time. Your hero has almost no Health left and OprahWindfury’s mage keeps pummeling you with fireballs. This has been going on for hours—time to end this! Luckily your hand is full of high-powered cards with Charge, which can attack immediately.
Get out as many of these guys as you can afford!

Input Your available mana K. The minions with Charge on your hand, (a1,h1,c1),…,(an,hn,cn) ∈ N2.

Output: The total number of Attack points you can play this round.


Cards generated using achievementgen.com

The Monster in the Library of Turing

Appears (in Swedish) as T. Husfeldt, Monstret i Turings bibliotek, Filosofisk tidskrift 36(4):44-53, 2015.

[As PDF]

Nick Bostrom’s Superintelligence presents a dystopian view of strong artificial intelligence: Not only will it be the greatest invention of mankind, it will also be the last, and this emerging technology should be viewed as an immediate and catastrophic risk to our species, like molecular nanotechnology, nuclear power, or chemical warfare.

Nick Bostrom, Superintelligence, Oxford University Press, 2014.

Nick Bostrom,
Superintelligence, Oxford University Press, 2014.

Artificial intelligence with super-human capabilities will be the last invention controlled by Homo sapiens, since all subsequent inventions will be made by the “superintelligence” itself. Moreover, unless we are extremely careful or lucky, the superintelligence will destroy us, or at least radically change our living conditions in a way that we may find undesirable. Since we are currently investigating many technologies that may lead to a superintelligence, now would be a good time for reflection.

Nobody knows, much less agrees on, how to define intelligence, be it general, artificial, or strong. Neither does Bostrom. By his own admission, his book is inherently speculative and probably wrong. Not even the rudiments of the relevant technology may be known today. However, many of Bostrom’s arguments are quite robust to the particulars of “what?” and “how?”, and the book can be enjoyed without a rigorous definition. For now, we imagine the superintelligence as a hypothetical agent that is much smarter than the best current human brains in every cognitive activity, including scientific creativity, general wisdom, and social skills.

Pathways and Consequences

Bostrom describes a number of pathways towards a superintelligence. They consist of current scientific activities and emerging technologies, extrapolated beyond human cognitive capabilities. These include

  • neuroanatomical approaches, such as simulation of whole brains (Einstein’s brain in a vat or simulated on a computer, neurone by neurone),
  • genetically or artificially modified humans (brain implants, parental gamete selection for intelligence),
  • intelligence as an emergent phenomenon in simpler networks (the internet as a whole “becomes conscious”),
  • computer science approaches like machine learning (IBM’s Jeopardy-winning Watson) and “good old-fashioned artificial intelligence” using symbolic reasoning (chess computers).

None of these technologies is currently close to even a dullard’s intelligence, but on a historical time scale, the are all very new. Bostrom’s description is an entertaining tour of computer science, neuroanatomy, evolutionary biology, cognitive psychology, and related fields. It is moderately informative, but none of it is authoritative.

The consequences of any of these research programs actually achieving their goals are even more speculative. Several futurists have developed scenarios for how a superintelligent future might look, and Bostrom surveys many of these ideas. In one of those visions, accelerating and self-improving digital technologies quickly overtake human cognitive abilities and transform our environment, like we transformed pre-historic Earth. After a short while, all the protons that currently making up the planets of the solar system are put to better use as solar-powered computing devices, orbiting the sun in a vast networked intelligence known as a Dyson sphere. There are many other scenarios, partly depending on which approach will turn out to win the race against our own intelligence, and how the result can be harnessed. Not all these possible futures are dystopian. Some even leave room for humans, maybe uploaded to a digital version of immortality, or kept in zoos. But they certainly entail dramatic changes to our way of life, easily comparable to the invention of agriculture or the industrial revolution.

The Control Problem

Bostrom’ book begins with a short fable, in which a group of birds agrees to look for an owl chick to help them with nest-buildling and other menial labours. We immediately see their folly: The owl chick will quickly outgrow the birds, throw off their yoke, and quite probably eat them, as is its nature. The birds would have been better off thinking about the result of their search before it was too late.

However, in its most harmless form, the superintelligence is merely a device that excels at goal-oriented behaviour, without intentionality, consciousness, or predatory tendencies. Bostrom explains that even such a superintelligent servant, docile in comparison to the rampant killer robots from blockbuster movies, would be a terrible thing.

Bostrom describes an interesting thought experiment about how to specify the behaviour of a superintelligent machine that produces paperclips. There are at least two undesirable outcomes that stem from “perverse instantiation” of the machine’s task. One is that the machine might turn everything into paperclips, including humans. Or, faced with a more carefully worded task, the machine first solves the problem of increasing its own intelligence (to become a better paperclip-producer), turning the entire solar system microprocessors. No matter how much we continue specifying our orders, the machine continues to avoid “doing what we mean” in increasingly intricate ways, all with catastrophic outcomes.

I like to think of this idea in terms of Goethe’s Zauberlehrling, immortalised by Mickey Mouse in Disney’s Fantasia. In this tale, the sorcerer’s apprentice commands his enchanted broomstick to fill water into a bathtub. Obedient and literal-minded, the magical servant hauls up bucket after bucket, yet continues long after the tub has been filled. Disaster is averted only because the sorcerer himself arrives in the nick of time to save Mickey from drowning. No malice was involved; unlike Bostrom’s allegorical owl-chick, the broomstick has no volition other than the dutiful execution of Mickey’s task. It was Mickey who failed to be sufficiently precise in how he formulated the task. Had Goethe’s broomstick been superintelligent, it seems to me that he might just have killed the apprentice and thrown his body in the tub. After all, 70 percent of it are water, so the task is completed with speed and elegance.

Illustration of Der Zauberlehrling. From: Goethe's Werke, 1882, drawing by Ferdinand Barth (1842--1892).

Illustration of Der Zauberlehrling. From: Goethe’s Werke, 1882, drawing by Ferdinand Barth (1842–1892).

These games of formalism may strike you as trite exercises in deliberately misunderstanding instructions against their intention. However, every programmer or lawmaker knows that this is exactly the reason for why software is so hard to write or laws are hard to formulate. If there is a way to misunderstand your instructions, it will happen.

Thus, there is no need to attribute malice to the superintelligence. Instead, we might be doomed even by a perfectly obedient agent labouring to perform ostensibly innocent tasks. In the words of Eliezer Yudkowsky, “The AI does not hate you, nor does it love you, but you are made out of atoms which it can use for something else.” 1 Of course, a superintelligence with volition, intentionality, or free will, would be even harder to control.

The control problem has many aspects, one of which is purely institutional: If the superintelligence is developed in vicious competition between corporations or militaries, none of them is motivated to stop the development, for fear of losing a technological arms race. As a civilisation, we have an unimpressive track record of preventing globally harmful behaviour when individual proximate gains are at hand. This addresses a popular rejoinder to a dystopian intelligence explosion: “Why don’t we just pull the plug?” First, it’s not clear that there is a plug to pull.2 Second, who is “we”?

Assuming we can solve the institutional problem of who gets to design the the superintelligence, the solution seems to be to codify our goals and values, so that it won’t act in ways that we find undesirable. This, of course, is a problem as old as philosophy: What are our values? And again, who is “we”: the species, the individual, or our future? Should the paperclip maximiser make sure no children are killed? Should no unborn children aborted? Is it in the alcoholic’s interest to receive alcohol or not?

Bostrom speculates if we can “what is good for us” on a higher-order level, asking the superintelligence to extrapolate our desires based on a charitable (rather than literal) interpretation of our own flawed descriptions, possibly in a hierarchy of decisions deferred to ever higher moral and intellectual powers. Assuming that we were to agree on a meaningful “Three Laws of Robotics” that accurately described our values without risking perverse instantiation, how do we then motivate a vastly superiour intellect to follow these laws? I find these speculations both entertaining and thought-provoking.3

Some futurists welcome the idea of a paternalistic superintelligence that unburdens our stone-age mind from solving our own ethical questions. Even so, as Bostrom argues, if we share our environment with a superintelligence, our future depends on its decisions, much like the future of gorillas depends on human decisions. If we are currently building the superintelligence, we have but one chance to make it treat us as nice as we treat the gorillas.

The Library of Turing

Bostrom tacitly assumes a strictly functionalist view of the mind. For instance, if we were able to perfectly simulate the neurochemical workings of a brain, this simulation itself would be a mind with consciousness, volition, and agency. Once the functions of the brain are understood, the substrate on which their simulation runs is secondary. From this perspective, questions about cognition, intelligence, and even agency, are ultimately computational questions.

Let me invite you to a fictional place that I call the Library of Turing. It is inspired by La biblioteca de Babel, described in a short story by Jorge Luis Borges. His library consists of an enormous collection of all possible books of a certain format. Almost every book is gibberish, as had it been typed by intoxicated monkeys. One book consists entirely of the letter A, but another contains Hamlet.4 In Borges’ story, the librarians find themselves in a suicidal state of despair; surrounded by an ocean of knowledge, yet unable to navigate it due to the library’s overwhelming dimensions. Our brains cannot fathom its size, and our languages cannot describe it5, “unimaginably vast” does not even come close. However, the metaphor of the library helps us to build some kind of mental image of its size.6

Behold, then, the Library of Turing. Each volume contains computer code. Much of it is garbage, but some volumes contain meaningful programs in some concrete programming language, let’s say Lisp.7 We can feed these programs to a computer found in each room. Most wouldn’t do anything useful, many would cause the computer to crash. From our starting room, lined with bookcases, we see exits to other rooms in all directions. These rooms contain more volumes, more bookcases, and more exits. There is no discernible ordering in the library, but close to where we are standing, a particularly worn volume contains the program

        (print "Hello, world!")
    

which instructs the computer to output the friendly message “Hello world!”. Next to it, a book contains the nonsensical phrase “Etaoin shrdlu,” not a valid program in Lisp. We shrug and put it back. Thanks to the diligence of some algorithmic librarian, a third book in our room contains the complete code for the primitive natural language processor Eliza, written by Joseph Weizenbaum in 1966. This famous little program is able to pretend to have (typed) conversations with you, like this:

“Tell me your troubles.”

“My cat hates me.”

“What makes you believe cat hates you?”

The primitive grammatical mistake of leaving out the pronoun gives you a clue that Eliza works by very simple syntactic substitutions, without any attempt at understanding what you mean. Still, it’s better than just saying “Hello, world!” If we continue browsing, we might find the code of some natural language processors that are state-of-the-art in the 2010s, such as IBM’s Watson, or Apple’s Siri.

eliza

Fragments of the source code of Eliza, an early natural language processor. The whole program takes just over 1000 lines.

Fragments of the source code of Eliza, an early natural language processor. The whole program takes just over 1000 lines.

Indeed, our conceit is that every algorithm appears somewhere in Turing’s library. 8 In particular, if we accept functionalism, some book describes the behaviour of Einstein’s brain: On input “What is 5 + 5” or “Do you prefer Brahms?” or “Prove the Riemann hypothesis” it will give the same answer as Einstein. We have no idea how this program looks. Maybe it is based symbolic artificial intelligence, like Eliza. Or maybe the bulk of the books is taken up by a “connectome” of Einstein’s actual brain, i.e., a comprehensive map of its neural connections. Such a map has been known for C. elegans, a transparent roundworm with 302 neurones, since the mid-1980s, and even though Einstein’s brain is considerably larger, this is not absurd in principle.

Somewhere in Turing’s library there must be description of a computational process that is vastly superior to every human brain. Otherwise Einstein’s brain would have been the smartest algorithmic intelligence allowed by the laws of logic, or close to it. Yet it seems unlikely, not to say self-congratulatory, that evolution on the planet Earth succeeded in constructing the ultimate problem solving device in just a few million generations.

Translated into this setting, Bostrom suggests that our discovery of this description would have catastrophic consequences. The library contains a monster. Our exploration should proceed with prudence rather than ardour.

Searching for the Monster

Given that the description of a superintelligence exists somewhere in the library, all that remains is to find it. If you don’t work in computer science, this task seems to be relatively trivial. After all, even a mindless exhaustive search will find the volume in question. While this approach is not a particularly tempting exercise for a human, computers are supposed to be good at performing mindless, well-defined, repetitive, and routine tasks at high speed and without complaining. Thus, sooner or later we stumble upon the monster; the only debate is whether the search time is measured in years, generations, or geological time scales.

But this is a fallacy. It is a fallacy because of the unreasonable growth rate of the exponential function, and the powerlessness of exhaustive search.

To appreciate this, consider again the 23 symbols that make up our friendly “Hello World!” program. We could have found it, in principle, by exhaustively searching through all sequences of characters that make up Lisp programs.

How much time does this take? That is a simple exercise in combinatorics, after we fix some details—how many symbols are there, how fast is the computer, etc. But no matter how you fix these details, the result is disappointing.9 If a modern computer computer had started this calculation when the universe began, it would have gotten to somewhere around (print "Hello,"). You could gain a few extra letters by throwing millions of computers at the problem. But even then, the universe does not have enough resources to allow for an exhaustive search for even a very simple program. Either you run out of time before the universe ends, or you run out of protons to build computers with. Computation is a resource, exponential growth is immense, and the universe is finite.

Bostrom pays little attention to this problem. For instance, in his discussion of current efforts on brain simulation, he writes:

Success at emulating a tiny brain, such as that of C. elegans, would give us a better view of what it would take to emulate larger brains. At some point in the technology development process, once techniques are available for automatically emulating small quantities of brain tissue, the problem reduces to one of scaling.

Well, to me, scaling is the problem.

One might object that this observation is a mundane, quantitative argument that does not invalidate the compelling fact that in principle, the exhaustive search will sooner or later stumble upon the fully-fletched “Hello World!”-program, and eventually the monstrous superintelligence. But that is exactly my point: You can simultaneously accept machine-state functionalism and be blasé about the prospects of AI. Speculation about the imminent discovery of the monster in Turing’s Library must be grounded in computational thinking, which is all about the growth rates of computational resources.

Could there be another way of discovering the superintelligence than exhaustive search? Certainly. After all, nature has discovered one of the monsters, the brain of Homo sapiens, starting with very simple “brains” hundreds of millions of years ago, and refining them stepwise by natural selection and mutation in environments that favoured cognition. Thus, there is some gradient, some sensible set of stepwise refinements, that Nature has followed through the Library of Turing to arrive at Einstein’s brain. 10 We just don’t know how to recognise, nor efficiently follow this gradient. In the enthusiasm surrounding artificial intelligence in the 1960s we might have thought that we were on such a gradient. If so, we have abandoned it. The current trend in artificial intelligence, away from symbolic reasoning and towards statistical methods like machine learning, that do not aim to build cognitive models, strikes me as an unlikely pathway.

Given our current understanding of the limits of computation, there are many relatively innocent-looking computational problems that are computationally hard.11 After more than a generation of very serious research into these problems, nobody knows anything better than exhaustive search for many of them. In fact, while the amazing features of your smartphone may tell you a different story, the main conclusion of a generation of research in algorithms is bleak: for most computational problems we don’t know what to do.12

Let me repeat that I do not try to rule out the existence of a monster. I merely point out that even though a monster exists, we may never run into it. Turing’s Library is just too vast, nobody has labelled the shelves, much less put up useful signs and maps. Our intuition is mistaken when it extrapolates that we will soon have mapped the entire library, just because we’ve seen more of it than our grandparents ever did. Moreover, imminent and rampant progress in exhaustive search may have been a reasonable hope half a century ago. But today we know how hard it is.

Research Directions

If the algorithmic perspective above is correct, then there is nothing to worry about. The superintelligence is an entertaining fiction, no more worthy of our attention than an imminent invasion by aliens,13 eldritch gods from the oceans, or a sudden emergence of magic. The issues raised are inherently unscientific, and we might as well worry about imminent overpopulation on Venus or how many angels can dance on the head of a pin.

But I could be wrong. After all, I wager the future of human civilization on a presumption about the computational complexity of an ill-defined problem. I do think that I have good reasons for that, and that these reasons are more firmly grounded in our current understanding of computation than Bostrom’s extrapolations. However, if I’m wrong and Bostrom is right, then humanity will soon be dead, unless we join his research agenda. Thus, from the perspective of Pascal’s wager, it may seem prudent to entertain Bostrom’s concerns.

The problem domain opened up by Superintelligence may lead to valid research in various areas, independently of the plausibility of the underlying hypothesis.

For instance, the problem of codifying human values, a formalization of ethics, is a problem as old as philosophy. Bostrom’s prediction injects these questions with operational significance, as these codified ethics would be the framework for the incentive structure needed to solve the control problem. However, an “algorithmic code of ethics” is a worthwhile topic anyway. After all, our digital societies are becoming increasingly controlled by algorithmic processes. These processes are nowhere near superintelligent, but they are highly influential: Algorithms choose our news, decide our insurance premiums, and filter our friends and potential mates. Their consistency with human values is a valid question for ethicists and algorithmicists alike, no matter if the algorithms are authored by Google’s very real software engineers or a very hypothetical paternalistic AI.

Another issue related to the control problem is the ongoing work on the semantics and verification of programming languages. This has been a well-established subfield of computer science for a generation already. Some of the these issues go back to Gödel’s incompleteness theorem’s from the 1930s, proving that formal systems are unable to reason about the behaviour of formal systems. In particular, it has turned out to be a very difficult problem of logic to specify and verify the intended behaviour of even very short pieces of computer code. It may well be that questions about harnessing the behaviour of a superintelligence can be investigated using these tools. Other scientific areas may provide similar connection points: Incentive structures are a valid question for game theory and algorithmic mechanism design, which resides on the intersection of computer science and economics. Or the computational aspects of artificial intelligence may become sufficiently well defined to become a valid question for researchers in the field of computational complexity. This might all lead to fruitful research, even if the superintelligence remains eternally absent. But whether superintelligence becomes a valid topic for any of these disciplines is very unclear to me. It may depend on purely social issues within those research communities.

It may also depend on the availability of external funding.

This last point leads me to speculate about a very real potential impact of Bostrom’s book. It has to do with the perception of artificial intelligence in the public eye. Research ethics are a political question ultimately decided by the public. The most Herculean promise of current artificial intelligence research is the construction of general artificial intelligence. What if the public no longer saw that as a goal, but as a threat? If Bostrom’s dystopian perspective leads to increased public awareness about catastrophic effects of superintelligence, then general AI would not appear under “Goals” in a research plan, but under “Ethical considerations” that merit to public scrutiny along with climate change, sensitive medical data, rampant superviruses, animal testing, or nuclear disasters. And these, largely political, requirements may themselves necessitate research into the control problem.

We may want to ponder the consequences of running into a monster in the Library of Turing no matter how plausible that event may be.


  1. Eliezer Yudkowsky, Artificial Intelligence as a Positive and Negative Factor in Global Risk, 2006.
  2. Unlike in the movies, we must assume that a superintelligence can anticipate the efforts of a plucky group of heroes. Bostrom describes a number of ways in which to make yourself immune to such an attack by distributing the computational substrate. Surely a superintelligence can think of more.
  3. I particularly like the idea of design an AI with a craving for cryptographic puzzles to which we know the answer.
  4. A million others contain Hamlet with exactly one misprint.
  5. The language of mathematics is an exception. But our brains cannot imagine 1025, the number of stars, much less 10123 the number of atoms in the universe. By contrast, the number of books in the Library of Babel is 251, 312, 000.
  6. Daniel Dennett has has used this idea as “the Library of Mendel” to illustrate the vast configuration space of genetic variation. Daniel C. Dennett, Darwin’s Dangerous Idea, Simon & Schuster 1995.
  7. I chose Lisp because of its role as an early AI programming language, but any other language would do. For a cleaner argument, I could have chosen the syntax of Alan Turing’s original “universal machine”. In the language of computability theory, all these choices are “Turing-complete”: they can simulate each other.
  8. Some programs may be so big as to be spread over several books, maybe referring to other volumes as subroutines much like modern software is arranged into so-called software libraries.
  9. Lisp is written in an alphabet of at most 128 characters. A modern computer with 109 operations per second, running since the Big Bang, would not have finished all 12813 strings of length 13.
  10. If we entertain this idea, then a pathway to intelligence would be the simulation of competetive environments in which to artificially evolve intelligence by mutation and selection. This replaces the problem from simulation of entire brains to simulation of entire adaptive environments, including the brains in them.
  11. This claim is formalised in various hypotheses in the theory of computational complexity, such as “P is not NP” and the Exponential Time Hypothesis.
  12. Not even functioning quantum computers would change this.
  13. Here is the analogy in full: We have explored the Moon and are about to explore Mars. We should worry about imminent contact with alien civilisations.