Complexity no Bar to AI

Critics of AI risk suggest diminishing returns to computing (formalized asymptotically) means AI will be weak; this argument relies on a large number of questionable premises and ignoring additional resources, constant factors, and nonlinear returns to small intelligence advantages, and is highly unlikely.
computer-science, transhumanism, AI, R, insight-porn
2014-06-012019-06-09 finished certainty: likely importance: 10

Com­pu­ta­tional com­plex­ity the­ory de­scribes the steep in­crease in com­put­ing power re­quired for many al­go­rithms to solve larger prob­lems; fre­quent­ly, the in­crease is large enough to ren­der prob­lems a few times larger to­tally in­tractable. Many of these al­go­rithms are used in AI-rel­e­vant con­texts. It has been ar­gued that this im­plies that AIs will fun­da­men­tally be lim­ited in ac­com­plish­ing re­al-world tasks bet­ter than hu­mans be­cause they will run into the same com­pu­ta­tional com­plex­ity limit as hu­mans, and so the con­se­quences of de­vel­op­ing AI will be small, as it is im­pos­si­ble for there to be any large fast global changes due to hu­man or su­per­hu­man-level AIs. I ex­am­ine the as­sump­tions of this ar­gu­ment and find it ne­glects the many con­di­tions un­der which com­pu­ta­tional com­plex­ity the­o­rems are valid and so the ar­gu­ment does­n’t work: prob­lems can be solved more effi­ciently than com­plex­ity classes would im­ply, large differ­ences in prob­lem sol­u­bil­ity be­tween hu­mans and AIs is pos­si­ble, greater re­source con­sump­tion is pos­si­ble, the re­al-world con­se­quences of small differ­ences on in­di­vid­ual tasks can be large on agent im­pacts, such con­se­quences can com­pound, and many agents can be cre­at­ed; any of these in­de­pen­dent ob­jec­tions be­ing true de­stroys the ar­gu­ment.

at­tempts to de­scribe the re­source us­age of al­go­rithms from the ab­stract van­tage point of con­sid­er­ing how run­ning time on some ide­al­ized com­puter rel­a­tively in­creases for a spe­cific al­go­rithm as the in­puts scale in size to­wards in­fin­i­ty. For many im­por­tant al­go­rithms used in AI and pro­gram­ming in gen­er­al, the diffi­culty turns out to in­crease steeply with ex­tra data—­com­par­ison-based sort­ing al­go­rithms like take only 𝒪(n · log(n)) and so you can sort just about any amount of data in a fea­si­ble time, but more in­ter­est­ing prob­lems like the / be­come (or ex­po­nen­tially or worse) as the data in­creases and quickly go from fast to fea­si­ble to im­pos­si­ble.

Complexity implies Singularities are impossible

One ar­gu­ment against pow­er­ful ar­ti­fi­cial in­tel­li­gences, and sce­nar­ios cor­re­spond­ing to in gen­er­al, draws from .

For ex­am­ple, in “The Sin­gu­lar­ity Is Fur­ther Than It Ap­pears”, makes a num­ber of ob­jec­tions rang­ing from the pos­si­bil­ity that neu­rons are more pow­er­ful than gen­er­ally be­lieved and that cor­po­ra­tions have not cre­ated a Sin­gu­lar­ity yet so they never will (some of which are crit­i­cized by William Hertling), but he starts with a com­pu­ta­tional com­plex­ity ar­gu­ment us­ing as an ex­am­ple:

Are we headed for a Sin­gu­lar­i­ty? Is it im­mi­nen­t?…But re­gard­less of which de­fi­n­i­tion you use, there are good rea­sons to think that it’s not on the im­me­di­ate hori­zon…This is the so-called ‘hard take­off’ sce­nar­io, also called the FOOM model by some in the sin­gu­lar­ity world. It’s the sce­nario where in a blink of an AI, a ‘god­like’ in­tel­li­gence boot­straps into be­ing, ei­ther by up­grad­ing it­self or by be­ing cre­ated by suc­ces­sive gen­er­a­tions of an­ces­tor AIs. It’s al­so, with due re­spect to Ver­nor Vinge, of whom I’m a great fan, al­most cer­tainly wrong. It’s wrong be­cause most re­al-world prob­lems don’t scale lin­ear­ly. In the real world, the in­ter­est­ing prob­lems are much much harder than that.

Graph of ex­po­nen­tial scal­ing time in chem­i­cal mod­el­ing

started in the 1950s. To­day we have lit­er­ally tril­lions of times more com­put­ing power avail­able per dol­lar than was avail­able at that time. But it’s still hard. Why? Be­cause the prob­lem is in­cred­i­bly non-lin­ear…How fast? The very fastest (and al­so, sad­ly, the most lim­ited and least ac­cu­rate) scale at N2, which is still far worse than lin­ear. By anal­o­gy, if de­sign­ing in­tel­li­gence is an N2 prob­lem, an AI that is 2× as in­tel­li­gent as the en­tire team that built it (not just a sin­gle hu­man) would be able to de­sign a new AI that is only 70% as in­tel­li­gent as it­self. That’s not es­cape ve­loc­i­ty.

A fol­lowup post by Naam, “Why AIs Won’t As­cend in the Blink of an Eye­—­Some Math”, de­scribes it more di­rect­ly:

In my pre­vi­ous post on why the Sin­gu­lar­ity is Fur­ther Than it Ap­pears, I ar­gued that cre­at­ing more ad­vanced minds is very likely a prob­lem of non-lin­ear com­plex­i­ty. That is to say, cre­at­ing a mind of in­tel­li­gence 2 is prob­a­bly more than twice as hard as cre­at­ing a mind of in­tel­li­gence 1. The diffi­culty might go up ex­po­nen­tial­ly. Or it might go up ‘merely’ with the cube or the square of the in­tel­li­gence level you’re try­ing to reach. Blog reader Paul Baum­bart took it upon him­self to graph out how the in­tel­li­gence of our AI changes over time, de­pend­ing on the com­pu­ta­tional com­plex­ity of in­creas­ing in­tel­li­gence.

In­tel­li­gence growth un­der Var­i­ous Diffi­culty As­sump­tions

…Ev­ery other model Paul put into his spread­sheet showed con­ver­gence in­stead of di­ver­gence. Al­most any non-lin­ear diffi­culty in boost­ing in­tel­li­gence means that no run­away oc­curs. (Note that these do not in­clude the ben­e­fit of get­ting new hard­ware over time and gen­eral speedup from Moore’s Law, for so long as that con­tin­ues. But they do in­clude the ben­e­fit of de­sign­ing new hard­ware for it­self or any speedup that it can cause to Moore’s Law.) The bot­tom line, in green, is ex­po­nen­tial diffi­culty (ex). Many re­al-world prob­lems are ex­po­nen­tially diffi­cult as they grow in size. The ‘trav­el­ing sales­man’ prob­lem is an ex­po­nen­tial prob­lem (at least to find an ex­act so­lu­tion). Mod­el­ing quan­tum me­chan­i­cal sys­tems is an ex­po­nen­tial prob­lem. Even some im­por­tant sce­nar­ios of pro­tein fold­ing are ex­po­nen­tially diffi­cult. So it’s not at all un­likely that boost­ing in­tel­li­gence would fall into this cat­e­go­ry. And as you can see,if in­tel­li­gence is ex­po­nen­tially diffi­cult, the su­per-in­tel­li­gence does as­cend.

Or to put it per­haps more clear­ly, for a fixed amount of com­pu­ta­tion, at each greater level of in­tel­li­gence, a smaller in­crease in in­tel­li­gence can be re­al­ized with that amount of com­pu­ta­tion.

A some­what sim­i­lar ar­gu­ment is ges­tured at by Nathan Myhrvold:

The­o­rists have proved that some math­e­mat­i­cal prob­lems are ac­tu­ally so com­pli­cated that they will al­ways be chal­leng­ing or even im­pos­si­ble for com­put­ers to solve. So at least for now, peo­ple who can push for­ward the bound­ary of com­pu­ta­tion­ally hard prob­lems need never fear for lack of work. This tells us some­thing im­por­tant about AI. Like math­e­mat­ics, in­tel­li­gence is not just one sim­ple kind of prob­lem, such as pat­tern recog­ni­tion. It’s a huge con­stel­la­tion of tasks of widely differ­ing com­plex­i­ty. So far, the most im­pres­sive demon­stra­tions of “in­tel­li­gent” per­for­mance by AI have been pro­grams that play games like chess or Go at su­per­hu­man lev­els. These are tasks that are so diffi­cult for hu­man brains that even the most tal­ented peo­ple need years of prac­tice to mas­ter them. Mean­while, many of the tasks that seem most ba­sic to us hu­man­s—­like run­ning over rough ter­rain or in­ter­pret­ing body lan­guage—are all but im­pos­si­ble for the ma­chines of to­day and the fore­see­able fu­ture. As AI gets more ca­pa­ble, the sphere of jobs that com­put­ers can do faster or more ac­cu­rately than peo­ple will ex­pand. But an ex­pand­ing uni­verse of work will re­main for hu­mans, well out­side the reach of au­toma­tion.

Awk­ward­ly, this ar­gu­ment con­tains its own refu­ta­tion: chess/Go are com­pu­ta­tion­ally diffi­cult in pre­cisely the way Myhrvold claims will put math­e­mat­i­cal prob­lems out of reach of com­put­ers, and yet, have al­ready fall­en.1

