Surprisingly Turing-Complete

A catalogue of software constructs, languages, or APIs which are unexpectedly Turing-complete; implications for security and reliability
computer-science, philosophy, insight-porn
2012-12-09–2019-06-15 finished certainty: highly likely importance: 6

‘Com­put­ers’, in the sense of being Tur­ing-com­plete, are extremely com­mon. Almost any sys­tem of suffi­cient com­plex­i­ty—un­less care­fully engi­neered oth­er­wise—­may be found to ‘acci­den­tally’ sup­port Tur­ing-com­plete some­where inside it, even sys­tems which would appear to have not the slight­est thing to do with com­pu­ta­tion. Soft­ware sys­tems are espe­cially sus­cep­ti­ble to this, which often leads to seri­ous secu­rity prob­lems as the Tur­ing-com­plete com­po­nents can be used to run attacks on the rest of the sys­tem.

I pro­vide a run­ning cat­a­logue of sys­tems which have been, sur­pris­ing­ly, demon­strated to be Tur­ing-com­plete.

Tur­ing-com­plete­ness (TC) is (avoid­ing pedan­ti­cally rig­or­ous for­mal defi­n­i­tions) the prop­erty of a sys­tem being able to, under some sim­ple rep­re­sen­ta­tion of input & out­put, com­pute any pro­gram of inter­est, includ­ing another com­puter in some form.

TC, besides being foun­da­tional to com­puter sci­ence and under­stand­ing many key issues like “why a per­fect antivirus pro­gram is impos­si­ble”, is also weirdly com­mon: one might think that such uni­ver­sal­ity as a sys­tem being smart enough to be able to run any pro­gram might be diffi­cult or hard to achieve, but it turns out to be the oppo­site—it is diffi­cult to write a use­ful sys­tem which does not imme­di­ately tip over into TC. “Sur­pris­ing” exam­ples of this behav­ior remind us that TC lurks every­where, and secu­rity is extremely diffi­cult.

I like demon­stra­tions of TC lurk­ing in sur­pris­ing places because they are often a dis­play of con­sid­er­able inge­nu­ity, and feel like they are mak­ing a pro­found philo­soph­i­cal point about the nature of com­pu­ta­tion: com­pu­ta­tion is not some­thing eso­teric which can exist only in pro­gram­ming lan­guages or com­put­ers care­fully set up, but is some­thing so uni­ver­sal to any rea­son­ably com­plex sys­tem that TC will almost inevitably pop up unless actively pre­vent­ed.

Accidentally Turing-complete

“Any suffi­ciently com­pli­cated C or For­tran pro­gram con­tains an ad hoc, infor­mal­ly-spec­i­fied, bug-rid­den, slow imple­men­ta­tion of half of Com­mon Lisp.”

Green­spun’s Tenth Law

XKCD #1636, “XKCD Stack”