This can be seen as one of the “struc­tural ob­jec­tions” where the is specifi­cally at­trib­uted to in­cre­ments in com­put­ing power solv­ing less data points as data sizes scale (to use Chalmers 2010’s tax­on­o­my). So the ar­gu­ment (fill­ing in the gaps and omit­ting the var­i­ous graphs show­ing hy­po­thet­i­cal scal­ings) goes some­thing like this:

  1. most tasks an in­tel­li­gent agent (hu­man or ar­ti­fi­cial in­tel­li­gence) needs to solve are in diffi­cult com­plex­ity class­es, such as NP or NP-hard: Trav­el­ing Sales­man, 3-SAT, be­lief prop­a­ga­tion, train­ing, , play­ing , solv­ing
  2. a task in NP or higher com­plex­ity class can only be solved for small prob­lem sizes
  3. if a task can only be solved for small prob­lem sizes, then the best agent will solve only slightly larger prob­lem sizes
  4. the re­al-world re­ward to an agent from solv­ing a slightly larger prob­lem is only slightly greater
  5. the long-term con­se­quence of slightly greater re­wards is it­self small
  6. if an AI be­comes the best agent, then it must solve prob­lems in diffi­cult com­plex­ity classes (1), so it will be able to solve only slightly larger pro­grams (2–3), re­ceiv­ing slightly greater re­wards (4), with only small long-term con­se­quences (5)
  7. if each AI has only small long-term con­se­quences, all AIs to­gether will have a small to­tal long-term con­se­quence
  8. thus, AIs be­com­ing in­tel­li­gent agents will have only small to­tal long-term con­se­quences

This ar­gu­ment is valid as far as it goes and can prob­a­bly be for­mal­ized. But is the ar­gu­ment sound?

Complexity caveats

One diffi­culty with ap­ply­ing com­pu­ta­tional com­plex­ity the­ory out­side its usual area is that peo­ple tend to ne­glect the re­quire­ments of com­plex­ity the­ory which gives it its gen­er­al­i­ty: that it omits the ‘con­stant fac­tors’ and the ac­tual run­time, that many of the state­ments are lower/upper bounds or state­ments about worst-case com­plex­i­ty, that the state­ments tend to be about spe­cific al­go­rithm­s—which are rarely the only way to solve a re­al-world prob­lem—and that it does­n’t try to say any­thing about util­ity or con­se­quences. Sim­i­lar­ly, peo­ple some­times rea­son that since a hu­man and AI would be in the same com­putabil­ity class (Tur­ing-com­plete­ness), that any­thing an AI could do or think, a hu­man must also be able to do or think, but they ne­glect that hu­mans do not have un­bounded time or space like the ide­al­ized Tur­ing ma­chine and there is no more rea­son to ex­pect un­der­stand­ing to be pos­si­ble than to ex­pect an ant to un­der­stand every­thing a hu­man does be­fore it dies of old age; an ant with galax­ies of note­books and bil­lions of years could per­haps un­der­stand hu­man civ­i­liza­tion, but no such ant has ever ex­isted or ever will, and the un­der­stand­ing of that ant of hu­man ac­tion will ul­ti­mately be . The ques­tion of whether such tasks are fea­si­ble for a “com­pact, effi­cient com­puter pro­gram”, not just com­putable, may take on both meta­phys­i­cal and prac­ti­cal sig­nifi­cance (to para­phrase ).

Laid out bare, I would have to say that the ar­gu­ment de­pends crit­i­cally on each of the premises be­ing true, but every premise 1–5 is ei­ther ques­tion­able or false.

Are all problems worst-case and NP-hard?

Premise 1 is in­cor­rect be­cause the proofs of those com­plex­i­ties gen­er­ally de­pend on gen­eral so­lu­tions with de­ter­min­is­tic ex­act­ly-op­ti­mal worst-case be­hav­ior. The ap­par­ent bar­rier of a com­plex prob­lem can be by­passed by (in roughly in­creas­ing or­der of prac­ti­cal im­por­tance):

  1. op­ti­miz­ing com­plex­ity class: ex­ist­ing proofs could be in­cor­rect, in­ap­plic­a­ble (such as as­sum­ing clas­si­cal rather than quan­tum com­put­er­s), or based on open con­jec­tures widely be­lieved by hu­mans one way but which could still re­solve in the more ad­van­ta­geous di­rec­tion (eg )

  2. giv­ing up de­ter­min­ism and us­ing which are faster but or a 2 (they typ­i­cally can be run many times if cor­rect­ness is im­por­tant; after a few times, the prob­a­bil­ity of an er­ror will be smaller than the prob­a­bil­ity that the com­puter hard­ware has suffered ); ran­dom­iza­tion can be ap­plied to al­go­rithms and to data struc­tures.

  3. need­ing good av­er­age-case be­hav­ior rather than worst-case be­hav­ior

    Rather than merge sort, one could use —merge sort has bet­ter worst-case com­plex­ity than Quick­sort (which ren­ders it vul­ner­a­ble to DoS at­tacks if there are ad­ver­saries who can force the worst-case 𝒪(n2)), but Quick­sort is still usu­ally faster. Like­wise, in the worst case, 3-SAT/Traveling Sales­man are wildly in­tractable for any re­al­is­tic dataset like plan­ning a trip across the USA; but the av­er­age-case per­for­mance is quite differ­ent and in prac­tice, 3-SAT/Traveling Sales­man are solved all the time, to the ex­tent where SAT solvers are rou­tinely used in com­puter se­cu­rity or the­o­rem prov­ing or type­-check­ing and lo­gis­tics com­pa­nies are able to heav­ily op­ti­mize their ship­ping with them.

    Sim­i­larly for lin­ear pro­gram­ming’s sim­plex al­go­rithm and other op­er­a­tions re­search al­go­rithms, with are the­o­ret­i­cally in­tim­i­dat­ing but in re­al-world prob­lems yield so­lu­tions after rea­son­able run­time—they work in prac­tice, but not in the­o­ry. For ex­am­ple, TSP in­stances up to 85,900 cities have been solved.

  4. giv­ing up gen­er­al­ity and spe­cial­iz­ing: an al­go­rithm may be un­nec­es­sar­ily gen­er­al.

    A com­par­i­son sort can be done in 𝒪(n · log(n)), yes, but one fre­quently does­n’t need to sort any kind of datatype for which an or­der­ing is avail­able but specifi­cally strings, num­bers, etc, for which quasi linear/𝒪(n) sort­ing is pos­si­ble us­ing /. An al­go­rithm could also have prior in­for­ma­tion about the kind of data in­put which will be avail­able— is aware that most in­puts will be par­tially sorted al­ready and can out­per­form a naive sort. Data struc­tures can be tuned for par­tic­u­lar dis­tri­b­u­tions of data, and & & can be seen as gen­eral al­go­rithms to the cur­rent or like­ly-fu­ture in­puts.

  5. giv­ing up op­ti­mal­ity and com­put­ing an ap­prox­i­ma­tion of the op­ti­mal an­swer (often very close to the op­ti­mal an­swer)

    Al­ready men­tioned is 3-SAT/TSP, for which there is a World Tour of 1,904,711-c­i­ties which has been solved with a tour within 0.0474% of the op­ti­mal tour by 2007, and plan­ning prob­lems sol­u­ble by trans­la­tion into SAT form can have mil­lions of clauses & vari­ables3, en­abling such silly ap­pli­ca­tions as draw­ing por­traits & art us­ing the TSP; Naam gives chem­istry as an ex­am­ple by not­ing that while the ex­act physics is to­tally in­tractable, ap­prox­i­ma­tions which are much more fea­si­ble are used. The last frac­tion of a per­cent­age point of op­ti­mal­ity can take truly enor­mous amounts of com­pu­ta­tion to squeeze out.

  6. chang­ing the prob­lem rather than suc­cumb­ing to func­tional fix­ity: many prob­lems can be re­de­fined or en­vi­ron­ments can be tweaked to by­pass a chal­lenge & lever­age com­puter strengths.

    A may not be as good at vi­sion as a hu­man dri­ver, but sen­sors can be in­cor­po­rated into it in a way that can­not for hu­mans as it would dis­tract them; a may not be as good at dri­ving around as a hu­man work­er, but the en­vi­ron­ment can be al­tered with white lines or bar­code tags on the floor so the ro­bots al­ways know where they are. To quote para­phrase of 4:

    All processes that are sta­ble we shall pre­dict. All processes that are un­sta­ble we shall con­trol.

    Or to quote :

    …This du­al­ity [be­tween re­duc­ing data chan­nel & data source noise] can be pur­sued fur­ther and is re­lated to a du­al­ity be­tween past and fu­ture and the no­tions of con­trol and knowl­edge. Thus we may have knowl­edge of the past but can­not con­trol it; we may con­trol the fu­ture but have no knowl­edge of it.

  7. solv­ing differ­ent non-hu­man prob­lems which hu­mans can­not or will not solve.

    As says, “There are wave­lengths that peo­ple can­not see, there are sounds that peo­ple can­not hear, and maybe com­put­ers have thoughts that peo­ple can­not think.” There are prob­lems hu­mans could never solve be­cause it would re­quire too much train­ing, or too much mem­o­ry, or too bizarre so­lu­tions. A hu­man would never come up with many so­lu­tions that or neural net­works do, and they can be used on scales that hu­mans never would; an unim­por­tant but in­ter­est­ing ex­am­ple would be —I can’t imag­ine any hu­man beat­ing such a CNN, or even try­ing. In such cas­es, scal­ing con­cerns are to­tally be­side the point.

Sev­eral of these cat­e­gories might ring fa­mil­iar to those in­ter­ested in com­puter se­cu­ri­ty, be­cause com­puter se­cu­rity suffers from sim­i­lar is­sues in the at­tempt to close the gap be­tween the the­o­ret­i­cal guar­an­tees about the se­cu­rity of par­tic­u­lar cryp­tog­ra­phy al­go­rithms and what se­cu­rity one gets in prac­tice.

In par­tic­u­lar, the have demon­strated the re­mark­able breadth of ways in which the NSA goes about break­ing com­puter se­cu­rity with­out need­ing ac­cess to the­o­ret­i­cal break­throughs or ex­otic quan­tum com­put­ers (and in­deed, the NSA is more than a lit­tle con­temp­tu­ous of the aca­d­e­mic com­puter security/cryptography com­mu­ni­ties for their mis­guided fo­cus on the­ory at the ex­pense of im­ple­men­ta­tion): com­put­ers can be in­ter­cepted in the mail and hard­ware bugs im­plant­ed; com­put­ers can be mon­i­tored re­motely us­ing var­i­ous ra­dio and phreak­ing de­vices; air­gapped net­works can be jumped by mal­ware hitch-hik­ing on USB dri­ves or buried in­erad­i­cally in­side BIOSes of de­vices like hard dri­ves which have their own proces­sors; data which is not at rest can be stolen from oth­er­wise-se­cure data cen­ters by tap­ping pri­vate fiber op­tic links (eg Google); more pub­lic fiber op­tic ca­bles such as un­der­seas ca­bles are hacked us­ing ISP as­sis­tance and sub­ma­rine op­er­a­tions, in some cases en­tire days of raw traffic be­ing re­tained for analy­sis; en­crypted data can be re­tained for­ever for fu­ture de­cryp­tion (such as by the NSA’s ac­tive quan­tum com­put­ing R&D effort); In­ter­net-wide at­tacks can be mounted by fac­tor­ing cer­tain very com­monly used num­bers us­ing NSA’s large com­pu­ta­tional re­sources and likely spe­cial­ized ASICs (the amor­tized cost of fac­tor­ing many keys si­mul­ta­ne­ously is differ­ent and much smaller than the usu­ally cal­cu­lated cost of crack­ing a sin­gle key); pri­vate keys can be stolen by us­ing sub­poe­nas or na­tional se­cu­rity let­ters or hack­ing in or even phys­i­cal breakins; data can be traded with the in­tel­li­gence agen­cies of other coun­tries or their own hack­ing op­er­a­tions hacked by the NSA (and ); back­doors can be in­tro­duced into oth­er­wise-se­cure soft­ware (D­u­al_EC); com­monly used soft­ware can be ex­ten­sively au­dit­ed, with bugs dis­cov­ered and ex­ploited long be­fore they are pub­licly known (); In­ter­net con­nec­tions can be hi­jacked and di­verted to NSA servers to serve up mal­ware. This gives an idea of the diffi­cul­ties faced when try­ing to be se­cure: where does one trustably get one’s com­puter and the soft­ware on it? How many 0-day vul­ner­a­bil­i­ties are there in the op­er­at­ing sys­tem and all the cryp­to­graphic soft­ware? The en­cryp­tion al­go­rithms may be in­se­cure, or im­ple­mented in­se­cure­ly, or ex­ist de­crypted some­where, or be run on sub­verted hard­ware, or the con­tents in­ferrable from meta­data & other ac­tiv­i­ty.

Hence, the ex­act diffi­culty of in­te­ger fac­tor­ing or the ex­is­tence of one-way func­tions is often among the least of the fac­tors de­ter­min­ing the se­cu­rity of a sys­tem.

Are all implementations equally fast?

“For every poly­no­mi­al-time al­go­rithm you have, there is an ex­po­nen­tial al­go­rithm that I would rather run.”


Premise 3 ig­nores that com­plex­ity classes by de­sign try to ab­stract away from the ‘con­stant fac­tors’ which is the com­pu­ta­tion time de­ter­mined not by in­put size but by the de­tails of com­puter ar­chi­tec­tures, im­ple­men­ta­tions, and avail­able com­put­ing hard­ware. AIs and hu­mans can be equally bound by as­ymp­totic com­plex­i­ty, but still differ on per­for­mance. Scott Aaron­son:

…while P≟NP has tremen­dous rel­e­vance to ar­ti­fi­cial in­tel­li­gence, it says noth­ing about the differ­ences, or lack there­of, be­tween hu­mans and ma­chines. In­deed, P ≠ NP would rep­re­sent a lim­i­ta­tion on all clas­si­cal dig­i­tal com­pu­ta­tion, one that might plau­si­bly ap­ply to hu­man brains just as well as to elec­tronic com­put­ers. Nor does P ≠ NP rule out the pos­si­bil­ity of ro­bots tak­ing over the world. To de­feat hu­man­i­ty, pre­sum­ably the ro­bots would­n’t need to solve ar­bi­trary NP prob­lems in poly­no­mial time: they’d merely need to be smarter than us, and to have im­per­fect heuris­tics bet­ter than the im­per­fect heuris­tics that we picked up from a bil­lion years of evo­lu­tion! Con­verse­ly, while a proof of P=NP might has­ten a ro­bot up­ris­ing, it would­n’t guar­an­tee one.

But with care­fully op­ti­mized code, use of the , and spe­cial­ized hard­ware (eg GPUs, ASICs), it is pos­si­ble to see per­for­mance gains of mul­ti­ple or­ders of mag­ni­tude, which im­plies that one can in­crease the in­put size sev­eral times be­fore hit­ting the scal­ing way that an­other agent might who paid less at­ten­tion to con­stant fac­tors. (Com­pu­ta­tional chem­istry may be in­tractable, even with ap­prox­i­ma­tions, on clas­si­cal hard­ware—but what about if one has a with a few hun­dred qubits, enough that one can do ?) The im­por­tance of con­stant fac­tors is one of the ma­jor traps in prac­ti­cal use of com­plex­ity class­es: a fancy al­go­rithm with a su­pe­rior com­plex­ity class may eas­ily be de­feated by a sim­pler al­go­rithm with worse com­plex­ity but faster im­ple­men­ta­tion.6 (One rea­son that pro­gram­mers are ex­horted to bench­mark, bench­mark, bench­mark!)

This does­n’t dis­prove the com­plex­ity class, which is about as­ymp­totic scal­ing and will still kick in at some point, but if it’s pos­si­ble to dou­ble or dec­tu­ple or more the in­put, this is enough of an in­crease that it’s hard to dis­miss the differ­ence be­tween best and worst agents’ prob­lem sizes as be­ing only ‘slight’.

Fi­nal­ly, in­creased re­source use / brute force is al­ways an op­tion for a pow­er­ful agent. Par­tic­u­larly in his sec­ond post, Naam’s ar­gu­ment as­sumes fixed re­sources. This might be rel­e­vant to a few sce­nar­ios like an AI per­ma­nently con­fined to a sin­gle com­puter and un­able to ac­cess more re­sources—but then, how in­tel­li­gent could such an AI pos­si­bly be if it can’t get out? How­ev­er, thanks to its in­tel­li­gence, hu­man­ity now con­trols a large frac­tion of the bios­phere’s en­ergy and with a su­per­com­put­er, or tech gi­ants like Google or Ama­zon who con­trol mil­lions of proces­sor-cores, can com­pute things to­tally out of reach of other agents; no lim­its to the amount of com­pu­ta­tion that can be done on (or off) Earth have yet been reached. In­creases in com­put­ing re­sources of thou­sands or mil­lions of times, along with larger timescales, can over­come the as­ymp­totic to achieve the next in­tel­li­gence in­crease; if a hu­man-level AI can ‘only’ ac­com­plish a few dozen dou­blings, well…

Are all returns linear?

Premise 4 is where the ar­gu­ment starts try­ing to tie state­ments about com­plex­ity to re­al-world con­se­quences. Naam ar­gues

By anal­o­gy, if de­sign­ing in­tel­li­gence is an N2 prob­lem, an AI that is 2× as in­tel­li­gent as the en­tire team that built it (not just a sin­gle hu­man) would be able to de­sign a new AI that is only 70% as in­tel­li­gent as it­self. That’s not es­cape ve­loc­i­ty.

But this does­n’t make any sense. First, Naam’s re­quire­ment for a Sin­gu­lar­ity is a straw man: ‘es­cape ve­loc­ity’ is not a con­cept any­one has re­quired to be true of the Sin­gu­lar­i­ty; if noth­ing else, there are can be done in the ob­serv­able uni­verse, so it’s un­likely that there is such a thing as an ‘in­fi­nite in­tel­li­gence’. At no point do Good or Vinge say that the Sin­gu­lar­ity is im­por­tant only if the in­crease of in­tel­li­gence can con­tinue eter­nally with­out bound and Vinge is clear that the Sin­gu­lar­ity is a metaphor with no ac­tual in­fin­ity7; in­tel­li­gence in­creases are im­por­tant be­cause wher­ever the im­prove­ments ter­mi­nate, they will ter­mi­nate at a in­tel­li­gence level above hu­man­i­ty, which will give it ca­pa­bil­i­ties be­yond hu­man­i­ty’s. (Good, for ex­am­ple, in his cost pro­jec­tions, ap­pears to have a di­min­ish­ing re­turns model in mind when he spec­u­lates that if hu­man-level in­tel­li­gence can be cre­at­ed, then twice the cost would give a greater-than-hu­man level in­tel­li­gence, and his later em­pha­sis on ‘econ­omy of mean­ing’; and Vinge says the Sin­gu­lar­ity is “the point where our old mod­els must be dis­carded and a new re­al­ity rules”, with­out mak­ing claims about in­defi­nite in­tel­li­gence in­crease, just that con­trol of events will have “in­tel­lec­tual run­away” from hu­man­s—but a run­away train does­n’t in­crease ve­loc­ity ex­po­nen­tially un­til it at­tains the speed of light, it just es­capes its op­er­a­tors’ con­trol.)