They are prob­a­bly best con­sid­ered as a sub­set of “dis­cov­ered” or “found” eso­teric pro­gram­ming lan­guages (esolangs). So FRACTRAN, as extra­or­di­nar­ily min­i­mal­ist as it is, does not count; nor would a delib­er­ately obfus­cated lan­guage like Mal­bolge (where it took years to write a triv­ial pro­gram) count because it was designed to be an esolang; but nei­ther would Con­way’s Game of Life count because ques­tions about whether it was TC appeared almost imme­di­ately upon pub­li­ca­tion and being able to pro­gram Tetris in it is not sur­pris­ing, and given the com­plex­ity of pack­et-switch­ing Eth­er­net net­works & routers it’s not nec­es­sar­ily too sur­pris­ing if one can build a cel­lu­lar automa­ton into them or encode log­i­cal cir­cuits, or if air­plane ticket planning/validation is not just NP-hard or EXPSPACE-hard but unde­cid­able (be­cause of the com­plex rules air­lines require). Many con­fig­u­ra­tion or spe­cial-pur­pose lan­guages or tools or com­pli­cated games turn out to vio­late the Rule of least power & be “acci­den­tally Tur­ing-com­plete”, like Send­mail1, Medi­aWiki tem­plates, sed or repeated regexp/find-replace com­mands in an edi­tor (any form of string sub­sti­tu­tion or tem­plat­ing or com­pile-time com­pu­ta­tion is highly likely to be TC on its own or when iter­ated since they often turn out to sup­port a lambda cal­cu­lus or a ter­m-rewrit­ing lan­guage or tag sys­tem eg esolangs “///” or Thue), XSLT, Infi­nite Minesweeper, Dwarf Fortress2, Star­craft, Minecraft, Ant, Trans­port Tycoon & Cities: Sky­line, C++ tem­plates & Java gener­ics, DNA com­put­ing etc are TC but these are not sur­pris­ing either: many games sup­port script­ing (ie TC-ness) to make their devel­op­ment eas­ier and enable fan mod­i­fi­ca­tions, so games’ TC may be as sim­ple as includ­ing syn­tax for call­ing out to a bet­ter-known lan­guage like Perl, or it may just be an obscure part of a stan­dard for­mat (most peo­ple these days are prob­a­bly unaware that True­Type & many fonts are Post­Script pro­grams based on stack machi­nes, sim­i­lar to DWARF debug­ging and ELF meta­data, or that some music for­mats go beyond MIDI in pro­vid­ing script­ing capa­bil­i­ties and must be inter­preted to be dis­played; once one knows this, then fonts being TC are no more sur­pris­ing than TeX doc­u­ments being TC, lead­ing of course, to many severe & fas­ci­nat­ing font or media secu­rity vul­ner­a­bil­i­ties such as the BLEND vul­ner­a­bil­ity or SNES & NES code exploit­ing Linux sys­tems Other for­mats, like PDF, are sim­ply appalling.3). Sim­i­lar­ly, such feats as cre­at­ing a small Tur­ing machine using Legos or domi­nos4 would not count, since we already know that mechan­i­cal com­put­ers work. On the other hand, “weird machines” are a fer­tile ground of “that’s TC?” reac­tions.

Surprisingly Turing-complete

Many cases of dis­cov­er­ing TC seem to con­sist of sim­ply notic­ing that a prim­i­tive in a sys­tem is a lit­tle too powerful/flexible. For exam­ple, if Boolean logic can be imple­ment­ed, that’s a sign that more may be pos­si­ble and turn Boolean cir­cuits into ful­l-blown cir­cuit logic for a TM. Sub­sti­tu­tions, definitions/abbreviations, reg­u­lar expres­sions (espe­cially with any exten­sions or cus­tom fea­tures), or any other kind of ‘search and replace’ func­tion­al­ity is another red flag, as they sug­gest that a cel­lu­lar automa­ton or tag sys­tem is lurk­ing. This applies to any­thing which can change state based on ‘neigh­bors’, like a spread­sheet cell or a pix­el. Any sort of script­ing inter­face or API, even if locked down, may not be locked down quite enough. An actual script­ing lan­guage or VM is so bla­tant as to be bor­ing when (not if) some­one finds a vul­ner­a­bil­ity or escape from the sand­box. Oper­a­tions which take vari­able lengths of times or whose com­ple­tion can’t eas­ily be pre­dicted from the start are another source of prim­i­tives, as they may ‘depend’ on the data they are oper­at­ing over in some way, imple­ment­ing differ­ent oper­a­tions on differ­ent data, which may mean that they can be made equiv­a­lent to Boolean con­di­tion­als based on a care­ful encod­ing of data.

What is “sur­pris­ing” may differ from per­son to per­son. Here is a list of acci­den­tal­ly-Tur­ing-com­plete sys­tems that I found sur­pris­ing:

Pos­si­bly acci­den­tally or sur­pris­ingly Tur­ing-com­plete sys­tems:

  • CSS with­out the assump­tion of a dri­ving mouse click (per­haps some sort of Wang tile using reflec­tions and con­di­tion­al­s?)

  • Uni­code (!): Nico­las Seriot sug­gests that Uni­code’s bidi­rec­tional algo­rithms (in­tended for dis­play­ing scripts like Ara­bic or Hebrew which go right-to-left rather than left­-to-right like Eng­lish) may be com­plex enough to sup­port a tag sys­tem via case fold­ing rules (eg Turk­ish).

  • Human visual illu­sions: Changizi 2008 presents ambigu­ous images in a cir­cuit-like for­mat, whose depth per­cep­tion ‘flips’ based on the ‘input’ or top of the cir­cuit, which are anal­o­gous to OR/AND/NOT/XOR com­pu­ta­tions; the exis­tence of these ‘visual cir­cuits’ hints at the pos­si­bil­ity of ‘TC-com­plete’ images (although many pieces, like a work­ing mem­o­ry, are miss­ing)

Security implications

It turns out that given even a lit­tle con­trol over input into some­thing which trans­forms input to out­put, one can typ­i­cally lever­age that con­trol into ful­l-blown TC. This mat­ters because, if one is clev­er, it pro­vides an escape hatch from a sys­tem which is small, pre­dictable, con­trol­lable, and secure, to one which could do any­thing. It’s hard enough to make a pro­gram do what it’s sup­posed to do with­out giv­ing any­one in the world the abil­ity to insert another pro­gram into your pro­gram. Even if there is no way to out­right ‘escape’ the sand­box, such hid­den pro­grams can be dan­ger­ous, by extract­ing infor­ma­tion about the sur­round­ing pro­gram (eg JS embed­ded in a web page which can extract your pass­words by using Row ham­mer to attack your hard­ware direct­ly, even if it can’t actu­ally escape your web browser), or can take the host into strange & uncharted (and untest­ed) ter­ri­to­ries.

That we find these demon­stra­tions sur­pris­ing is itself a demon­stra­tion of our lack of imag­i­na­tion and under­stand­ing of com­put­ers, com­puter secu­ri­ty, and AI. We pre­tend that we are run­ning pro­grams on these sim­ple abstract machines which do what we intu­itively expect, but they run on com­put­ers which are bizarre, and our pro­grams them­selves turn out to be com­put­ers which are even more bizarre. Secure sys­tems have to be built by con­struc­tion; once the genie has been let out of the lamp, it’s diffi­cult to patch the lamp.

An active area of research is into lan­guages & sys­tems care­fully designed and proven to not be TC (eg. total func­tional pro­gram­ming). Why this effort to make a lan­guage in which many pro­grams can’t be writ­ten? Because TC is inti­mately tied to Godel’s incom­plete­ness the­o­rems & Rice’s the­o­rem, allow­ing TC means that one is for­feit­ing all sorts of prov­abil­ity prop­er­ties: in a non-TC lan­guage, one may be able to eas­ily prove all sorts of use­ful things to know; for exam­ple, that pro­grams ter­mi­nate, that they are type­-safe or not, that they can be eas­ily con­verted into a log­i­cal the­o­rem, that they con­sume a bounded amount of resources, that one imple­men­ta­tion of a pro­to­col is cor­rect or equiv­a­lent to another imple­men­ta­tion, that there are a lack of side-effects and a pro­gram can be trans­formed into a log­i­cal­ly-e­quiv­a­lent but faster ver­sion (par­tic­u­larly impor­tant for declar­a­tive lan­guages like SQL where the query opti­mizer being able to trans­form queries is key to accept­able per­for­mance, but of course one can do a sur­pris­ing amount in SQL like 3D ray­trac­ing gra­di­ent descent for fit­ting machine learn­ing mod­els and some SQL exten­sions make it TC any­way by allow­ing either a cyclic tag sys­tem to be encod­ed, the model DSL, or to call out to PL/SQL) etc.

Lan­guages or sys­tems which unin­ten­tion­ally cross over the line into being TC can be amus­ing or use­ful (although usu­ally not), but they also have some seri­ous impli­ca­tions: such sys­tems, because they were never expected to be pro­gram­ma­ble, can be harm­ful, or extremely inse­cure & a crack­er’s delight, as exem­pli­fied by the “lan­guage-the­o­retic secu­rity” par­a­digm, based on exploit­ing “weird machines”; some of the lit­er­a­ture:

Most recent­ly, Spec­tre & gen­er­al­iza­tions (Mcil­roy et al 2019) can be inter­preted as pro­vid­ing a whole ‘shadow com­puter’ in the CPU via spec­u­la­tive exe­cu­tion which can be pro­grammed to do things like run mal­ware with­out vis­i­bly exe­cut­ing any of the mal­ware instruc­tions while hav­ing side-effects in the real com­put­er. Spec­tre is inter­est­ing in being a class of vul­ner­a­bil­i­ties which have existed for decades in CPU archi­tec­tures that were closely scru­ti­nized for secu­rity prob­lems, but just sort of fell into a col­lec­tive human blind spot. Nobody thought of con­trol­lable spec­u­la­tive exe­cu­tion as being a ‘com­puter’ which could be ‘pro­grammed’. Once some­one noticed, because it was a pow­er­ful com­puter and of course TC, it could be used in many ways to attack stuff.

“Too pow­er­ful” lan­guages can also man­i­fest as nasty DoS attacks; the fuzz tester afl found that it could cre­ate an infi­nite loop in OpenBSD’s roff doc­u­ment for­mat­ting tool (first ver­sion, 43 years pri­or) by abus­ing some of the string sub­sti­tu­tion rules.

On Seeing Through and Unseeing

“Uncle Mil­ton Indus­tries has been sell­ing ant farms to chil­dren since 1956. Some years ago, I remem­ber open­ing one up with a friend. There were no actual ants included in the box. Instead, there was a card that you filled in with your address, and the com­pany would mail you some ants. My friend expressed sur­prise that you could get ants sent to you in the mail. I replied: ‘What’s really inter­est­ing is that these peo­ple will send a tube of live ants to any­one you tell them to.’”

Bruce Schneier, “The Secu­rity Mind­set” (2008)

“Every drop of blood has great tal­ent; the orig­i­nal cel­lule seems iden­ti­cal in all ani­mals, and only var­ied in its growth by the vary­ing cir­cum­stance which opens now this kind of cell and now that, caus­ing in the remote effect now horns, now wings, now scales, now hair; and the same numer­i­cal atom, it would seem, was equally ready to be a par­ti­cle of the eye or brain of man, or of the claw of a tiger…The man truly con­ver­sant with life knows, against all appear­ances, that there is a rem­edy for every wrong, and that every wall is a gate.”

Ralph Waldo Emer­son, “Nat­ural His­tory Of Intel­lect”, 18936

“The ques­tion is”, said Alice, “whether you can make words mean so many differ­ent things.”
“The ques­tion is”, said Humpty Dump­ty, “which is to be mas­ter—that’s all.”

Lewis Car­roll, Through the Look­ing-Glass, and What Alice Found There (1872)7

“I don’t even see the code. All I see is blonde, brunet­te, red­head.”

Cypher, The Matrix

To draw some par­al­lels here and expand Dul­lien 2017, I think unex­pected Tur­ing-com­plete sys­tems and weird machines have some­thing in com­mon with heist movies or cons or stage mag­ic: they all share a spe­cific par­a­digm we might call the secu­rity mind­set or hacker mind­set.

What they/OP/security/speedrun­ning/hacking/social-engi­neer­ing all have in com­mon is that they show that the much-bal­ly­hooed ‘hacker mind­set’ is, fun­da­men­tal­ly, a sort of reduc­tion­ism run amok, where one ‘sees through’ abstrac­tions to a manip­u­la­ble real­i­ty.8 Like Neo in the Matrix—a deeply cliche anal­ogy for hack­ing, but cliche because it res­onates—one achieves enlight­en­ment by see­ing through the sur­face illu­sions of objects and can now see the end­less lines of green code which make up the Matrix (and vice-ver­sa).

In each case, the fun­da­men­tal prin­ci­ple is that the hacker asks: “here I have a sys­tem W, which pre­tends to be made out of a few Xs; how­ev­er, it is really made out of many Y, which form an entirely differ­ent sys­tem, Z; I will now pro­ceed to ignore the X and under­stand how Z works, so I may use the Y to thereby change W how­ever I like”.

Abstrac­tions are vital, but abstrac­tions also always leak. (“You’re very clev­er, young man, but it’s reduc­tion­ism all the way down!”) This is in some sense the oppo­site of a math­e­mati­cian: a math­e­mati­cian tries to ‘see through’ a com­plex sys­tem’s acci­den­tal com­plex­ity up to a sim­pler more-ab­stract more-true ver­sion which can be under­stood & manip­u­lat­ed—but for the hack­er, all com­plex­ity is essen­tial, and they are instead try­ing to unsee the sim­ple abstract sys­tem down to the more-com­plex less-ab­stract (but also more true) ver­sion. (A math­e­mati­cian might try to trans­form a pro­gram up into suc­ces­sively more abstract rep­re­sen­ta­tions to even­tu­ally show it is triv­ially cor­rect; a hacker would pre­fer to com­pile a pro­gram down into its most con­crete rep­re­sen­ta­tion to brute force all exe­cu­tion paths & find an exploit triv­ially prov­ing it incor­rec­t.) Ordi­nary users ask only that all their every­day exam­ples of Ys trans­forms into Z cor­rect­ly; they for­get to ask whether all and only cor­rect exam­ples of Ys trans­form into cor­rect Zs, and whether only cor­rect Zs can be con­structed to become Ys. Even a sin­gle ‘anom­aly’, appar­ently triv­ial in itself, can indi­cate the every­day men­tal model is not just a lit­tle bit wrong, but fun­da­men­tally wrong, in the way that New­ton’s the­ory of grav­ity is not merely a lit­tle bit wrong and just needs a quick patch with a fudge fac­tor to account for Mer­cury or that NASA man­age­men­t’s men­tal model of O-rings was not merely in need of a lit­tle increase in the thick­ness of the rub­ber gas­kets9.

It’s all ‘atoms and void’10:

  • In hack­ing, a com­puter pre­tends to be made out of things like ‘buffers’ and ‘lists’ and ‘objects’ with rich mean­ing­ful seman­tics, but real­ly, it’s just made out of bits which mean noth­ing and only acci­den­tally can be inter­preted as things like ‘web browsers’ or ‘pass­words’, and if you move some bits around and rewrite these other bits in a par­tic­u­lar order and read one string of bits in a differ­ent way, now you have bypassed the pass­word.

  • In speed run­ning (par­tic­u­larly TASes), a video game pre­tends to be made out of things like ‘walls’ and ‘speed lim­its’ and ‘lev­els which must be com­pleted in a par­tic­u­lar order’, but it’s really again just made out of bits and mem­ory loca­tions, and mess­ing with them in par­tic­u­lar ways, such as delib­er­ately over­load­ing the RAM to cause mem­ory allo­ca­tion errors, can give you infi­nite ‘veloc­ity’ or shift you into alter­nate coor­di­nate sys­tems in the true physics, allow­ing enor­mous move­ments in the sup­posed map, giv­ing short­cuts to the ‘end’11 of the game.

  • In rob­bing a hotel room, peo­ple see ‘doors’ and ‘locks’ and ‘walls’, but real­ly, they are just made out of atoms arranged in a par­tic­u­lar order, and you can move some atoms around more eas­ily than oth­ers, and instead of going through a ‘door’ you can just cut a hole in the wall12 (or ceil­ing) and obtain access to a space. At Los Alam­os, Richard Feyn­man, among other tac­tics, obtained clas­si­fied papers by reach­ing in under­neath draw­ers and ignored the locks entire­ly.

    • One analy­sis of the movie Die Hard, “Nakatomi space”, high­lights how it & the Israel mil­i­tary’s mouse-hol­ing in the Bat­tle of Nablus treat build­ings as kinds of machi­nes, which can be manip­u­lated in weird ways to move around to attack their ene­mies.

    • That exam­ple reminds me of the Carr & Adey anatomy of locked room mur­der mys­ter­ies, lay­ing out a tax­on­omy of all the pos­si­ble solu­tions which—­like a magi­cian’s trick­—vi­o­late one’s assump­tions about the locked room: whether it was always locked, locked at the right time, the mur­der done while in the room, mur­der rather than sui­cide, the room with locked-doors hav­ing a ceil­ing etc. (These tricks inspired Umineko’s mys­ter­ies (review), although in it a lot of them turn out to just involve conspirators/lying.)

    • In lock­pick­ing, copy­ing a key or reverse-engi­neer­ing its cuts are some of the most diffi­cult ways to pick a lock. One can instead sim­ply use a bump key to brute-force the posi­tions of the pins in a lock, or kick the door in, or among other door lock bypasses, wig­gle the bolt, or reach through a crack to open from the inside, or drill the lock. (How do you know some­one has­n’t already? You assume it’s the same lock as yes­ter­day?)

      Locks & safes have many other inter­est­ing vul­ner­a­bil­i­ties; I par­tic­u­larly like Matt Blaze’s mas­ter-key vul­ner­a­bil­ity (Blaze 2003/Blaze 2004a/Blaze 2004b), which uses the fact that a mas­ter-key lock is actu­ally open­ing for any com­bi­na­tion of mas­ter+or­di­nary key cuts (ie ‘mas­ter OR ordi­nary’ rather than ‘mas­ter XOR ordi­nary’), and so it is like a pass­word which one can guess one let­ter at a time.

  • In stage magic (espe­cially close-up/card/coin/pickpocketing), one believes one is con­tin­u­ously see­ing sin­gle whole objects which must move from one place to another con­tin­u­ous­ly; in real­i­ty, one is only see­ing, occa­sion­al­ly, sur­faces of many (pos­si­bly dupli­cate) objects, which may be mov­ing only when you are not look­ing, in the oppo­site direc­tion, or not mov­ing at all. By hack­ing object per­ma­nence and lim­ited atten­tional resources, the stage magi­cian shows the ‘impos­si­ble’ (Mack­nik et al 2008’s Table 1 lists folk assump­tions which can be hacked). Stage magic works by exploit­ing our implicit beliefs that no adver­sary would take the trou­ble to so pre­cisely exploit our heuris­tics and short­cuts.1314

  • In weird machi­nes, you have a ‘pro­to­col’ like SSL or X86 machine code which appear to do sim­ple things like ‘check a cryp­to­graphic sig­na­ture’ or ‘add one num­ber in a reg­is­ter to another reg­is­ter’, but in real­i­ty, it’s a layer over far more com­plex real­i­ties like proces­sor states & opti­miza­tions like spec­u­la­tive exe­cu­tion read­ing other parts of mem­ory and then quickly eras­ing it, and these can be pasted together to exe­cute oper­a­tions and reveal secrets with­out ever run­ning ‘code’ (see again Mcil­roy et al 2019).

    Sim­i­lar­ly, in find­ing hid­den exam­ples of Tur­ing com­plete­ness, one says, ‘this sys­tem appears to be a bunch of domi­noes or what­ev­er, but actu­al­ly, each one is a com­pu­ta­tional ele­ment which has unusual inputs/outputs; I will now pro­ceed to wire a large num­ber of them together to form a Tur­ing machine so I can play Tetris in Con­way’s Game of Life or use heart mus­cle cells to imple­ment Boolean logic or run arbi­trary com­pu­ta­tions in a game of Mag­ic: The Gath­er­ing’.

    Or in side chan­nels, you go below bits and say, ‘these bits are only approx­i­ma­tions to the actual flow of elec­tric­ity and heat in a sys­tem; I will now pro­ceed to mea­sure the phys­i­cal sys­tem’ etc.

  • In social engineering/pen test­ing, peo­ple see social norms and imag­i­nary things like ‘per­mis­sion’ and ‘author­ity’ and ‘man­agers’ which ‘for­bid access to facil­i­ties’, but in real­i­ty, all there is, is a piece of lam­i­nated plas­tic or a clip­board or cer­tain magic words spo­ken; the peo­ple are merely non-com­put­er­ized ways of imple­ment­ing rules like ‘if lam­i­nated plas­tic, allow in’, and if you put on a blue piece of plas­tic to your shirt and you incant cer­tain words at cer­tain times, you can walk right past the guards.15

  • Many finan­cial or eco­nomic strate­gies have a cer­tain fla­vor of this; Alice Maz’s Minecraft eco­nom­ics exploita­tions strongly reminds me of ‘see­ing through’, as do many clever finan­cial trades based on care­ful read­ing of con­trac­tual minu­tiae or tak­ing seri­ously what are usu­ally abstracted details like ‘tak­ing deliv­ery’ of futures etc

  • and while we’re at it, why are puns so irre­sistible to hack­ers? (Con­sider how omnipresent they are in Gödel, Escher, Bach or the Jar­gon File or text adven­tures or…) Com­put­ers are noth­ing but puns on bits, and lan­guages are noth­ing but puns on let­ters. Puns force one to drop from the abstract seman­tic level to the raw syn­tac­tic level of sub­-words or char­ac­ters, and back up again to achieve some seman­tic twist—they are lit­er­ally hack­ing lan­guage.

And so on. These sorts of things can seem mag­i­cal (‘how‽’), shock­ing (‘but—but—that’s cheat­ing!’), or hilar­i­ous (in the ‘vio­la­tion of expec­ta­tions fol­lowed by under­stand­ing’ the­ory of humor) because the abstract sys­tem W & our ver­bal­iza­tions are so famil­iar and use­ful that we quickly get trapped in our dreams of abstrac­tions, and for­get that it is merely a map and not the ter­ri­to­ry, while inevitably the map has made gross sim­pli­fi­ca­tions and it fails to doc­u­ment var­i­ous paths from one point to another point which we don’t want to exist.

Per­verse­ly, the more edu­cated you are, and the more of the map you know, the worse this effect can be, because you have more to unsee. One must always main­tain a cer­tain con­tempt for words & spooks.

The fool can walk right in because he was too igno­rant to know that’s impos­si­ble. This is why athe­o­ret­i­cal opti­miza­tion processes like ani­mals (eg cats engaged in fuzz test­ing) or SMT solvers or evo­lu­tion­ary AI are so dumb to begin with, but in the long run can be so good at sur­pris­ing us and find­ing ‘unrea­son­able’ inputs or reward hacks (anal­o­gous to the bias-vari­ance trade­off): being unable to under­stand the map, they can’t ben­e­fit from it like we do, but they also can’t over­value it, and, forced to explore the ter­ri­tory directly to get what they want, dis­cover new things.

To escape our seman­tic illu­sions can require a deter­mined effort to unsee them, and use of tech­niques to defa­mil­iar­ize the things. For exam­ple, you can’t find typos in your own writ­ing with­out a great deal of effort because you know what it’s sup­posed to say; so copy­edit­ing advice runs like ‘read it out loud’ or ‘print it out and read it’ or ‘wait a week’ or even ‘read it upside down’ (easier than it sound­s). That’s the sort of thing it takes to force you to read what you actu­ally wrote, and not what you thought you wrote. Sim­i­lar tricks are used for learn­ing draw­ing: a face is too famil­iar, so instead you can flip it in a mir­ror and try to copy it.

See Also

Appendix

Macknik Et Al 2008: Table 1: Psychological Assumptions

Table 1: Types of con­jur­ing effects16
Magic effects Exam­ples Method­olog­i­cal strate­gies
Appear­ance: an object appears ‘as if by magic’ Pulling a rab­bit out of a hat; the Mis­er’s Dream (in which hun­dreds of coins seem to appear where pre­vi­ously there were none)75, 94 (BOX 2; Sup­ple­men­tary infor­ma­tion S2 (movie)); Mac King’s giant rock in a shoe trick75, 87 (Sup­ple­men­tary infor­ma­tion S3 (movie))
  • The object was already there but was con­cealed (for exam­ple, the magi­cian might con­ceal a coin in his or her hand prior to its pro­duc­tion)
  • The object was secretly put into posi­tion (for exam­ple, in the Cups and Balls rou­tine, var­i­ous objects are secretly loaded under the cups dur­ing the rou­tine)
  • The object is not there but seems to be (for exam­ple, a ‘medium’ can sim­u­late the pres­ence of a spirit at a seance by secretly touch­ing a spec­ta­tor)
Van­ish: an object dis­ap­pears ‘as if by magic’ Van­ish­ing of a coin; Penn and Teller’s under­wa­ter van­ish­ing of a naval sub­marine; David Cop­per­field’s van­ish­ing of the Statue of Lib­er­ty.
  • The object was not really where it appeared to be to begin with (for exam­ple, the magi­cian fakes a trans­fer of a coin from the left hand to the right hand, then shows that the coin ‘dis­ap­peared’ from the right)
  • The object has been secretly removed (for exam­ple, the magi­cian uses a secret device, called a gim­mick, to pull an object into his sleeve)
  • The object is still there but is con­cealed (a coin can seem to van­ish from the magi­cian’s hand although in real­ity it is merely con­cealed)
Trans­po­si­tion: an object changes posi­tion in space from posi­tion A to posi­tion B Hou­dini’s Meta­mor­pho­sis (in which two peo­ple change places between locked box­es); Penn and Teller’s Hang­ing Man trick (in which Penn is appar­ently hanged to death, only to be found safe and sound in the audi­ence)
  • The object seemed to be at A, but actu­ally was already at B (for exam­ple, the magi­cian fakes the trans­fer of a coin from the right to the left hand, then pre­tends to trans­fer the coin mag­i­cally from left to right)
  • The object is still at A but seems to be at B (for exam­ple, the magi­cian fakes a coin trans­fer from the left hand to the right and then, when reveal­ing the coin by drop­ping it, uses sleight of hand to give the impres­sion that it was dropped from the right hand)
  • The object was secretly moved from A to B (for exam­ple, a coin in the left hand is secretly trans­ferred to the right hand and then is revealed there)
  • A dupli­cate object is used (for exam­ple, both hands hold iden­ti­cal coins that are revealed at differ­ent times to sim­u­late a trans­fer)
Restora­tion: an object is dam­aged and then restored to its orig­i­nal con­di­tion. Cut­ting and restor­ing a rope; saw­ing an assis­tant in half; tear­ing and restor­ing a news­pa­per; break­ing and restor­ing rub­ber bands
  • The object was not really dam­aged
  • The object was not really restored
  • A dupli­cate is used
Pen­e­tra­tion: mat­ter seems to mag­i­cally move through mat­ter Chi­nese Link­ing Rings (metal rings that link and unlink mag­i­cal­ly); Hou­dini’s Walk­ing Through A Wall trick; Coins Through The Table
  • Pen­e­tra­tions com­bine the tech­niques used in the trans­po­si­tion and restora­tion cat­e­gories
Trans­for­ma­tion: an object changes form (size, colour, shape, weight, etc.) Colour-Chang­ing Card Trick; Spell­bound (in which a coin turns into a differ­ent coin); the Pro­fes­sor’s Night­mare (in which three ropes of differ­ent length are made equal in length)

Trans­for­ma­tions can be seen as the van­ish­ing of object A com­bined with the appear­ance of object B:

  • Object A was secretly switched with object B
  • Object B was always present but was ini­tially dis­guised as object A
  • Object A is dis­guised as object B at the point of ‘trans­for­ma­tion’
Extra­or­di­nary feats (in­clud­ing men­tal and phys­i­cal feats) Extra­or­di­nary mem­ory (re­mem­ber­ing the names of all the audi­ence mem­ber­s); extra­or­di­nary cal­cu­la­tion (re­port­ing the result of mul­ti­ply­ing ran­domly selected 4-digit num­ber­s); extra­or­di­nary strength; invul­ner­a­bil­ity (spe­cific exam­ples: walk­ing on hot coals; Penn and Teller’s bul­let-catch­ing trick)
  • Might rely on rel­a­tively obscure sci­en­tific knowl­edge (such as math­e­mat­i­cal or phys­i­o­log­i­cal knowl­edge). For exam­ple, walk­ing on hot coals is harm­less when per­formed cor­rectly
Telekine­sis: ‘mag­i­cal’ lev­i­ta­tion or ani­ma­tion of an object Lev­i­ta­tion; spoon bend­ing
  • The action is caused by an exter­nal force (for exam­ple, an invis­i­ble thread)
  • The action is caused by an inter­nal force (elas­tic­i­ty, chem­i­cal reac­tion, mag­net­ism, etc.)
  • The action did not actu­ally occur (for exam­ple, a spoon ben­der can con­vince a spec­ta­tor that a sta­tion­ary spoon is still bend­ing)
Extrasen­sory per­cep­tion (ESP; includ­ing clair­voy­ance, telepa­thy, pre­cog­ni­tion, men­tal con­trol, etc.) Clair­voy­ance (ac­quir­ing infor­ma­tion that is not known to oth­ers through ESP); telepa­thy (ac­quir­ing infor­ma­tion that is known to oth­ers through ESP); pre­cog­ni­tion (ac­quir­ing infor­ma­tion from the future); men­tal con­trol (the per­former influ­ences the selec­tion process of another per­son)
  • Con­trol­ling a spec­ta­tor’s choices to give the illu­sion of free will
  • Dis­cov­er­ing hid­den infor­ma­tion (for exam­ple, read­ing infor­ma­tion that has been sealed in an envelope, fish­ing for or pump­ing infor­ma­tion from a spec­ta­tor, cold read­ing, etc.)
  • Reveal­ing appar­ent proof that infor­ma­tion announced by the spec­ta­tor was pre­vi­ously known by the magi­cian (for exam­ple, by writ­ing the announce­ment on paper and using sleight of hand to make the paper seem to come out of an enve­lope that was sealed before the announce­ment)

How many computers are in your computer?

Why are there so many places for back­doors and weird machines in your “com­puter”? Because your com­puter is in fact scores or hun­dreds, per­haps even thou­sands, of com­puter chips, many of which host weird machines and are explic­itly or implic­itly capa­ble of Tur­ing-com­plete com­pu­ta­tions (many more pow­er­ful than desk­tops of bygone eras), work­ing together to cre­ate the illu­sion of a sin­gle com­put­er. Back­doors, bugs, weird machi­nes, and secu­rity do not care about what you think—only where resources can be found and orches­trated into a com­pu­ta­tion.

If ‘the net­work is now the com­puter’, it is equally true that ‘the com­puter is now a net­work’. While per­haps the ear­li­est com­put­ers like the Altair PC really did have just one ‘com­puter’ in them, one place where all Tur­ing-com­plete tasks had to pass through, that era is long over, and a ‘com­puter’ is com­posed of count­less com­po­nents, many of which pre­vi­ously could have been a use­ful com­put­er. The phrase “com­puter” is one of con­ve­nience, rather than a hard-and-fast dis­tinc­tion. What is impor­tant are the inputs and out­puts: how capa­ble is the sys­tem as a whole and what resources does it require and how can the com­po­nents be repro­grammed?

No one cares if Google is imple­mented using 50 super­com­put­ers, 50,000 main­frames, 5 mil­lion servers, or 50 mil­lion embedded/mobile proces­sors, or a mix of any of the above exploit­ing a wide vari­ety of chips from cus­tom “ten­sor pro­cess­ing units” to cus­tom on-die sil­i­con (im­ple­mented by Intel on Xeon chips for a num­ber of its biggest cus­tomers) to FPGAs to GPUs to CPUs to still more exotic hard­ware like pro­to­type D-Wave quan­tum com­put­er­s—as long as it is com­pet­i­tive with other tech cor­po­ra­tions and can deliver its ser­vices at a rea­son­able cost. (A “super­com­puter” these days mostly looks like a large num­ber of rack­-mounted servers with unusual num­bers of GPUs & con­nected by unusu­ally high­-speed Infini­Band con­nec­tions and is not that differ­ent from a dat­a­cen­ter.) Any of these pieces of hard­ware could sup­port mul­ti­ple weird machines on many differ­ent lev­els of com­pu­ta­tion depend­ing on their inter­nal dynam­ics & con­nec­tiv­i­ty. The sys­tem can be seen on many lev­els, each equally invalid but use­ful for differ­ent pur­pos­es. Are you a ‘sin­gle bio­log­i­cal intel­li­gence’ or a community/ecosystem of human cells/neurons/bacteria/yeast/viruses/parasites? And does it mat­ter in the slight­est bit to any­one you might wrong?

#2166, “Stack” Here is an exam­ple of the ill-de­fined nature of the ques­tion: on your desk or in your pock­et, how many com­put­ers do you cur­rently have? How many com­put­ers are in your “com­puter”? Did you think just one? Let’s take a closer look—it’s com­put­ers all the way down. You might think you have just the one large CPU occu­py­ing pride of place on your moth­er­board, and per­haps the GPU too, but the com­pu­ta­tional power avail­able goes far beyond just the CPU/GPU, for a vari­ety of rea­sons: tran­sis­tors and proces­sor cores are so cheap now that it often makes sense to use a sep­a­rate core for real­time or higher per­for­mance, for secu­rity guar­an­tees, to avoid hav­ing to bur­den the main OS with a task, for com­pat­i­bil­ity with an older archi­tec­ture or exist­ing soft­ware pack­age, because a DSP or core can be pro­grammed faster than a more spe­cial­ized ASIC can be cre­at­ed, or because it was the quick­est pos­si­ble solu­tion to slap down a small CPU and they could­n’t be both­ered to shave some pen­nies17… When­ever a periph­eral or device is made, the Wheel of Rein­car­na­tion begins to turn. Fur­ther, many of these com­po­nents can be used as com­pu­ta­tional ele­ments even if they were not intended to be or try to hide that func­tion­al­i­ty. (For exam­ple, the Com­modore 64’s floppy drive‘s CPU run­ning Com­modore DOS was used as a source of spare com­pute power & for defeat­ing copy­-pro­tec­tion schemes, because it was as pow­er­ful; one can offload to the ’co-proces­sor’ tasks like com­put­ing frac­tals, 3D math rou­tines for ani­mat­ing demos, com­puter chess…)

Thus:

  • A com­mon AMD/Intel x86 CPU has bil­lions of tran­sis­tors, devoted to many dis­crete com­po­nents:

    • Each of the >2 CPU cores can run inde­pen­dent­ly, shut­ting on or off as nec­es­sary, and has its own pri­vate caches L1–L3 (often big­ger than desk­top com­put­ers’ entire RAM a few decades ago18, and likely phys­i­cally big­ger than their CPUs were to boot), and must be regarded as indi­vid­u­als. Fur­ther, the CPU as a whole is repro­gram­ma­ble through microc­o­de, such as to work around errors in the chip design, so what those CPUs com­pute changes.

    • CPUs sport increas­ingly opaque fea­tures, such as the man­age­ment engines/secure enclaves, like the Intel Man­age­ment Engine (with a JVM for pro­gram­ma­bil­ity; Ruan 2014 & SGX), or AMD’s Plat­form Secu­rity Proces­sor (PSP) or Android’s TEEs or Titan chips; these hard­ware mod­ules typ­i­cally are full com­put­ers in their own right, run­ning inde­pen­dently of the host and able to tam­per with it (and have con­tributed to ter­mi­no­log­i­cal con­fu­sion, as the for­merly sim­ple pro­tec­tion ring lev­els of 0–3 have had to be aug­mented with “ring −1”, “ring −2”, and “ring −3”). Intel’s ME runs a pro­pri­etary unau­ditable fork of MINIX (an OS bet­ter known for its role in the cre­ation of Lin­ux), whose secu­rity impli­ca­tions con­cerned Google enough to launch a project to remove MINIX from its CPUs & its Titan chip to cryp­to­graph­i­cally ver­ify firmware on boot.

      • any float­ing-point unit may be Tur­ing-com­plete through encod­ing into float­ing-point oper­a­tions in the spirit of FRACTRAN19
      • the MMU can be pro­grammed into a page-fault weird machine dri­ven by a CPU stub (see above)

  • DSP units, cus­tom sil­i­con: ASICs for video for­mats like h.264 prob­a­bly are not Tur­ing-com­plete (de­spite their sup­port for com­pli­cated deltas and com­pres­sion tech­niques which might allow some­thing like Wang tiles), but for exam­ple Apple’s A9 mobile sys­tem-on-a-chip goes far beyond sim­ply a dual-core ARM CPU and GPU as like Intel/AMD desk­top CPUs, it includes the secure enclave (a phys­i­cally sep­a­rate ded­i­cated CPU core), but it also includes an image co-proces­sor, a motion/voice-recognition coproces­sor (par­tially to sup­port Sir­i), and appar­ently a few other cores. These ASICs are some­times there to sup­port AI tasks, and pre­sum­ably spe­cial­ize in matrix mul­ti­pli­ca­tions for neural net­works; as recur­rent neural net­works are Tur­ing-com­plete… Other com­pa­nies have rushed to expand their sys­tem-on-chips as well, like Motorola or Qual­comm

    • Mark Ermolov notes that a given sys­tem on a chip (SoC) may have not just mul­ti­ple CPUs, but eas­ily 5 differ­ent CPU archi­tec­tures all rep­re­sent­ed:

      It’s amaz­ing how many het­ero­ge­neous CPU cores were inte­grated in Intel Sil­ver­mon­t’s Moore­field SoC (ANN): x86, ARC, LMT, 8051, Audio DSP, each run­ning own firmware and sup­port­ing JTAG inter­face.

    • even weirder spe­cial-pur­pose chips like the Mac­book Touch Bar’s chips which run lit­tle WatchOS apps & fin­ger­print authen­ti­ca­tion on a Apple T1/T2 SoC (us­ing an ARM CPU) inde­pen­dent of the lap­top OS, which can, of course, be hacked to run Linux

  • moth­er­board BIOS & man­age­ment engines (on top of the CPU equiv­a­lents), typ­i­cally with net­work access

    These man­age­ment or debug­ging chips may be ‘acci­den­tally’ left enabled on ship­ping devices, like the Via C3 CPUs’s embed­ded ARM CPUs.

  • GPUs have >100s of sim­ple GPU cores, which can run neural net­works well (which are highly expres­sive or Tur­ing-com­plete), or do gen­er­al-pur­pose com­pu­ta­tion (al­beit slower than the CPU)20

  • smart­phones: in addi­tion to all the other units men­tioned, there is an inde­pen­dent base­band proces­sor run­ning a pro­pri­etary real­time OS for han­dling radio com­mu­ni­ca­tions with the cel­lu­lar towers/GPS/other things, or pos­si­bly more than one vir­tu­al­ized using some­thing like L4. Base­band proces­sors have been found with back­doors, in addi­tion to all their vul­ner­a­bil­i­ties.

    Given ARM CPUs are used in most of these embed­ded appli­ca­tions, it’s no sur­prise ARM likes to boast that “a mod­ern smart­phone will con­tain some­where between 8 and 14 ARM proces­sors, one of which will be the appli­ca­tion proces­sor (run­ning Android or iOS or what­ev­er), while another will be the proces­sor for the base­band stack.”.

  • SIM cards for smart­phones are much more than sim­ple mem­ory cards record­ing your sub­scrip­tion infor­ma­tion, as they are smart cards which can inde­pen­dently run Java Card appli­ca­tions (ap­par­ently NFC chips may also be like this as well), some­what like the JVM in the Intel Man­age­ment Engine. Nat­u­ral­ly, SIM cards can be hacked too and used for sur­veil­lance etc.

  • the IO con­trollers for tape dri­ves, hard dri­ves, flash dri­ves, or SSD dri­ves etc typ­i­cally all have ARM proces­sors to run the on-disk firmware for tasks like hid­ing bad sec­tors from the oper­at­ing sys­tem or accel­er­at­ing disk encryp­tion or doing wear lev­el­ing; these can be hacked.

  • net­work chips do inde­pen­dent pro­cess­ing for DMA. (This sort of inde­pen­dence, in con­junc­tion with the moth­er­board & CPU man­age­ment engi­nes, is why fea­tures like Wake-on-LAN for net­boot work.)

  • USB/Thunderbolt cables/devices, or moth­er­board­-at­tached devices: an embed­ded proces­sor on device is needed for nego­ti­a­tion of data/power pro­to­cols at the least for cables/batteries/chargers21, and may be even more heavy duty with mul­ti­ple addi­tional spe­cial­ized proces­sors them­selves like WiFi adapters or key­boards or mice or SD cards.

    In the­o­ry, most of these are sep­a­rate and are at least pre­vented from directly sub­vert­ing the host via DMA by in-be­tween IOMMU units, but the devil is in the details…

  • mon­i­tor-em­bed­ded CPU for con­trol of dis­play­ing what­ever the GPU sends it (part of a tra­di­tion going back to smart tele­types)

  • …

So a desk­top or smart­phone can rea­son­ably be expected to have any­where from 15 to sev­eral thou­sand “com­put­ers” (in the sense of a Tur­ing-com­plete device which can be pro­grammed in a use­fully gen­eral fash­ion with lit­tle or no code run­ning on the ‘offi­cial’ com­put­er); which is com­pu­ta­tion­ally pow­er­ful enough to run many pro­grams from through­out com­put­ing his­to­ry; and which can be exploited by an adver­sary for sur­veil­lance, exfil­tra­tion, or attacks against the rest of the sys­tem.

None of this is unusual his­tor­i­cal­ly, as even the ear­li­est main­frames tended to be mul­ti­ple com­put­ers, with the main com­puter doing batch pro­cess­ing while addi­tional smaller com­put­ers took care of high­-speed I/O oper­a­tions that would oth­er­wise choke the main com­put­ers with inter­rupts.

In prac­tice, aside from the com­puter secu­rity com­mu­nity (as all these com­put­ers are inse­cure and thus use­ful attack routes), users don’t care that our com­put­ers, under the hood, are insanely com­plex and more accu­rately seen as a mot­ley menagerie of hun­dreds of com­put­ers awk­wardly yoked togeth­er; as long as it is work­ing cor­rect­ly, he per­ceives & uses it as a sin­gle pow­er­ful com­put­er.

Until it stops work­ing as expect­ed.

  1. The baroque com­plex­ity of Send­mail pos­si­bly con­tributed to its infa­mous rep­u­ta­tion for inse­cu­ri­ty—it was one of the exploit vec­tors of the Mor­ris worm, and for years shipped with a remote root back­door (WIZ).↩︎

  2. Dwarf Fortress pro­vides clock­work mech­a­nisms, so TC is unsur­pris­ing; but the water is imple­mented as a sim­ple cel­lu­lar automa­tion, so there might be more ways of get­ting TC in DF! The DF wiki cur­rently lists 4 poten­tial ways of cre­at­ing logic gates: the flu­ids, the clock­work mech­a­nisms, mine-carts, and creature/animal logic gates involv­ing doors+­pres­sure-sen­sors.↩︎

  3. The full PDF spec­i­fi­ca­tion is noto­ri­ously bloat­ed. For exam­ple, in a PDF viewer which sup­ports enough of the PDF spec, like the Google Chrome Browser, one can play Break­out (be­cause PDF includes its own weird sub­set of JavaScrip­t). The Adobe PDF viewer includes func­tion­al­ity as far afield as 3D CAD sup­port.↩︎

  4. See Think Math’s domino logic gates & 2014 demon­stra­tion of a 4-bit adder imple­mented using domino logic.↩︎

  5. Ear­lier ver­sions required play­ers to take all pos­si­ble actions, but the 2019 paper claims to remove this assump­tion and force all actions, ren­der­ing the con­struc­tion fully mechan­i­cal.↩︎

  6. pg441-442, The com­plete works of Ralph Waldo Emer­son: Nat­ural his­tory of intel­lect, and other papers, Vol. 12↩︎

  7. “48. The best book on pro­gram­ming for the lay­man is Alice in Won­der­land; but that’s because it’s the best book on any­thing for the lay­man.” —“Epi­grams on Pro­gram­ming”, Perlis 1982.↩︎

  8. ‘Think­ing out­side the box’ can be this, but often isn’t. This is a spe­cific pat­tern of reduc­tion­ism, and many instances of ‘think­ing out­side the box’ are other pat­terns, like putting on another lay­er, or elim­i­nat­ing the sys­tems in ques­tion entire­ly.↩︎

  9. Feyn­man:

    The phe­nom­e­non of accept­ing for flight, seals that had shown ero­sion and blow-by in pre­vi­ous flights, is very clear. The Chal­lenger flight is an excel­lent exam­ple. There are sev­eral ref­er­ences to pre­vi­ous flights; the accep­tance and suc­cess of these flights are taken as evi­dence of safe­ty. But ero­sion and blowby are not what the design expect­ed. They are warn­ings that some­thing is wrong. The equip­ment is not oper­at­ing as expect­ed, and there­fore there is a dan­ger that it can oper­ate with even wider devi­a­tions in the unex­pected and not thor­oughly under­stood way. The fact that this dan­ger did not lead to cat­a­stro­phe before is no guar­an­tee that it will not the next time, unless it is com­pletely under­stood. When play­ing Russ­ian roulette the fact that the first shot got off safely is lit­tle com­fort for the next. The ori­gin and con­se­quences of the ero­sion and blow-by were not under­stood. They did not occur equally on all flights and all joints; some­times more, and some­times less. Why not some­time, when what­ever con­di­tions deter­mined it were right, still more lead­ing to cat­a­stro­phe?

    In spite of these vari­a­tions from case to case, offi­cials behaved as if they under­stood it, giv­ing appar­ently log­i­cal argu­ments to each other often depend­ing on the “suc­cess” of pre­vi­ous flights…

    ↩︎

  10. Dem­ocri­tus: “By con­ven­tion sweet is sweet, bit­ter is bit­ter, hot is hot, cold is cold, color is col­or; but in truth there are only atoms and the void.”↩︎

  11. A fic­tional exam­ple from Ender’s Game is worth not­ing: if vic­tory in Bat­tle School is defined by 4 sol­diers at the cor­ner of the enemy gate & some­one pass­ing through, then why not—shades of Eurisko—skip fight­ing entirely & go straight for the gate?↩︎

  12. pg356 of A Bur­glar’s Guide to the City, Geoff Man­augh 2016:

    Schatz’s exhor­ta­tion to play­ers to move against the archi­tec­ture, not with it, to uncover a scene’s pos­si­ble crimes, is use­ful not only in the world of games. Ignor­ing the paths laid out by archi­tects and even remak­ing a space from within are some of the most fun­da­men­tal ways in which bur­glars mis­use the built envi­ron­men­t…In one of the most inter­est­ing moments in Bill Mason’s mem­oir, he sees that archi­tec­ture can be made to do what he wants it to do; it’s like watch­ing a char­ac­ter in Star Wars learn to use the Force.

    …he explains that his intended prize was locked inside a room whose door was too closely guarded for him to slip through. Then he real­izes the obvi­ous: he has been think­ing the way the hotel wanted him to think—the way the archi­tects had hoped he would behave—look­ing for doors and hall­ways when he could sim­ply carve a new route where he wanted it. The ensu­ing real­iza­tion delights him. “Elated at the idea that I could cut my own door right where I needed one,” he writes, Mason sim­ply breaks into the hotel suite adja­cent to the main office. There, he flings open the clos­et, pushes aside the hang­ers, and cuts his way from one room into the other using a dry­wall knife. In no time at all, he has cut his “own door” through to the man­ager’s office, where he takes what­ever he wants—de­part­ing right back through the very “door” he him­self made. It is archi­tec­tural surgery, pure and sim­ple.

    Lat­er, Mason actu­ally mocks the idea that a per­son would remain reliant on doors, mak­ing fun of any­one who thinks bur­glars, in par­tic­u­lar, would respect the lim­i­ta­tions of archi­tec­ture. “Surely if some­one were to rob the place,” he writes in all ital­ics, barbed with sar­casm, “they’d come in as respectable peo­ple would, through the door pro­vided for the pur­pose. Maybe that explains why peo­ple will have 4 heavy-duty locks on a solid oak door that’s right next to a glass win­dow.” Peo­ple seem to think they should lock­-pick or kick their way through solid doors rather than just take a $10 dry­wall knife and carve whole new hall­ways into the world. Those peo­ple are mere slaves to archi­tec­ture, spa­tial cap­tives in a world some­one else has designed for them.

    Some­thing about this is almost unset­tlingly bril­liant, as if it is non­bur­glars who have been mis­us­ing the built envi­ron­ment this whole time; as if it is non­bur­glars who have been unwill­ing to ques­tion the world’s most basic spa­tial assump­tions, too scared to think past the tyranny of archi­tec­ture’s long-held behav­ioral expec­ta­tion­s….Be­cause doors are often the stur­di­est and most for­ti­fied parts of the wall in front of you, they are a dis­trac­tion and a trap. By com­par­ison, the wall itself is often more like tis­sue paper, just dry­wall and some 2×4s, with­out a lock or a chain in sight. Like clouds, apart­ment walls are mostly air; seen through a bur­glar’s eyes, they aren’t even there. Cut a hole through one and you’re in the next room in sec­onds.

    ↩︎

  13. Stage magi­cian Teller, of Penn & Teller, puts this well in inter­views: what makes stage magic work is hard work. Teller, “Teller Reveals His Secrets: The small­er, qui­eter half of the magi­cian duo Penn & Teller writes about how magi­cians manip­u­late the human mind” 2012

    I think you’ll see what I mean if I teach you a few prin­ci­ples magi­cians employ when they want to alter your per­cep­tion­s…­Make the secret a lot more trou­ble than the trick seems worth. You will be fooled by a trick if it involves more time, money and prac­tice than you (or any other sane onlook­er) would be will­ing to invest. My part­ner, Penn, and I once pro­duced 500 live cock­roaches from a top hat on the desk of talk-show host David Let­ter­man. To pre­pare this took weeks. We hired an ento­mol­o­gist who pro­vided slow-mov­ing, cam­er­a-friendly cock­roaches (the kind from under your stove don’t hang around for close-ups) and taught us to pick the bugs up with­out scream­ing like pread­o­les­cent girls. Then we built a secret com­part­ment out of foam-core (one of the few mate­ri­als cock­roaches can’t cling to) and worked out a devi­ous rou­tine for sneak­ing the com­part­ment into the hat. More trou­ble than the trick was worth? To you, prob­a­bly. But not to magi­cians.

    Or in his Hutt­son 2015 inter­view:

    Matt: “So why don’t you explain all your tricks?”

    Teller: “Because the short expla­na­tion—the expla­na­tion that you’d have to do dur­ing a the­atri­cal or TV per­for­mance—is dull and no fun. The great­est secret to mak­ing a decep­tive piece of magic is you do it by the ugli­est pos­si­ble means. It’s com­plex, it’s unro­man­tic, it’s unclever. Because there are no big secrets. There is no safe full of magic secrets some­where. Jim Stein­meyer said he thinks most of the pub­lic believes there’s a big safe that con­tains all the magic secrets. The biggest job for a magi­cian, he says, is to con­ceal the fact that that safe is emp­ty. Because every magic secret is just a minor mod­i­fi­ca­tion of some­thing that you fully under­stand in every­day life. Take sus­pend­ing some­thing with a thread, for exam­ple. Every­body’s not been able to see a piece a thread when they were try­ing to put it through a nee­dle. What makes it diffi­cult to find is light­ing and back­ground. If a magi­cian’s using a thread on stage, say, to lev­i­tate a ball, he must use light­ing and back­ground to con­ceal the thread. There’s no obscure secret in that. You learned that play­ing in your grand­moth­er’s sewing box. Every magic ‘secret’ is hid­ing in plain sight in the every­day world. It’s not news, and emi­nently drab.”

    ↩︎

  14. Hou­dini’s trick of Sir Arthur Conan Doyle exem­pli­fies these strate­gies. No one would expect Hou­dini to ren­o­vate a room just for a trick, to have learned a stegano­graphic code to com­mu­ni­cate the phrase Doyle wrote on a piece of phrase to the assis­tant with­out Doyle notic­ing, or the assis­tant to manip­u­late a mag­netic pole behind a small sus­pended slate board, hid­ing it in the view­ers’ pre­cise blind spot in order to make it appear as if the chalk were hov­er­ing in mid-air & writ­ing by itself. Doyle did not, and dis­be­lieved Hou­dini’s state­ment it was merely a trick. But Doyle should have remem­bered Hume’s dic­tum: which is more like­ly—wit­ness­ing the para­nor­mal, or that some­where in the world there was a man as cun­ning, care­ful, & com­pul­sive as Hou­dini? The lat­ter!↩︎

  15. Speak­ing of ‘social engi­neer­ing’, why was Face­book’s suc­cess in spread­ing from a niche of col­lege stu­dents to much of the world by offer­ing such super­fi­cial social net­work­ing so sur­pris­ing to so many? Per­haps its suc­cess is a hint that the under­ly­ing logic of social inter­ac­tions are much more abstractable than, and not as rich & sub­tle as, we’d pre­fer to think.↩︎

  16. We adopt Lam­ont and Wise­man’s clas­si­fi­ca­tion7 of con­jur­ing or magic effects into 9 main cat­e­gories.↩︎

  17. An exam­ple of this kind of men­tal­ity is noted by pkaye on HN

    Reminds of when I was doing firmware devel­op­ment and the ASIC team would ask if they could toss in a extra Cor­tex-M3 core to solve spe­cific con­trol prob­lems. Those cores would be used as pro­gram­ma­ble state machines. For the ASIC team toss­ing in a extra core was free com­pared to cus­tom logic design. How­ever for the firmware team it would be another job to write and test that firmware. We had designs with upwards of 10 Cor­tex-M3 cores. I’ve heard from a friend at another employer had some­thing like 32 such cores and it was a pain to debug.

    ↩︎

  18. Eg a 2017 Intel Core i9-7900X CPU has ~24MB cache total, con­sid­er­ably larger than, say, a 1996 desk­top Power Mac­in­tosh 5200 LC’s 16MB RAM (with 16KB CPU cache!).↩︎

  19. Or might be run­ning appar­ently harm­less FP oper­a­tions which still encode a (deep) NN by exploit­ing FP set­tings enabling non­lin­ear­i­ties. See also “Adver­sar­ial Repro­gram­ming of Neural Net­works”, Elsayed et al 2018 & Neekhara et al 2018. A related topic is “machine teach­ing”: Zhu 2013, Zhu 2015, Wang et al 2018, Sucholut­sky & Schon­lau 2020.↩︎

  20. Arrigo Tri­ulzi in 2008 demoed an exploit sys­tem which com­bined a hack of the (com­pu­ta­tion­ally lim­it­ed) NIC and GPU to run inde­pen­dently of the host OS/CPU: “Project Maux Mk.II: ‘I Own the NIC, Now I Want A Shell!’”/“The Jedi Packet Trick takes over the Death­star (or: ‘tak­ing NIC back­doors to the next level’)”.↩︎

  21. Ken Shirriff amus­ingly notes in a Mac­book charger analy­sis: “One unex­pected com­po­nent is a tiny cir­cuit board with a micro­con­troller, which can be seen above. This 16-bit proces­sor con­stantly mon­i­tors the charg­er’s volt­age and cur­rent. It enables the out­put when the charger is con­nected to a Mac­book, dis­ables the out­put when the charger is dis­con­nect­ed, and shuts the charger off if there is a prob­lem. This proces­sor is a Texas Instru­ments MSP430 micro­con­troller, roughly as pow­er­ful as the proces­sor inside the orig­i­nal Mac­in­tosh. [The proces­sor in the charger is a MSP430F2003 ultra low power micro­con­troller with 1kB of flash and just 128 bytes of RAM. It includes a high­-pre­ci­sion 16-bit ana­log to dig­i­tal con­vert­er. More infor­ma­tion is here.]”↩︎