Sec­ond, an in­tel­li­gence ex­plo­sion scal­ing even su­per­lin­early at, say, 𝒪(n2) would re­sult in ab­solutely enor­mous prac­ti­cal differ­ences, al­though I can’t un­der­stand what model Naam has in mind ex­act­ly—de­sign­ing in­tel­li­gence can’t lit­er­ally work as he de­scribes with the AI get­ting dumber be­cause the orig­i­nal AI could sim­ply copy it­self to ‘de­sign’ a new AI which is 100% as in­tel­li­gent as it­self at lit­tle com­pu­ta­tional cost, but it’s un­clear what sort of input/output vari­ables are go­ing into this scal­ing equa­tion. Naam’s en­dorse­ment of the spreadsheet/chart in the sec­ond post im­plies that he is think­ing of a model in which the in­put is some un­spec­i­fied unit of com­pu­ta­tion like 1 GPU-year, and the out­put is an ad­di­tional ‘unit’ of in­tel­li­gence, in which case it does make sense to ob­serve that where the AI pre­vi­ously got a 100% in­crease in in­tel­li­gence for spend­ing that 1 GPU-year, now it only gets a <100% in­crease; in this sce­nar­io, it gets a smaller in­crease each com­pu­ta­tion unit and (with ap­pro­pri­ate as­ymp­tot­ics) it may con­verge on some fi­nite up­per bound. But you could just as eas­ily ex­press this re­la­tion­ship the other way around, and note that the num­ber of com­pu­ta­tion units for each dou­bling of in­tel­li­gence is in­creas­ing steeply. Looked at this way, there’s no rea­son to ex­pect con­ver­gence on a fi­nite bound, or even the in­tel­li­gence in­crease to slow down—be­cause the fixed com­pu­ta­tion in­put as­sump­tion be­comes glar­ing; the AI sim­ply “must con­struct ad­di­tional py­lons”, as it were.

A lit­tle per­spec­tive from an­i­mal in­tel­li­gence may be help­ful here; as a sim­ple mod­el, an­i­mal in­tel­li­gence seems closely re­lated to mod­er­ated by . Start­ing at 0, we have the sponge; by 250,000 neu­rons, we have the fly (which can ac­com­plish be­hav­iors like fly­ing around but lit­tle in the way of plan­ning) and the ant (sim­pler lo­co­mo­tion but ca­pa­ble of sim­ple plan­ning and in con­junc­tion with many other ants, sur­pris­ingly com­plex emer­gent be­hav­ior); at 1,000,000, we have the frus­trat­ingly tough cock­roach, and at 16,000,000, the frog; by 71,000,000, the com­mon house mouse, which can be taught tricks, solve com­plex plan­ning tasks and mazes, and is re­spectably in­tel­li­gent. Clearly the scal­ing here is not lin­ear—it’s hard to ar­gue that the mouse is 284 times smarter than a fly. The scal­ing gets worse as we con­tin­ue; the star-nosed mole has 131,000,000 but is it twice as in­tel­li­gent as the house mouse? Only at the oc­to­pus with 500,000,000 does one rec­og­nize a real differ­ence in in­tel­li­gence, and thank­fully the cat shows up at 760,000,000. But for a crea­ture which has ~11× the neu­rons, the cat does­n’t seem to be as good at catch­ing mice as one might ex­pect! From there, the neu­ron count gets worse and worse—­ca­puchins need al­most 4 bil­lion neu­rons, macaques al­most dou­ble that, and hu­mans re­quire a cool 86 bil­lion neu­rons, 113× a cat (with ele­phants at 267 bil­lion, but as much as those neu­rons are used up by their enor­mous body size, they are still eeri­ly, dis­turbing­ly, in­tel­li­gent) Plot­ted on a graph by some for­mal or in­for­mal mea­sure­ment of be­hav­ioral com­plex­i­ty, we have a su­per-lin­ear as­ymp­tot­ic; an­i­mal psy­chol­o­gists are al­ways dis­cov­er­ing ways in which hu­man be­hav­iors have roots in an­i­mal an­tecedents, im­ply­ing that hu­mans are, on an ab­solute lev­el, not that much smarter. Surely each neu­ron added along the way suffered from di­min­ish­ing re­turns. We al­ready live in a world with di­min­ish­ing re­turns to com­pu­ta­tional re­sources! Yet, de­spite that as­ymp­tot­ic, it clearly has been pos­si­ble for hu­mans to defy this scal­ing and de­velop brains with al­most a hun­dred bil­lion neu­rons (and ele­phants triple that) and con­sid­er­able room for fur­ther growth (), and this evo­lu­tion has also led to enor­mous re­al-world con­se­quences: hu­mans not just con­trol the earth, they have re­made it in their own im­age, dri­ven count­less species ex­tinct or to the brink of ex­tinc­tion (as other pri­mates can at­test) as hu­mans (and their world) changes faster than most species are able to adapt, and done im­pos­si­ble things like gone to the moon. And all this in a blink of an eye.

Aside from the is­sue that the com­plex­ity claims are prob­a­bly false, this one is par­tic­u­larly ques­tion­able: small ad­van­tages on a task do trans­late to large re­al-world con­se­quences, par­tic­u­larly in com­pet­i­tive set­tings. A horse or an ath­lete wins a race by a frac­tion of a sec­ond; a stock­-mar­ket in­vest­ing edge of 1% an­nu­ally is worth a bil­lion­aire’s for­tune; a slight ad­van­tage in pick­ing each move in a game likes chess trans­lates to al­most cer­tain vic­tory (con­sider how rank­ing changed with ); a logistics/shipping com­pany which could shave the re­main­ing 1–2% of in­effi­ciency off its plan­ning al­go­rithms would have a ma­jor ad­van­tage over its ri­vals inas­much as ship­ping is one their ma­jor costs & the profit mar­gin of such com­pa­nies is it­self only a few per­cent­age points of rev­enue; or con­sider & win­ner-take-all mar­kets. (Or think about safety in some­thing like self­-driv­ing cars: even a small ab­solute differ­ence in ‘re­ac­tion times’ be­tween hu­mans and ma­chines could be enough to drive hu­mans out of the mar­ket and per­haps ul­ti­mately even make them il­le­gal.)

Turn­ing to hu­man in­tel­li­gence, the ab­solute range of hu­man in­tel­li­gence is very small: differ­ences in re­ac­tion times are small, s range from 3–7, brain imag­ing stud­ies have diffi­culty spot­ting neu­ro­log­i­cal differ­ences, the ab­solute ge­netic in­flu­ence on in­tel­li­gence is on net min­i­mal, and this nar­row range may be a gen­eral phe­nom­e­non about hu­mans (Wech­sler 1935); and yet, in hu­man so­ci­ety, how crit­i­cal are these tiny ab­solute differ­ences in de­ter­min­ing who will be­come rich or poor, who will be­come a crim­i­nal, who will do cut­ting-edge sci­en­tific re­search, who will get into the Ivy Leagues, who will be a suc­cess­ful politi­cian, and this holds true as high as IQ can be mea­sured re­li­ably (see ). (I think this nar­row­ness of ob­jec­tive per­for­mance may help ex­plain why some events sur­prise a lot of ob­servers: when we look at en­ti­ties be­low the hu­man per­for­mance win­dow, we just see it as a uni­form ‘bad’ level of per­for­mance, we can’t see any mean­ing­ful differ­ences and can’t see any trends, so our pre­dic­tions tend to be hi­lar­i­ously op­ti­mistic or pes­simistic based on our prior views; then, when they fi­nally en­ter the hu­man per­for­mance win­dow, we can fi­nally ap­ply our ex­ist­ing ex­per­tise and be­come sur­prised and op­ti­mistic, and then the en­ti­ties can with small ob­jec­tive in­creases in per­for­mance move out of the hu­man win­dow en­tirely and it be­comes an ac­tiv­ity hu­mans are now un­com­pet­i­tive at like chess (be­cause even grand­mas­ters are con­stantly mak­ing mis­takes8) but may still con­tribute a bit on the mar­gin in things like , and within a few years, be­comes truly su­per­hu­man.)

This also ig­nores the many po­ten­tial ad­van­tages of AIs which have noth­ing to do with com­pu­ta­tional com­plex­i­ty; Al­phaGo may con­front the same that hu­man Go play­ers do, but as soft­ware it is im­mor­tal and can be con­tin­u­ously im­proved, among other ad­van­tages (So­tala 2012, ).

Are all scenarios one-shot?

Premise 5 would seem to as­sume that there is no such thing as com­pound in­ter­est or ex­po­nen­tial growth or that small ad­van­tages can ac­cu­mu­late to be­come crush­ing ones; which of course there is for com­pa­nies, coun­tries, and in­di­vid­u­als alike.

Some­thing sim­i­lar has been noted about hu­man in­tel­li­gence—while any par­tic­u­lar day-to-day de­ci­sion has lit­tle to do with in­tel­li­gence, the effects of in­tel­li­gence are con­sis­tently ben­e­fi­cial and ac­cu­mu­late over a life­time, so the ran­dom noise starts to can­cel out, and in­tel­li­gence is seen to have strong cor­re­la­tions with long-term out­comes (eg ). More ab­stract­ly, many ca­reer or in­tel­lec­tual out­comes have been no­ticed to fol­low a roughly (Burt 1943; , Mur­ray 2003); a log-nor­mal dis­trib­uted can be gen­er­ated when an out­come is caused by a ‘leaky pipeline’ (sci­en­tific out­put might be due to mo­ti­va­tion times in­tel­li­gence times cre­ativ­i­ty…), in which case a small im­prove­ment on each vari­able can yield a large im­prove­ment in the out­put.9 For re­peated ac­tions, ad­van­tages can build up. A chess ex­am­ple: may be the strongest hu­man chess player in his­to­ry, with a peak rat­ing of ~2882; as of 2016, the top-rated is prob­a­bly Ko­modo at ELO 3358. The ELO ex­pected score for­mula im­plies that if Ko­modo 2016 played peak Carlsen, it would have an ex­pected score of , so it would win ~94% of its games; this is im­pres­sive enough (it would lose only 1 time out of 20), how­ev­er, in the stan­dard 5-game match, it would win not 94%, but ~99.8% of the 5-game matches (los­ing only 1 time out of 500). One thinks of Ama­ra’s law: “We tend to over­es­ti­mate the effect of a tech­nol­ogy in the short run and un­der­es­ti­mate the effect in the long run.”

Are AI agents rare?

Ex­pand­ing on the ob­ser­va­tion that AIs can have ad­van­tages which are un­re­lated to com­pu­ta­tional com­plex­ity or solv­ing larger in­stances of prob­lems, is it re­ally the case that a Sin­gu­lar­ity can hap­pen only if AIs are able to sur­pass hu­mans on par­tic­u­lar al­go­rith­mic tasks? This is un­like­ly. For ex­am­ple, in a sce­nario (Sand­berg & Bostrom 2008), such up­loaded minds would not nec­es­sar­ily be gifted with any new ac­com­plish­ments with re­gard to com­plex­ity classes but can we re­ally swal­low the ar­gu­men­t’s con­clu­sion that this sce­nario sim­ply can­not lead to any ma­jor changes wor­thy of the name Sin­gu­lar­i­ty? Far from it—it seems that such an achieve­ment would rad­i­cally change hu­man so­ci­ety in a num­ber of ways, rang­ing from re­defin­ing mor­tal­ity to ac­cel­er­at­ing neu­ro­science to trans­for­ma­tions of the econ­omy as such em­u­lated brains can be copied in­defi­nitely onto as much hard­ware as is avail­able (con­sider ex­trap­o­la­tions in Age of Em; a world-cham­pi­on-level hu­man Go player re­quires mil­lions of chil­dren sam­pled and 15+ years to train, while an Al­p­haZero is sim­ply copied over to an­other com­put­er). It would be sur­pris­ing if one could run hu­man-level in­tel­li­gences (per­haps ar­bi­trar­ily many of them) on a pocket smart­phone, with mil­lions or bil­lions of them across the world, even out­num­ber­ing reg­u­lar bi­o­log­i­cal hu­mans, and still have no ‘Sin­gu­lar­ity’ through sheer num­bers.

Parable of the Worms

ex­plains to Spi­der-Man why he is un­friend­ly.

Once upon a time, two worms were de­bat­ing the prospect of “transwormism”, and specifi­cally the pos­si­bil­ity of hy­po­thet­i­cal crea­tures from else­where in the space of all pos­si­ble or­gan­isms, which might ex­ceed worms by as much as worms ex­ceed the bac­te­ria they thrive up­on, and the im­pli­ca­tions for their pile of com­post­ing ma­nure which con­tains their worm civ­i­liza­tion. Was this pos­si­ble? Could all species be ranked on some sort of ‘in­tel­li­gence’ or ‘power’ met­ric? Where would the re­sources to sup­port such en­ti­ties come from, and how would they be able to do any­thing more than worms them­selves could do? Crawlviati ar­gues for transwormism:

"There is no a pri­ori rea­son to be­lieve that worms must be the pin­na­cle of cre­ation, and that there are no larger or more com­plex or more in­tel­li­gent or­gan­isms pos­si­ble. We should be ap­ply­ing the Pooper­ni­can Prin­ci­ple here—‘the ma­nure piles in which we live are but a tiny seg­ment of the uni­verse in both space and time, of no priv­i­leged per­spec­tive’, and so in the Great Chain of Eat­ing, we should ex­pect us to be in a mediocre po­si­tion.

In­deed, from the start of life, we can see many break­throughs: mul­ti­cel­lu­lar life has pro­duced end­less forms most differ­ent from uni­cel­lu­lar life, while fairly re­cently have neu­rons been in­vented & just in­creas­ing neu­ron count seems to yield con­sid­er­able gains (look at us ver­sus bac­te­ri­a), so we live at an ex­cit­ing time. We can spec­u­late about the pos­si­bil­i­ties: a transworm might be com­pletely differ­ent from us worms; or it might be sim­i­lar in ar­chi­tec­ture to us worms, per­haps with a much longer body with many more neu­rons and so much smarter than us.

Re­gard­less, a transworm would be diffi­cult for us to pre­dict, and may be able to de­velop very fast as it learns new ways of hunt­ing bac­te­ria and self­-fer­til­iza­tion, in what we might call a ‘Moundu­lar­ity’ in which it piles up re­sources and off­spring faster than any­one else; inas­much as a transworm may have very differ­ent pri­or­i­ties from us and change the en­vi­ron­ment to fit its needs, it would be dan­ger­ous to us."

Slimepli­cius dis­agrees:

"Ridicu­lous! Think for a mo­ment about your claims. We are blessed with 302 neu­rons, with which we can re­act to stim­uli, move for­ward, move back­ward, hunt bac­te­ria, and solve chal­leng­ing nav­i­ga­tional puz­zles of many wor­m-lengths.

But these prob­lems ex­hibit di­min­ish­ing re­turn­s—­worm­pu­ta­tional com­plex­ity the­ory tells us that op­ti­mal maze nav­i­ga­tion is ex­po­nen­tially diffi­cult, for ex­am­ple, and many im­por­tant prob­lems are worse. Transworms would im­me­di­ately find their ad­di­tional cog­ni­tion to be of ever less mar­ginal value as they run up against the wall of worm­pu­ta­tional com­plex­i­ty.

What could they pos­si­bly do with, say, 1000 neu­rons that would jus­tify a meta­bolic cost over 3 times greater? And to be truly wor­thy of the name transworm, they might need tens of thou­sands, or even mil­lions of neu­rons! (I won’t even bother to de­bunk fan­ci­ful ex­trap­o­la­tions to bil­lions of neu­rons, which would be more than ex­ist in pos­si­bly all the ma­nure piles in our ob­serv­able uni­verse put to­geth­er.)

Con­sider the ab­sur­dity of such an ar­chi­tec­ture: could our ma­nure pile sup­port a sin­gle such transworm? Where would the food come from? For that mat­ter, how would its body sup­port so many neu­rons? And its genes could no longer spec­ify cell place­ment one by one, but or­ga­ni­za­tion would have to some­how ‘emerge’ or be ‘learned’, and you are rather ob­scure about how this might hap­pen.

Not to men­tion the many enor­mously com­pli­cated prac­ti­cal en­gi­neer­ing prob­lems you seem to gloss over in your blind faith in progress and lines on graphs: for ex­am­ple, diffu­sion would no longer work to feed each cell, re­quir­ing novel mech­a­nisms solely to move flu­ids around to avoid over­heat­ing or starv­ing to death.

If a transworm could ex­ist, it would be ex­po­nen­tially diffi­cult for it to eat bac­te­ria and re­pro­duce faster than reg­u­lar worms, and its per­for­mance would likely con­verge with ours: it would solve our prob­lems only slightly bet­ter than us, at tremen­dously in­creased cost. Con­sider Tur­ing-com­plete­ness: any­thing a transworm could com­pute, us worms could also com­pute, is it not so? (We could even make an evo­lu­tion­ary ar­gu­ment: we have evolved to be as smart as is op­ti­mal in our niche—and no more or less.)

Cer­tain­ly, any ‘Moundu­lar­ity’ would be so slow that us worms would smell it com­ing long in ad­vance and wrig­gle to­gether in a big ball to crush it."


"Y­our ar­gu­ment seems overly nar­row to me. Yes, I agree that it would be diffi­cult to sup­port so many neu­rons packed to­gether in one worm, but I’m sure the en­gi­neer­ing diffi­cul­ties can be over­come—there seems to be no fun­da­men­tal limit to worm­pu­ta­tion much greater than 302 neu­rons, so there must be a way. And your food ob­jec­tion is like­wise sol­uble: per­haps transworms can mi­grate from com­post pile to gar­den to com­post pile reg­u­larly as they ex­haust re­sources in each one, or even fig­ure out some way to eas­ily knock down low-hang­ing fruit & let them rot.

They may not, bac­terium for bac­terium or cell for cell, be as effi­cient as us, but that does­n’t mat­ter as long as the di­min­ish­ing re­turns don’t turn into neg­a­tive re­turns. As long as the re­turns are pos­i­tive, they will be able to pay for their in­creased re­source uti­liza­tion and con­tinue climb­ing up the ex­po­nen­tial curves.

And what does ‘bet­ter’ even mean here? The worm­pu­ta­tional com­plex­ity of a maze may in­crease sharply with maze size, but that’s a state­ment about mazes, not about com­par­ing maze-solvers, which might be ar­bi­trar­ily bet­ter or worse than each oth­er, so there’s a prob­lem: maybe they could solve mazes 100× faster.

Then there’s fig­ur­ing out what any bit of per­for­mance means: if a transworm could solve mazes twice as fast as you or I, maybe it’ll get all the rot­ting food when it beats us in a race to the end, and not less than twice as much.

Heck, we’re worms—what do we know about the world? Maybe there’s more to life, the mound and every­thing; per­haps there are all sorts of cool things we could do, be­sides ‘stim­u­lus, re­spon­se; stim­u­lus, re­spon­se; stim­u­lus, re­sponse’—if we could just think for once in our lives!"


“These claims seem to rest en­tirely on what I might call an ap­peal to ig­no­rance: maybe mazes can be run faster than we can, maybe there are great things which could be done with more neu­rons, maybe there’s lots of food we can’t ob­tain but could with more in­tel­li­gence… Sure, maybe I can’t prove that there aren’t, but is any of this what a rea­son­able worm, the or­di­nary worm in the dirt, would be­lieve? Cer­tainly not. We are the pin­na­cle of civ­i­liza­tion, and can hardly be ex­pected to be­lieve in the pos­si­bil­ity of ‘transworms’ with­out even a live ex­am­ple of a transworm to point to. Cre­ate a transworm and per­haps then I will take your wild spec­u­la­tions more se­ri­ous­ly.”

Crawlvi­ati, plain­tive:

“If you’ll just think a lit­tle more about the pos­si­bil­i­ties…”

Slimepli­cius, dis­mis­sive­ly:

“There are bet­ter things to worry about: like pile warm­ing. What if our wastes and their de­cay make our mound too hot for us? We should dis­cuss that in­stead.”

So they did. A week lat­er, the farm was sold to a real es­tate de­vel­oper to build town­houses on. The mound was flat­tened by a steam roller, and then paved over with as­phalt—the con­struc­tion work­ers nei­ther loved nor hated the worms, but the worms had noth­ing to offer in trade, and were made of atoms use­ful for widen­ing the new road to make some hu­mans’ com­mute ever so slightly faster.


Com­pu­ta­tional com­plex­ity classes offer lit­tle guid­ance about the ca­pa­bil­i­ties of hu­mans, AIs, or other agents as they are too uni­ver­sal and gen­er­al­ized and do not tightly bind out­comes; at most, they demon­strate that nei­ther hu­mans nor AIs are om­nipo­tent. If one wants to put lim­its on the abil­ity of an AI by way of com­pu­ta­tional re­sources, a much more de­tailed analy­sis must be done link­ing data/sample effi­ciency or al­go­rith­mic per­for­mance to ca­pa­bil­ity im­prove­ment to per­for­mance on an en­sem­ble of tasks & ac­cess to ad­di­tional re­sources, with the con­se­quent eco­nom­ic, mil­i­tary, or so­cial out­comes.

See Also


Technology forecasting errors: functional fixedness in assuming dependencies

“Gal­lant fel­lows, these sol­diers; they al­ways go for the thick­est place in the fence.”

, of the 10

“In ex­press­ing full func­tion, there are no fixed meth­ods.”


A clas­sic cog­ni­tive bias in tech­no­log­i­cal fore­cast­ing is mo­ti­vat­ed-stop­ping and lack of imag­i­na­tion in con­sid­er­ing pos­si­bil­i­ties. Many peo­ple use a men­tal model of tech­nolo­gies in which they pro­ceed in a se­r­ial se­quen­tial fash­ion and as­sume every step is nec­es­sary and only all to­gether are they suffi­cient, and note that some par­tic­u­lar step is diffi­cult or un­likely to suc­ceed and thus as a whole it will fail & never hap­pen. But in re­al­i­ty, few steps are truly re­quired. Progress is pre­dictably un­pre­dictable: A tech­nol­ogy only needs to suc­ceed in one way to suc­ceed, and to fail it must fail in all ways. There may be many ways to work around, ap­prox­i­mate, brute force, re­duce the need for, or skip en­tirely a step, or re­de­fine the prob­lem to no longer in­volve that step at all. Ex­am­ples of this in­clude the par­al­lel projects used by the Man­hat­tan Project & Apollo pro­gram, which rea­soned that de­spite the for­mi­da­ble diffi­cul­ties in each path to the end goal, at least one would work out­—and they did. In fore­cast­ing, to counter this bi­as, one should make a strong effort to imag­ine all pos­si­ble al­ter­na­tives which could be pur­sued in par­al­lel, and re­mem­ber that over­all fail­ure re­quires all of them to fail.

One of the most com­mon er­rors in crit­i­ciz­ing a tech­nol­ogy or in fore­cast­ing fu­ture progress is to en­gage in overly rigid in­ter­pre­ta­tion of what that tech­nol­ogy is: to as­sume that it will be the same in 20 years as it is now, us­ing the same com­po­nents to achieve the same goals, and each com­po­nent help­lessly de­pen­dent on an­other com­po­nent such that fail­ure of one is fail­ure of all. This then leads to pes­simistic ex­trap­o­la­tions and as­sump­tions of im­mi­nent fail­ure which will look comic in ret­ro­spect. And too often a critic set­tles for find­ing a sin­gle way in which, if a tech­nol­ogy were im­ple­mented or used in the dumb­est way pos­si­ble, that would be bad, as if that was the only way pos­si­ble or if mis­use were uni­ver­sal­ly-inevitable, and de­clares the ques­tion set­tled. (One is re­minded of the joke about a pa­tient who goes to the doc­tor, as­sumes a yoga po­si­tion, and com­plains, “doc­tor, it hurts when I do this!”, to which he replies, “don’t do that, then.”)

The core mis­take in this fal­lacy is rem­i­nis­cent of the cre­ativ­ity tests which ask the sub­ject to ac­com­plish a task like mak­ing a can­dle holder from com­mon ob­jects like a box of soap and thumb­tacks, or to come up with as many pos­si­ble uses for a brick as pos­si­ble; a sub­ject who in­sists that a brick is a brick, and will not reimag­ine the box of soap as an open box which could be mounted on the wall, will never solve the tasks well, will be sur­prised when oth­ers ac­com­plish it eas­i­ly, and per­haps feel deep down that the oth­ers cheated (even if it worked per­fectly well).

Defin­ing a sys­tem, one might treat it as a “con­junc­tive” sys­tem where every­thing has to work: D de­pends on C1, C1 de­pends on B1, and B1 de­pends on A1; so if any prob­lem is found is A1, B1, or C1, the en­tire sys­tem can be treated as de­bunked and an im­pos­si­ble con­trap­tion. It suffices to show that prob­a­bly A1~, so prob­a­bly ~D too. The prob­lem with this way of think­ing is that it may be ad­e­quate for im­me­di­ate crit­i­cism of a spe­cific sys­tem and a use­ful ap­proach for en­gi­neer­ing it, but it is not the same thing as an­swer­ing whether D will be ac­com­plished in 10 years or if the sys­tem is a good idea! Be­cause such a crit­i­cism can be fixed by us­ing a differ­ent A2, or per­haps A3, or A4, or A5, or A6, or maybe not even need­ing some­thing like A at all and switch­ing to a differ­ent sys­tem {D, X1, Y1, Z1}. The critic asks “is there any way this sys­tem might not work?” and stops there; but the fore­caster asks, “is there any sys­tem with a way that works?” and keeps go­ing.

Most tech­nol­ogy goals are “dis­junc­tive” in the sense that “any­thing goes” as long as it ac­com­plishes the fi­nal goal, and it does­n’t mat­ter how many dead ends get tried. If one way ‘hurts’, “don’t do that, then” and find a differ­ent way. The critic needs to dis­prove all pos­si­ble ways, and not just fall for the in set­tling for us­ing their ex­per­tise for the far eas­ier (and far more use­less) task of scat­ter­ing around doubts about a hand­ful of ways. To fly, it is not nec­es­sary to recre­ate a bird’s wing, only to find some way to fly­—and there turn out to be many differ­ent propul­sion meth­ods which suc­ceed at the task of flight but bear lit­tle re­sem­blance to how a bird flies (hot air, lighter-than-air gas­es, pro­pellers, jet en­gi­nes, ram­jets, rock­ets, glid­er­s). A critic of the Wright or Mont­golfier broth­ers would have been per­fectly cor­rect in not­ing that their meth­ods could not and would never lead to bird flight, and wrong if they had then tried to pro­claim that hu­man flight was im­pos­si­ble or cen­turies away. Sim­i­lar­ly, the Man­hat­tan Project and the Apollo Project had a spe­cific tech­nol­ogy goal, but the goal was dis­junc­tive in that any of sev­eral meth­ods of re­fin­ing ura­nium or plu­to­nium or go­ing to the Moon could have achieved the goal, each had for­mi­da­ble tech­no­log­i­cal & sci­en­tific ob­sta­cles and had crit­ics pre­dict­ing fail­ure, but only one had to work out; with money no ob­ject, they pur­sued mul­ti­ple meth­ods in par­al­lel, and at least one did work out. Sim­i­lar­ly, Thomas Edi­son knew many peo­ple had failed to cre­ate a use­ful elec­tric light­bulb be­fore him, and failed to cre­ate one him­self after try­ing out hun­dreds of vari­ants; did this mean that an elec­tric light­bulb would never be in­vent­ed? No, it just meant that he had to keep try­ing fil­a­ments un­til he found one that worked, and that was all he need­ed. One might analo­gize R&D to com­puter hack­ers: both share a se­cu­rity mind­set where they only need to find one way in past the de­fenses thrown up in their path by Na­ture or cor­po­ra­tions; if the fire­wall can’t be pen­e­trat­ed, then try hack­ing their print­er, in­ject a into their servers, or just try call­ing up the sec­re­tary, say you’re the CEO, and ask for the pass­word!

There is rarely a need to be rigid about the ex­act method, as long as the re­sult works; we are free to be flex­i­ble.

If vir­tual re­al­ity head­sets re­quire 4K res­o­lu­tion per eye to de­liver sat­is­fac­tory VR ex­pe­ri­ences but this is too hard for GPUs to ren­der fast enough, does this prove VR is im­pos­si­ble, or does it sim­ply mean we must get a lit­tle cre­ative and ex­plore al­ter­na­tive so­lu­tions like us­ing “foveated ren­der­ing” to cheat and ren­der only a frac­tion of the 4K? In 10 years, should you ex­pect this to be an is­sue? No, be­cause res­o­lu­tion & qual­ity is a dis­junc­tive prob­lem, just like mo­tion-sick­ness in VR be­fore it, which was fixed by a com­bi­na­tion of con­tin­u­ous resolution/optics/FPS/locomotion/controller-hand-tracking/software/game-design fix­es; there is no com­po­nent which can be proven to be un­fix­able and uni­ver­sal across all pos­si­ble so­lu­tions. If vac­uum tubes will, for good physics rea­sons, cease to be shrink­able soon, does that mean Moore’s law is doomed and com­put­ers will al­ways be ENIAC-sized, or, is it a con­junc­tive prob­lem where any com­pu­ta­tional sub­strate can work, and the sig­moid of vac­uum tubes will be re­placed by other sig­moids of tran­sis­tors, main­tain­ing Moore’s law into the mod­ern era? (In­deed, any ex­po­nen­tial growth may turn out on closer in­spec­tion to be a stack of sig­moid growths, where al­ter­na­tives are reg­u­larly found in or­der to make fur­ther pro­gress; a cor­rect ar­gu­ment that a par­tic­u­lar tech­nol­ogy will soon top out still does not prove that the ex­po­nen­tial growth will stop, which would re­quire prov­ing that no al­ter­na­tives would be found after the cur­rent sig­moid.) If GOFAI ex­pert sys­tems turn out to not be great, are ex­pert sys­tems a con­junc­tive prob­lem where they are the only pos­si­ble way of ap­proach­ing ar­ti­fi­cial in­tel­li­gence, or can ar­ti­fi­cial in­tel­li­gence be solved in many ways and progress con­tin­ue? If Bit­coin trans­ac­tions are only pseu­do­ny­mous and cryp­tocur­rency blockchains scale poor­ly, are those con­junc­tive or dis­junc­tive prob­lems? (The an­swer should be easy even if you do not fol­low all the pro­pos­als for im­prove­ments like SegWit/Mimblewimble/sharding/MAST/scriptless scripts/Schnorr etc.) If ge­netic stud­ies like GWASes are only able to ex­plain a small per­cent­age of mea­sured in­di­vid­ual differ­ences at a par­tic­u­lar point in time, does that prove GWASes are a failed method­ol­ogy and that ge­net­ics in gen­eral is unim­por­tant, or should we note that data will con­tinue pil­ing up and that there are a dozen ways in which GWASes are in­effi­cient & we ex­pect the growth in pre­dic­tive power to con­tin­ue? How many differ­ent sen­sors could self­-driv­ing cars draw on to achieve hu­man-level safe­ty? etc. A sim­i­lar ob­ser­va­tion holds for im­pos­si­bil­ity proofs and no-go the­o­rems.12

Often, these ar­gu­ments seem im­pres­sive but in prac­tice, peo­ple con­tinue to do the im­pos­si­ble or go where they should­n’t; why?

The proofs may be en­tirely cor­rect, but as with any proof’s as­sump­tions and the­o­rem, the devil is in the de­tails: per­haps the as­sump­tions are not plau­si­ble in the first place, or the the­o­rem does­n’t mean what you thought it meant. It might be im­pos­si­ble to cre­ate an al­go­rithm with 100% ac­cu­ra­cy, but the er­rors oc­cur only on in­puts that never oc­cur, or the re­sult is an ap­prox­i­ma­tion which is how­ever in­dis­tin­guish­able from an ex­act an­swer for all in­tents & pur­poses or is less likely to be wrong than one’s com­puter or brain to be hit by a cos­mic ray or stroke while think­ing it through. And so on. A rel­e­vant ex­am­ple of this phe­nom­e­non comes up in dis­cussing AI risk: one type of ar­gu­ment that AIs can­not ever be dan­ger­ous and AI risk is not real re­lies on an ar­gu­ment from worst-case al­go­rith­mic com­plex­i­ty, ob­serv­ing that many im­por­tant prob­lems like 3SAT are NP-hard, where the re­quired com­pu­ta­tion quickly in­creases to in­fea­si­ble lev­els, so hu­mans and AIs must be equiv­a­lently in­tel­li­gent, there­for AIs can­not be dan­ger­ous (see above); un­for­tu­nate­ly, every premise is vul­ner­a­ble—­worst-case is often ir­rel­e­vant, the ig­nored con­stant fac­tors can be crit­i­cal, small differ­ences in intelligence/capability can have large com­pound­ing effects par­tic­u­larly in com­pe­ti­tions, prob­lems can be re­arranged to by­pass or make them eas­ier, ex­tremely large amounts of com­pu­ta­tion can be thrown at prob­lems, AIs could have many ad­van­tages like im­mor­tal­ity which are sim­ply or­thog­o­nal to com­pu­ta­tional com­plex­i­ty, etc. There is noth­ing wrong with the proofs of what com­plex­ity class 3SAT is in, it’s just that what is proven is not nec­es­sary to the ar­gu­ment and what is nec­es­sary to the ar­gu­ment is not proven.

When is it valid to ar­gue from a con­junc­tive per­spec­tive?

Some­times, it is pos­si­ble to come up with a uni­ver­sal proof like one based on laws of physics; if a goal turns out to be ther­mo­dy­nam­i­cally or in­for­ma­tion-the­o­ret­i­cally im­pos­si­ble, that’s a good hint that no one is go­ing to achieve it. So for the much-de­bated pos­si­bil­ity of cry­on­ics, a valid dis­proof would be to demon­strate that all the rel­e­vant in­for­ma­tion in the hu­man brain is lost or de­stroyed within minutes/hours of death; an in­valid con­junc­tive dis­proof would be to set up a chain of prob­a­bil­i­ties like “10% chance you die in a hos­pi­tal, 10% chance you are vit­ri­fied within a few hours, 10% chance ALCOR does­n’t go bank­rupt, 10% chance your body can be re­grown health­ily… thus, there’s ~0% chance it’ll work”, be­cause each step is not re­ally con­junc­tive but dis­junc­tive (one can die else­where, the time win­dow is not known, a cry­on­ics or­ga­ni­za­tion bank­ruptcy ≠ rethaw­ing, grow­ing bod­ies is not the only pos­si­ble good out­come, etc).

Other times a tech­nol­ogy may be in­her­ently bot­tle­necked at a step all of which pos­si­ble im­ple­men­ta­tions are very diffi­cult and it be­comes qua­si­-con­junc­tive, ver­sus a com­pet­ing par­a­digm which is dis­junc­tive. An ex­am­ple there is it­er­ated em­bryo se­lec­tion (IES) vs genome syn­the­sis for cre­at­ing ul­tra­-high­ly-op­ti­mized hu­man genomes: it­er­ated em­bryo se­lec­tion re­quires close con­trol over con­vert­ing stem cells to ga­metes and back in or­der to ex­ert se­lec­tion pres­sure over many ‘gen­er­a­tions’ to op­ti­mize for par­tic­u­lar traits, and given the trick­i­ness of coax­ing cells into re­gress­ing to stem cells and de­vel­op­ing into par­tic­u­lar cell types, there is prob­a­bly only one effec­tive pro­ce­dure and no real al­ter­na­tives; but ‘genome syn­the­sis’ is sim­ply the idea of syn­the­siz­ing an en­tire hu­man genome from scratch to a pre-spec­i­fied op­ti­mal­ly-de­signed genome, and, like the many com­pet­ing tech­niques in genome se­quenc­ing, there are many differ­ent meth­ods of com­bin­ing nu­cleotides to build up a cus­tom genome, which con­tribute to the (yes, ex­po­nen­tial) fall in genome syn­the­sis costs, and many fur­ther meth­ods pro­posed (like spe­cial­ized yeast) to re­duce costs even fur­ther to the point where hu­man genomes can be syn­the­sized for a few mil­lion dol­lars each (and then reused ar­bi­trar­ily often). IES is strongly con­junc­tive: if the stem cell steps can’t be solved, the en­tire cy­cle falls apart; genome syn­the­sis is dis­junc­tive: any of sev­eral meth­ods can be used to syn­the­size nu­cleotides, and many more can be tried. Which one can we ex­pect first? IES has a con­sid­er­able head­start but genome syn­the­sis pro­gresses like a metronome be­cause if it gets blocked on one track, it can hop to an­oth­er; so my money is on genome syn­the­sis at the mo­ment.

So in fore­cast­ing some­thing like GWASes, Bit­coin, or VR, here are some use­ful ques­tions to ask:

  1. Are there any hard con­straints from pow­er­ful the­o­ries like ther­mo­dy­nam­ics, evo­lu­tion, or eco­nom­ics bound­ing the sys­tem as a whole?
  2. Break­ing down by func­tion­al­i­ty, how many differ­ent ways are there to im­ple­ment each log­i­cal com­po­nent? Is any step a se­ri­ous bot­tle­neck with no ap­par­ent way to cir­cum­vent, re­de­fine, or solve with brute force?
  3. Do its past im­prove­ments de­scribe any lin­ear or ex­po­nen­tial trend? What hap­pens if you ex­trap­o­late it 20 years (in the grand scheme of things, a mi­nor er­ror of tim­ing)? If the trend is ex­po­nen­tial, is it a set of stacked sig­moids in­di­cat­ing con­sid­er­able flex­i­bil­ity in choice of technology/method?
  4. What could this ben­e­fit from in each of its com­po­nents and as a whole? If the cost de­creases 5% for every dou­bling of cu­mu­la­tive pro­duc­tion, what hap­pens and how much de­mand do the price drops in­duce? Are any of the in­puts cu­mu­la­tive, like dataset size (eg. num­ber of genomes se­quenced to date)?
  5. Does it ben­e­fit from var­i­ous forms of Moore’s laws for CPUs, RAM, HDD, or GPU FLOPs? Can fixed-cost hard­ware or hu­mans be re­placed by soft­ware, In­ter­net, or sta­tis­tics? Is any part par­al­leliz­able?
  6. What cal­iber of in­tel­lect has been ap­plied to op­ti­miza­tion? What amount of ‘con­stant fac­tor’ slack is left in the sys­tem to be mi­cro-op­ti­mized away?

  1. , for ex­am­ple, has tremen­dous game tree com­plex­i­ty. (Even de­cid­ing the win­ner of a Go board is sur­pris­ingly diffi­cult—PSPACE, so pos­si­bly worse than NP.) Nev­er­the­less, AIs greatly sur­pass hu­man abil­i­ties at them and as of 2018, even ‘cen­taur’ teams no longer add any­thing to the AI per­for­mance. Since this is the case al­ready, Myhrvold’s ar­gu­ment that math’s com­plex­ity makes it im­mune to AI is un­der­mined by his own ex­am­ples.↩︎

  2. “Shifts In Al­go­rithm De­sign”, Lipton/Regan:

    Now to­day, in the 21st cen­tu­ry, we have a bet­ter way to at­tack prob­lems. We change the prob­lem, often to one that is more tractable and use­ful. In many sit­u­a­tions solv­ing the ex­act prob­lem is not re­ally what a prac­ti­tioner needs. If com­put­ing X ex­actly re­quires too much time, then it is use­less to com­pute it. A per­fect ex­am­ple is the weath­er: com­put­ing to­mor­row’s weather in a week’s time is clearly not very use­ful. The bril­liance of the cur­rent ap­proach is that we can change the prob­lem. There are at least two ma­jor ways to do this:

    • Change the an­swer re­quired. Al­low ap­prox­i­ma­tion, or al­low a par­tial an­swer. Do not in­sist on an ex­act an­swer.
    • Change the al­go­rith­mic method. Al­low al­go­rithms that can be wrong, or al­low al­go­rithms that use ran­dom­ness. Do not in­sist that the al­go­rithm is a per­fect de­ter­min­is­tic one.

    This is ex­actly what Chayes and her co-au­thors have done.

  3. Rin­ta­nen 2012, , dis­cussing how to turn AI plan­ning prob­lems into SAT prob­lems which can be solved effi­cient­ly, notes that

    A pe­cu­liar­ity of SAT prob­lems ob­tained by trans­la­tion from the stan­dard plan­ning bench­mark prob­lems from the plan­ning com­pe­ti­tions, in con­trast to SAT prob­lems rep­re­sent­ing many other ap­pli­ca­tions, is their ex­tremely large size and the fact that these prob­lems can still often be solved quick­ly. The largest SAT prob­lems Lin­geling solves (within the time bounds ex­plained ear­lier) are in­stance 41 of AIRPORT (417476 propo­si­tional vari­ables, 92.9 mil­lion claus­es) and in­stance 26 of TRUCKS (926857 propo­si­tional vari­ables, 11.3 mil­lion claus­es).

    Our plan­ner solves in­stance 49 of AIRPORT (13840 ac­tions and 14770 state vari­ables) with a com­pleted un­sat­is­fi­a­bil­ity test for hori­zon 65, with 1.12 mil­lion propo­si­tional vari­ables and 108.23 mil­lion claus­es, and a plan for hori­zon 85, with 1.46 mil­lion propo­si­tional vari­ables and 141.54 mil­lion claus­es. The plan­ner also solves in­stance 33 of SATELLITE (989250 ac­tions and 5185 state vari­ables), with a plan found for hori­zon 20, with 19.89 mil­lion propo­si­tional vari­ables and 69.99 mil­lion claus­es, back­track­-free in 14.50 sec­onds ex­clud­ing trans­la­tion into SAT and in­clud­ing search effort for shorter hori­zons. These are ex­treme cas­es. More typ­i­cal SAT in­stances have less than 2 mil­lion propo­si­tional vari­ables and a cou­ple of mil­lion clauses

  4. , 1988; Dyson is summarizing/paraphrasing a weather pre­dic­tion lec­ture by von Neu­mann ~1950. It’s un­clear if von Neu­mann said this ex­act thing, al­though it is usu­ally at­trib­uted to him.↩︎

  5. At­trib­uted to him in 2009 by his col­league .↩︎

  6. Some ex­am­ples of this folk wis­dom: Can­tor & Zassen­haus 1981:

    The as­ymp­tot­i­cally best al­go­rithms fre­quently turn out to be worst on all prob­lems for which they are used.

    “Notes on Pro­gram­ming on C”, Rob Pike:

    Rule 3. Fancy al­go­rithms are slow when n is small, and n is usu­ally small. Fancy al­go­rithms have big con­stants. Un­til you know that n is fre­quently go­ing to be big, don’t get fan­cy. (Even if n does get big, use Rule 2 first.)


    In gen­eral I’m look­ing for more fo­cus on al­go­rithms that work fast with re­spect to prob­lems whose size, n, is fea­si­ble. Most of to­day’s lit­er­a­ture is de­voted to al­go­rithms that are as­ymp­tot­i­cally great, but they are help­ful only when n ex­ceeds the size of the uni­verse…An­other is­sue, when we come down to earth, is the effi­ciency of al­go­rithms on real com­put­ers. As part of the Stan­ford Graph­Base project I im­ple­mented four al­go­rithms to com­pute min­i­mum span­ning trees of graphs, one of which was the very pretty method that you de­vel­oped with Cheri­ton and Karp. Al­though I was ex­pect­ing your method to be the win­ner, be­cause it ex­am­ines much of the data only half as often as the oth­ers, it ac­tu­ally came out two to three times worse than Kruskal’s ven­er­a­ble method. Part of the rea­son was poor cache in­ter­ac­tion, but the main cause was a large con­stant fac­tor hid­den by O no­ta­tion.

    More specifi­cal­ly: “Knuth did a com­par­i­son be­tween Fi­bonacci heap and bi­nary heaps for min­i­mum span­ning trees back in 1993 for his book Stan­ford Graph­Base. He found Fi­bonacci to be 30 to 60% slower than bi­nary heaps at the graph sizes he was test­ing, 128 ver­tices at differ­ent den­si­ties.”

    On the :

    The Cop­per­smith-Wino­grad al­go­rithm is fre­quently used as a build­ing block in other al­go­rithms to prove the­o­ret­i­cal time bounds. How­ev­er, un­like the Strassen al­go­rithm, it is not used in prac­tice be­cause it only pro­vides an ad­van­tage for ma­tri­ces so large that they can­not be processed by mod­ern hard­ware.[6]

    Some al­go­rithms are par­tic­u­larly in­fa­mous for their ex­cel­lent as­ymp­tot­ics but abysmal con­stant fac­tors, such as the com­putable ver­sions of AIXI. Lip­ton dubs such al­go­rithms “galac­tic al­go­rithms”.↩︎

  7. The only au­thor on the Sin­gu­lar­ity I know of who claims an ac­tual in­defi­nite in­crease in in­tel­li­gence to in­fin­i­ty, tak­ing ‘sin­gu­lar­ity’ quite lit­er­ally and not as Vinge’s metaphor/comparison, would be ideas, but as far as I know, even as­sum­ing the cor­rect­ness of his cal­cu­la­tions, his in­fi­nite in­tel­li­gence is phys­i­cally pos­si­ble only un­der a num­ber of cos­mo­log­i­cal con­di­tions, some of which do not seem to be true (such as a closed uni­verse rather than a flat ex­pand­ing one).↩︎

  8. , 2013:

    Vasik Ra­jlich, the pro­gram­mer be­hind , gives a more pes­simistic spin to what we have learned from the chess-play­ing pro­grams. In Ra­jlich’s view, the strik­ing fact about chess is how hard it is for hu­mans to play it well. The out­put from the pro­grams shows that we are mak­ing mis­takes on a very large num­ber of moves. Ken’s mea­sures show that even top grand­mas­ters, ex­cept at the very peaks of their per­for­mances, are for­tu­nate to match Ry­bka’s rec­om­men­da­tions 55% of the time. When I com­pare a grand­mas­ter game to an on­go­ing Ry­bka eval­u­a­tion, what I see is an ini­tial po­si­tion of value be­ing squan­dered away by blun­der­s—if only small ones—a­gain and again and again. It’s a bit de­press­ing. Ra­jlich stresses that hu­mans blun­der con­stant­ly, that it is hard to be ob­jec­tive, hard to keep con­cen­trat­ing, and hard to cal­cu­late a large num­ber of vari­a­tions with ex­act­ness. He is not talk­ing here about the club patzer but rather the top grand­mas­ters: “I am sur­prised how far they are from per­fec­tion.” In ear­lier times these grand­mas­ters had a kind of aura about them among the chess-view­ing pub­lic, but in the days of the pro­grams the top grand­mas­ters now com­mand less re­spect. When a world-class player plays a club ex­pert, the world-class player looks bril­liant and in­vin­ci­ble at the board. In­deed, the world-class player does choose a lot of very good moves. At some point his su­pe­rior po­si­tion starts “play­ing it­self,” to use an ex­pres­sion from the chess world, and just about every­thing falls into place. When the same world-class player takes on Shred­der, to se­lect an ap­pro­pri­ately named pro­gram, he seems more like a hap­less fool who must ex­ert great care to keep the sit­u­a­tion un­der con­trol at all. And yet it is the very same play­er. That gap—­be­tween our per­cep­tion of su­pe­rior hu­man in­tel­lect and its ac­tual re­al­i­ty—is the sober­ing les­son of the pro­grams.

    See also , An­der­son et al 2016, and for com­par­ison, Al­phaGo Zero: the first Al­phaGo was trained to pre­dict hu­man player moves, achiev­ing ~55% ac­cu­ra­cy; Zero plays Go far bet­ter but pre­dicts no­tice­ably worse (~51%) and its pre­dic­tions get worse even as it gets bet­ter at play­ing or pre­dict­ing the ul­ti­mate win­ner, im­ply­ing that hu­man ex­perts also are able to choose the best move only 50% or less of the time.↩︎

  9. Shock­ley notes that with 8 vari­ables and an ad­van­tage of 50%, the out­put un­der a log-nor­mal model would be in­creased by as much as 25×:

    simulateLogNormal <- function(advantage, n.variables, iters=100000) {
      regular <- 1
      advantaged <- replicate(iters, Reduce(`*`, rnorm(n.variables, mean=(1+advantage), sd=1), 1))
      ma <- mean(advantaged)
    simulateLogNormal(0.5, 8)
    # [1] 25.58716574

    With more vari­ables, the out­put differ­ence would be larger still, and is con­nected to the . This poses a chal­lenge to those who ex­pect small differ­ences in abil­ity to lead to small out­put differ­ences, as the log-nor­mal dis­tri­b­u­tion is com­mon in the real world, and also im­plies that hy­brid hu­man-AI sys­tems are un­sta­ble as the hu­man will quickly be­come a bot­tle­neck.↩︎

  10. Spo­ken to ; recorded pg296 of The Naval Mem­oirs 1910–1915, Keyes 1934.↩︎

  11. As quoted by in , Mikkel­son 1997.↩︎

  12. For some rea­son, a lot of peo­ple are ab­solutely con­vinced that the Halt­ing The­o­rem or Godelian in­com­plete­ness do things like prove that cre­at­ing any ar­ti­fi­cial in­tel­li­gence is im­pos­si­ble in prin­ci­ple. (They do no such thing, any more than they prove the im­pos­si­bil­ity of, say, type­check­ers, or su­per­sized ma­chines, or their own ex­is­tence.)↩︎