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 be­ing Tur­ing-com­plete, are ex­tremely com­mon. Al­most any sys­tem of suffi­cient com­plex­i­ty—un­less care­fully en­gi­neered oth­er­wise—­may be found to ‘ac­ci­den­tally’ sup­port Tur­ing-com­plete some­where in­side it, even sys­tems which would ap­pear to have not the slight­est thing to do with com­pu­ta­tion. Soft­ware sys­tems are es­pe­cially sus­cep­ti­ble to this, which often leads to se­ri­ous se­cu­rity prob­lems as the Tur­ing-com­plete com­po­nents can be used to run at­tacks 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 de­fi­n­i­tions) the prop­erty of a sys­tem be­ing able to, un­der some sim­ple rep­re­sen­ta­tion of in­put & out­put, com­pute any pro­gram of in­ter­est, in­clud­ing an­other com­puter in some form.

TC, be­sides be­ing foun­da­tional to com­puter sci­ence and un­der­stand­ing many key is­sues like “why a per­fect an­tivirus pro­gram is im­pos­si­ble”, is also weirdly com­mon: one might think that such uni­ver­sal­ity as a sys­tem be­ing 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 op­po­site—it is diffi­cult to write a use­ful sys­tem which does not im­me­di­ately tip over into TC. “Sur­pris­ing” ex­am­ples of this be­hav­ior re­mind us that TC lurks every­where, and se­cu­rity is ex­tremely diffi­cult.

I like demon­stra­tions of TC lurk­ing in sur­pris­ing places be­cause they are often a dis­play of con­sid­er­able in­ge­nu­ity, and feel like they are mak­ing a pro­found philo­soph­i­cal point about the na­ture of com­pu­ta­tion: com­pu­ta­tion is not some­thing es­o­teric which can ex­ist 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 al­most in­evitably pop up un­less ac­tively pre­vent­ed.

Accidentally Turing-complete

“Any suffi­ciently com­pli­cated C or For­tran pro­gram con­tains an ad hoc, in­for­mal­ly-spec­i­fied, bug-rid­den, slow im­ple­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” es­o­teric pro­gram­ming lan­guages (esolangs). So FRACTRAN, as ex­tra­or­di­nar­ily min­i­mal­ist as it is, does not count; nor would a de­lib­er­ately ob­fus­cated lan­guage like Mal­bolge (where it took years to write a triv­ial pro­gram) count be­cause it was de­signed to be an es­olang; but nei­ther would Con­way’s Game of Life count be­cause ques­tions about whether it was TC ap­peared al­most im­me­di­ately upon pub­li­ca­tion and be­ing 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 au­toma­ton into them or en­code log­i­cal cir­cuits, or if air­plane ticket plan­ning/­val­i­da­tion is not just NP-hard or EXPSPACE-hard but un­de­cid­able (be­cause of the com­plex rules air­lines re­quire). Many con­fig­u­ra­tion or spe­cial-pur­pose lan­guages or tools or com­pli­cated games turn out to vi­o­late the Rule of least power & be “ac­ci­den­tally Tur­ing-com­plete”, like Send­mail1, Me­di­aWiki tem­plates, sed or re­peated reg­ex­p/find­-re­place com­mands in an ed­i­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 it­er­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 es­olangs “///” or Thue), XSLT, In­fi­nite Minesweeper, Dwarf Fortress2, Star­craft, Minecraft, Ant, Trans­port Ty­coon & Cities: Sky­line, C++ tem­plates & Java gener­ics, RNA/DNA com­put­ing etc are TC but these are not sur­pris­ing ei­ther: many games sup­port script­ing (ie TC-ness) to make their de­vel­op­ment eas­ier and en­able fan mod­i­fi­ca­tions, so games’ TC may be as sim­ple as in­clud­ing syn­tax for call­ing out to a bet­ter-known lan­guage like Perl, or it may just be an ob­scure part of a stan­dard for­mat (most peo­ple these days are prob­a­bly un­aware that True­Type & many fonts are Post­Script pro­grams based on stack ma­chi­nes, sim­i­lar to DWARF de­bug­ging and ELF meta­data, or that some mu­sic for­mats go be­yond MIDI in pro­vid­ing script­ing ca­pa­bil­i­ties and must be in­ter­preted to be dis­played; once one knows this, then fonts be­ing TC are no more sur­pris­ing than TeX doc­u­ments be­ing TC, lead­ing of course, to many se­vere & fas­ci­nat­ing font or me­dia se­cu­rity vul­ner­a­bil­i­ties such as the BLEND vul­ner­a­bil­ity or SNES & NES code ex­ploit­ing Linux sys­tems. Other for­mats, like PDF, are sim­ply ap­palling.3). Sim­i­lar­ly, such feats as cre­at­ing a small Tur­ing ma­chine us­ing Le­gos or domi­nos4 would not count, since we al­ready know that me­chan­i­cal com­put­ers work. On the other hand, “weird ma­chines” are a fer­tile ground of “that’s TC?” re­ac­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 pow­er­ful/flex­i­ble. For ex­am­ple, if Boolean logic can be im­ple­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, de­fi­n­i­tion­s/ab­bre­vi­a­tions, reg­u­lar ex­pres­sions (e­spe­cially with any ex­ten­sions or cus­tom fea­tures), or any other kind of ‘search and re­place’ func­tion­al­ity is an­other red flag, as they sug­gest that a cel­lu­lar au­toma­ton or tag sys­tem is lurk­ing. This ap­plies 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 in­ter­face or API, even if locked down, may not be locked down quite enough. An ac­tual 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 es­cape from the sand­box. Op­er­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 an­other source of prim­i­tives, as they may ‘de­pend’ on the data they are op­er­at­ing over in some way, im­ple­ment­ing differ­ent op­er­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 en­cod­ing of da­ta.

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

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

  • CSS with­out the as­sump­tion of a dri­ving mouse click (per­haps some sort of Wang tile us­ing re­flec­tions and con­di­tion­al­s?)

  • Uni­code (!): Nico­las Se­riot sug­gests that Uni­code’s bidi­rec­tional al­go­rithms (in­tended for dis­play­ing scripts like Ara­bic or He­brew 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).

  • Hu­man vi­sual il­lu­sions: Changizi 2008 presents am­bigu­ous im­ages in a cir­cuit-like for­mat, whose depth per­cep­tion ‘flips’ based on the ‘in­put’ or top of the cir­cuit, which are anal­o­gous to OR/AND/NOT/XOR com­pu­ta­tions; the ex­is­tence of these ‘vi­sual cir­cuits’ hints at the pos­si­bil­ity of ‘TC-com­plete’ im­ages (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 in­put into some­thing which trans­forms in­put to out­put, one can typ­i­cally lever­age that con­trol into ful­l-blown TC. This mat­ters be­cause, if one is clev­er, it pro­vides an es­cape hatch from a sys­tem which is small, pre­dictable, con­trol­lable, and se­cure, 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 in­sert an­other pro­gram into your pro­gram. Even if there is no way to out­right ‘es­cape’ the sand­box, such hid­den pro­grams can be dan­ger­ous, by ex­tract­ing in­for­ma­tion about the sur­round­ing pro­gram (eg JS em­bed­ded in a web page which can ex­tract your pass­words by us­ing Row ham­mer to at­tack your hard­ware di­rect­ly, even if it can’t ac­tu­ally es­cape your web browser), or can take the host into strange & un­charted (and untest­ed) ter­ri­to­ries.

That we find these demon­stra­tions sur­pris­ing is it­self a demon­stra­tion of our lack of imag­i­na­tion and un­der­stand­ing of com­put­ers, com­puter se­cu­ri­ty, and AI. We pre­tend that we are run­ning pro­grams on these sim­ple ab­stract ma­chines which do what we in­tu­itively ex­pect, 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. Se­cure sys­tems have to be built by con­struc­tion; once the ge­nie has been let out of the lamp, it’s diffi­cult to patch the lamp.

An ac­tive area of re­search is into lan­guages & sys­tems care­fully de­signed and proven to not be TC (eg. to­tal func­tional pro­gram­ming). Why this effort to make a lan­guage in which many pro­grams can’t be writ­ten? Be­cause TC is in­ti­mately tied to Godel’s in­com­plete­ness the­o­rems & Rice’s the­o­rem, al­low­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 ex­am­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 re­sources, that one im­ple­men­ta­tion of a pro­to­col is cor­rect or equiv­a­lent to an­other im­ple­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 im­por­tant for de­clar­a­tive lan­guages like SQL where the query op­ti­mizer be­ing able to trans­form queries is key to ac­cept­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 de­scent for fit­ting ma­chine learn­ing mod­els and some SQL ex­ten­sions make it TC any­way by al­low­ing ei­ther a cyclic tag sys­tem to be en­cod­ed, the model DSL, or to call out to PL/SQL) etc.

Lan­guages or sys­tems which un­in­ten­tion­ally cross over the line into be­ing TC can be amus­ing or use­ful (although usu­ally not), but they also have some se­ri­ous im­pli­ca­tions: such sys­tems, be­cause they were never ex­pected to be pro­gram­ma­ble, can be harm­ful, or ex­tremely in­se­cure & a crack­er’s de­light, as ex­em­pli­fied by the “lan­guage-the­o­retic se­cu­rity” par­a­digm, based on ex­ploit­ing “weird ma­chines”; some of the lit­er­a­ture:

Most re­cent­ly, Spec­tre & gen­er­al­iza­tions (Mcil­roy et al 2019) can be in­ter­preted as pro­vid­ing a whole ‘shadow com­puter’ in the CPU via spec­u­la­tive ex­e­cu­tion which can be pro­grammed to do things like run mal­ware with­out vis­i­bly ex­e­cut­ing any of the mal­ware in­struc­tions while hav­ing side-effects in the real com­put­er. Spec­tre is in­ter­est­ing in be­ing a class of vul­ner­a­bil­i­ties which have ex­isted for decades in CPU ar­chi­tec­tures that were closely scru­ti­nized for se­cu­rity prob­lems, but just sort of fell into a col­lec­tive hu­man blind spot. No­body thought of con­trol­lable spec­u­la­tive ex­e­cu­tion as be­ing a ‘com­puter’ which could be ‘pro­grammed’. Once some­one no­ticed, be­cause it was a pow­er­ful com­puter and of course TC, it could be used in many ways to at­tack stuff.

“Too pow­er­ful” lan­guages can also man­i­fest as nasty DoS at­tacks; the fuzz tester afl found that it could cre­ate an in­fi­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

“Un­cle Mil­ton In­dus­tries has been sell­ing ant farms to chil­dren since 1956. Some years ago, I re­mem­ber open­ing one up with a friend. There were no ac­tual ants in­cluded in the box. In­stead, there was a card that you filled in with your ad­dress, and the com­pany would mail you some ants. My friend ex­pressed sur­prise that you could get ants sent to you in the mail. I replied: ‘What’s re­ally in­ter­est­ing is that these peo­ple will send a tube of live ants to any­one you tell them to.’”

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

“Every drop of blood has great tal­ent; the orig­i­nal cel­lule seems iden­ti­cal in all an­i­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 re­mote effect now horns, now wings, now scales, now hair; and the same nu­mer­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 ap­pear­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 In­tel­lect”, 18936

“The ques­tion is”, said Al­ice, “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 Al­ice Found There (1872)7

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

Cypher, The Ma­trix

To draw some par­al­lels here and ex­pand Dul­lien 2017, I think un­ex­pected Tur­ing-com­plete sys­tems and weird ma­chines 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 se­cu­rity mind­set or hacker mind­set.

What they/OP/se­cu­ri­ty/speedrun­ning/hack­ing/so­cial-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 re­duc­tion­ism run amok, where one ‘sees through’ ab­strac­tions to a ma­nip­u­la­ble re­al­i­ty.8 Like Neo in the Ma­trix—a deeply cliche anal­ogy for hack­ing, but cliche be­cause it res­onates—one achieves en­light­en­ment by see­ing through the sur­face il­lu­sions of ob­jects and can now see the end­less lines of green code which make up the Ma­trix (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 re­ally made out of many Y, which form an en­tirely differ­ent sys­tem, Z; I will now pro­ceed to ig­nore the X and un­der­stand how Z works, so I may use the Y to thereby change W how­ever I like”.

Ab­strac­tions are vi­tal, but ab­strac­tions also al­ways leak. (“You’re very clev­er, young man, but it’s re­duc­tion­ism all the way down!”) This is in some sense the op­po­site of a math­e­mati­cian: a math­e­mati­cian tries to ‘see through’ a com­plex sys­tem’s ac­ci­den­tal com­plex­ity up to a sim­pler more-ab­stract more-true ver­sion which can be un­der­stood & ma­nip­u­lat­ed—but for the hack­er, all com­plex­ity is es­sen­tial, and they are in­stead try­ing to unsee the sim­ple ab­stract 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 ab­stract 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 ex­e­cu­tion paths & find an ex­ploit triv­ially prov­ing it in­cor­rec­t.) Or­di­nary users ask only that all their every­day ex­am­ples of Ys trans­forms into Z cor­rect­ly; they for­get to ask whether all and only cor­rect ex­am­ples of Ys trans­form into cor­rect Zs, and whether only cor­rect Zs can be con­structed to be­come Ys. Even a sin­gle ‘anom­aly’, ap­par­ently triv­ial in it­self, can in­di­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 ac­count 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 in­crease 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 ‘ob­jects’ with rich mean­ing­ful se­man­tics, but re­al­ly, it’s just made out of bits which mean noth­ing and only ac­ci­den­tally can be in­ter­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 or­der and read one string of bits in a differ­ent way, now you have by­passed 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 or­der’, but it’s re­ally again just made out of bits and mem­ory lo­ca­tions, and mess­ing with them in par­tic­u­lar ways, such as de­lib­er­ately over­load­ing the RAM to cause mem­ory al­lo­ca­tion er­rors, can give you in­fi­nite ‘ve­loc­ity’ or shift you into al­ter­nate co­or­di­nate sys­tems in the true physics, al­low­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 ho­tel room, peo­ple see ‘doors’ and ‘locks’ and ‘walls’, but re­al­ly, they are just made out of atoms arranged in a par­tic­u­lar or­der, and you can move some atoms around more eas­ily than oth­ers, and in­stead of go­ing through a ‘door’ you can just cut a hole in the wall12 (or ceil­ing) and ob­tain ac­cess to a space. At Los Alam­os, Richard Feyn­man, among other tac­tics, ob­tained clas­si­fied pa­pers by reach­ing in un­der­neath draw­ers and ig­nored the locks en­tire­ly.

    • One analy­sis of the movie Die Hard, “Nakatomi space”, high­lights how it & the Is­rael mil­i­tary’s mouse-hol­ing in the Bat­tle of Nablus treat build­ings as kinds of ma­chi­nes, which can be ma­nip­u­lated in weird ways to move around to at­tack their en­e­mies.

    • That ex­am­ple re­minds 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 so­lu­tions which—­like a ma­gi­cian’s trick­—vi­o­late one’s as­sump­tions about the locked room: whether it was al­ways 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 in­spired Umineko’s mys­ter­ies (re­view), al­though in it a lot of them turn out to just in­volve con­spir­a­tors/­ly­ing.)

    • In lock­pick­ing, copy­ing a key or re­verse-engi­neer­ing its cuts are some of the most diffi­cult ways to pick a lock. One can in­stead sim­ply use a bump key to brute-force the po­si­tions of the pins in a lock, or kick the door in, or among other door lock by­passes, wig­gle the bolt, or reach through a crack to open from the in­side, or drill the lock. (How do you know some­one has­n’t al­ready? You as­sume it’s the same lock as yes­ter­day?)

      Locks & safes have many other in­ter­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 ac­tu­ally open­ing for any com­bi­na­tion of mas­ter+or­di­nary key cuts (ie ‘mas­ter OR or­di­nary’ rather than ‘mas­ter XOR or­di­nary’), and so it is like a pass­word which one can guess one let­ter at a time.

  • In stage magic (e­spe­cially close-up/­card/­coin/pick­pock­et­ing), one be­lieves one is con­tin­u­ously see­ing sin­gle whole ob­jects which must move from one place to an­other con­tin­u­ous­ly; in re­al­i­ty, one is only see­ing, oc­ca­sion­al­ly, sur­faces of many (pos­si­bly du­pli­cate) ob­jects, which may be mov­ing only when you are not look­ing, in the op­po­site di­rec­tion, or not mov­ing at all. By hack­ing ob­ject per­ma­nence and lim­ited at­ten­tional re­sources, the stage ma­gi­cian shows the ‘im­pos­si­ble’ (Mack­nik et al 2008’s Ta­ble 1 lists folk as­sump­tions which can be hacked). Stage magic works by ex­ploit­ing our im­plicit be­liefs that no ad­ver­sary would take the trou­ble to so pre­cisely ex­ploit our heuris­tics and short­cuts.1314

  • In weird ma­chi­nes, you have a ‘pro­to­col’ like SSL or X86 ma­chine code which ap­pear 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 an­other reg­is­ter’, but in re­al­i­ty, it’s a layer over far more com­plex re­al­i­ties like proces­sor states & op­ti­miza­tions like spec­u­la­tive ex­e­cu­tion read­ing other parts of mem­ory and then quickly eras­ing it, and these can be pasted to­gether to ex­e­cute op­er­a­tions and re­veal se­crets with­out ever run­ning ‘code’ (see again Mcil­roy et al 2019).

    Sim­i­lar­ly, in find­ing hid­den ex­am­ples of Tur­ing com­plete­ness, one says, ‘this sys­tem ap­pears to be a bunch of domi­noes or what­ev­er, but ac­tu­al­ly, each one is a com­pu­ta­tional el­e­ment which has un­usual in­put­s/out­puts; I will now pro­ceed to wire a large num­ber of them to­gether to form a Tur­ing ma­chine so I can play Tetris in Con­way’s Game of Life or use heart mus­cle cells to im­ple­ment Boolean logic or run ar­bi­trary com­pu­ta­tions in a game of Mag­ic: The Gath­er­ing’.

    Or in side chan­nels, you go be­low bits and say, ‘these bits are only ap­prox­i­ma­tions to the ac­tual 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 so­cial en­gi­neer­ing/pen test­ing, peo­ple see so­cial norms and imag­i­nary things like ‘per­mis­sion’ and ‘au­thor­ity’ and ‘man­agers’ which ‘for­bid ac­cess to fa­cil­i­ties’, but in re­al­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 im­ple­ment­ing rules like ‘if lam­i­nated plas­tic, al­low in’, and if you put on a blue piece of plas­tic to your shirt and you in­cant cer­tain words at cer­tain times, you can walk right past the guards.15

  • Many fi­nan­cial or eco­nomic strate­gies have a cer­tain fla­vor of this; Al­ice Maz’s Minecraft eco­nom­ics ex­ploita­tions strongly re­minds me of ‘see­ing through’, as do many clever fi­nan­cial trades based on care­ful read­ing of con­trac­tual minu­tiae or tak­ing se­ri­ously what are usu­ally ab­stracted de­tails like ‘tak­ing de­liv­ery’ of fu­tures etc

  • and while we’re at it, why are puns so ir­re­sistible to hack­ers? (Con­sider how om­nipresent they are in Gödel, Es­cher, Bach or the Jar­gon File or text ad­ven­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 ab­stract se­man­tic level to the raw syn­tac­tic level of sub­-words or char­ac­ters, and back up again to achieve some se­man­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 hi­lar­i­ous (in the ‘vi­o­la­tion of ex­pec­ta­tions fol­lowed by un­der­stand­ing’ the­ory of hu­mor) be­cause the ab­stract sys­tem W & our ver­bal­iza­tions are so fa­mil­iar and use­ful that we quickly get trapped in our dreams of ab­strac­tions, and for­get that it is merely a map and not the ter­ri­to­ry, while in­evitably 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 an­other point which we don’t want to ex­ist.

Per­verse­ly, the more ed­u­cated you are, and the more of the map you know, the worse this effect can be, be­cause you have more to un­see. One must al­ways main­tain a cer­tain con­tempt for words & spooks.

The fool can walk right in be­cause he was too ig­no­rant to know that’s im­pos­si­ble. This is why athe­o­ret­i­cal op­ti­miza­tion processes like an­i­mals (eg cats en­gaged in fuzz test­ing) or SMT solvers or evo­lu­tion­ary AI are so dumb to be­gin with, but in the long run can be so good at sur­pris­ing us and find­ing ‘un­rea­son­able’ in­puts or re­ward hacks (anal­o­gous to the bi­as-vari­ance trade­off): be­ing un­able to un­der­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 ex­plore the ter­ri­tory di­rectly to get what they want, dis­cover new things.

To es­cape our se­man­tic il­lu­sions can re­quire a de­ter­mined effort to un­see them, and use of tech­niques to de­fa­mil­iar­ize the things. For ex­am­ple, you can’t find ty­pos in your own writ­ing with­out a great deal of effort be­cause you know what it’s sup­posed to say; so copy­edit­ing ad­vice runs like ‘read it out loud’ or ‘print it out and read it’ or ‘wait a week’ or even ‘read it up­side down’ (easier than it sound­s). That’s the sort of thing it takes to force you to read what you ac­tu­ally wrote, and not what you thought you wrote. Sim­i­lar tricks are used for learn­ing draw­ing: a face is too fa­mil­iar, so in­stead you can flip it in a mir­ror and try to copy it.

See Also

Appendix

Macknik Et Al 2008: Table 1: Psychological Assumptions

Ta­ble 1: Types of con­jur­ing effects16
Magic effects Ex­am­ples Method­olog­i­cal strate­gies
Ap­pear­ance: an ob­ject ap­pears ‘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 ap­pear where pre­vi­ously there were none)75, 94 (BOX 2; Sup­ple­men­tary in­for­ma­tion S2 (movie)); Mac King’s gi­ant rock in a shoe trick75, 87 (Sup­ple­men­tary in­for­ma­tion S3 (movie))
  • The ob­ject was al­ready there but was con­cealed (for ex­am­ple, the ma­gi­cian might con­ceal a coin in his or her hand prior to its pro­duc­tion)
  • The ob­ject was se­cretly put into po­si­tion (for ex­am­ple, in the Cups and Balls rou­tine, var­i­ous ob­jects are se­cretly loaded un­der the cups dur­ing the rou­tine)
  • The ob­ject is not there but seems to be (for ex­am­ple, a ‘medium’ can sim­u­late the pres­ence of a spirit at a seance by se­cretly touch­ing a spec­ta­tor)
Van­ish: an ob­ject dis­ap­pears ‘as if by magic’ Van­ish­ing of a coin; Penn and Teller’s un­der­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 ob­ject was not re­ally where it ap­peared to be to be­gin with (for ex­am­ple, the ma­gi­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 ob­ject has been se­cretly re­moved (for ex­am­ple, the ma­gi­cian uses a se­cret de­vice, called a gim­mick, to pull an ob­ject into his sleeve)
  • The ob­ject is still there but is con­cealed (a coin can seem to van­ish from the ma­gi­cian’s hand al­though in re­al­ity it is merely con­cealed)
Trans­po­si­tion: an ob­ject changes po­si­tion in space from po­si­tion A to po­si­tion B Hou­dini’s Meta­mor­pho­sis (in which two peo­ple change places be­tween locked box­es); Penn and Teller’s Hang­ing Man trick (in which Penn is ap­par­ently hanged to death, only to be found safe and sound in the au­di­ence)
  • The ob­ject seemed to be at A, but ac­tu­ally was al­ready at B (for ex­am­ple, the ma­gi­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 ob­ject is still at A but seems to be at B (for ex­am­ple, the ma­gi­cian fakes a coin trans­fer from the left hand to the right and then, when re­veal­ing the coin by drop­ping it, uses sleight of hand to give the im­pres­sion that it was dropped from the right hand)
  • The ob­ject was se­cretly moved from A to B (for ex­am­ple, a coin in the left hand is se­cretly trans­ferred to the right hand and then is re­vealed there)
  • A du­pli­cate ob­ject is used (for ex­am­ple, both hands hold iden­ti­cal coins that are re­vealed at differ­ent times to sim­u­late a trans­fer)
Restora­tion: an ob­ject is dam­aged and then re­stored to its orig­i­nal con­di­tion. Cut­ting and restor­ing a rope; saw­ing an as­sis­tant in half; tear­ing and restor­ing a news­pa­per; break­ing and restor­ing rub­ber bands
  • The ob­ject was not re­ally dam­aged
  • The ob­ject was not re­ally re­stored
  • A du­pli­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 un­link mag­i­cal­ly); Hou­dini’s Walk­ing Through A Wall trick; Coins Through The Ta­ble
  • 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 ob­ject 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 ob­ject A com­bined with the ap­pear­ance of ob­ject B:

  • Ob­ject A was se­cretly switched with ob­ject B
  • Ob­ject B was al­ways present but was ini­tially dis­guised as ob­ject A
  • Ob­ject A is dis­guised as ob­ject B at the point of ‘trans­for­ma­tion’
Ex­tra­or­di­nary feats (in­clud­ing men­tal and phys­i­cal feats) Ex­tra­or­di­nary mem­ory (re­mem­ber­ing the names of all the au­di­ence mem­ber­s); ex­tra­or­di­nary cal­cu­la­tion (re­port­ing the re­sult of mul­ti­ply­ing ran­domly se­lected 4-digit num­ber­s); ex­tra­or­di­nary strength; in­vul­ner­a­bil­ity (spe­cific ex­am­ples: walk­ing on hot coals; Penn and Teller’s bul­let-catch­ing trick)
  • Might rely on rel­a­tively ob­scure sci­en­tific knowl­edge (such as math­e­mat­i­cal or phys­i­o­log­i­cal knowl­edge). For ex­am­ple, walk­ing on hot coals is harm­less when per­formed cor­rectly
Telekine­sis: ‘mag­i­cal’ lev­i­ta­tion or an­i­ma­tion of an ob­ject Lev­i­ta­tion; spoon bend­ing
  • The ac­tion is caused by an ex­ter­nal force (for ex­am­ple, an in­vis­i­ble thread)
  • The ac­tion is caused by an in­ter­nal force (e­las­tic­i­ty, chem­i­cal re­ac­tion, mag­net­ism, etc.)
  • The ac­tion did not ac­tu­ally oc­cur (for ex­am­ple, a spoon ben­der can con­vince a spec­ta­tor that a sta­tion­ary spoon is still bend­ing)
Ex­trasen­sory per­cep­tion (ESP; in­clud­ing clair­voy­ance, telepa­thy, pre­cog­ni­tion, men­tal con­trol, etc.) Clair­voy­ance (ac­quir­ing in­for­ma­tion that is not known to oth­ers through ESP); telepa­thy (ac­quir­ing in­for­ma­tion that is known to oth­ers through ESP); pre­cog­ni­tion (ac­quir­ing in­for­ma­tion from the fu­ture); men­tal con­trol (the per­former in­flu­ences the se­lec­tion process of an­other per­son)
  • Con­trol­ling a spec­ta­tor’s choices to give the il­lu­sion of free will
  • Dis­cov­er­ing hid­den in­for­ma­tion (for ex­am­ple, read­ing in­for­ma­tion that has been sealed in an en­velope, fish­ing for or pump­ing in­for­ma­tion from a spec­ta­tor, cold read­ing, etc.)
  • Re­veal­ing ap­par­ent proof that in­for­ma­tion an­nounced by the spec­ta­tor was pre­vi­ously known by the ma­gi­cian (for ex­am­ple, by writ­ing the an­nounce­ment on pa­per and us­ing sleight of hand to make the pa­per seem to come out of an en­ve­lope that was sealed be­fore the an­nounce­ment)

How many computers are in your computer?

Why are there so many places for back­doors and weird ma­chines in your “com­puter”? Be­cause your com­puter is in fact scores or hun­dreds, per­haps even thou­sands, of com­puter chips, many of which host weird ma­chines and are ex­plic­itly or im­plic­itly ca­pa­ble of Tur­ing-com­plete com­pu­ta­tions (many more pow­er­ful than desk­tops of by­gone eras), work­ing to­gether to cre­ate the il­lu­sion of a sin­gle com­put­er. Back­doors, bugs, weird ma­chi­nes, and se­cu­rity do not care about what you think—only where re­sources can be found and or­ches­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 Al­tair PC re­ally 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 im­por­tant are the in­puts and out­puts: how ca­pa­ble is the sys­tem as a whole and what re­sources does it re­quire and how can the com­po­nents be re­pro­grammed?

No one cares if Google is im­ple­mented us­ing 50 su­per­com­put­ers, 50,000 main­frames, 5 mil­lion servers, or 50 mil­lion em­bed­ded/­mo­bile proces­sors, or a mix of any of the above ex­ploit­ing a wide va­ri­ety of chips from cus­tom “ten­sor pro­cess­ing units” to cus­tom on-die sil­i­con (im­ple­mented by In­tel on Xeon chips for a num­ber of its biggest cus­tomers) to FPGAs to GPUs to CPUs to still more ex­otic 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 de­liver its ser­vices at a rea­son­able cost. (A “su­per­com­puter” these days mostly looks like a large num­ber of rack­-mounted servers with un­usual num­bers of GPUs & con­nected by un­usu­ally high­-speed In­fini­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 ma­chines on many differ­ent lev­els of com­pu­ta­tion de­pend­ing on their in­ter­nal dy­nam­ics & con­nec­tiv­i­ty. The sys­tem can be seen on many lev­els, each equally in­valid but use­ful for differ­ent pur­pos­es. Are you a ‘sin­gle bi­o­log­i­cal in­tel­li­gence’ or a com­mu­ni­ty/e­cosys­tem of hu­man cell­s/neu­ron­s/bac­te­ri­a/yeast­/virus­es/­par­a­sites? And does it mat­ter in the slight­est bit to any­one you might wrong?

XKCD #2166, “Stack”

Here is an ex­am­ple of the il­l-de­fined na­ture 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 oc­cu­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 be­yond just the CPU/GPU, for a va­ri­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 re­al­time or higher per­for­mance, for se­cu­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 ar­chi­tec­ture or ex­ist­ing soft­ware pack­age, be­cause a DSP or core can be pro­grammed faster than a more spe­cial­ized ASIC can be cre­at­ed, or be­cause it was the quick­est pos­si­ble so­lu­tion to slap down a small CPU and they could­n’t be both­ered to shave some pen­nies17… (Hal­var Flake dubs this phe­nom­e­non “cheap com­plex­ity”.) When­ever a pe­riph­eral or de­vice is made, the Wheel of Rein­car­na­tion be­gins to turn. Fur­ther, many of these com­po­nents can be used as com­pu­ta­tional el­e­ments even if they were not in­tended to be or try to hide that func­tion­al­i­ty. (For ex­am­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 de­feat­ing copy­-pro­tec­tion schemes, be­cause 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 an­i­mat­ing demos, com­puter chess…)

Thus:

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

    • Each of the >2 CPU cores can run in­de­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’ en­tire RAM a few decades ago18, and likely phys­i­cally big­ger than their CPUs were to boot), and must be re­garded as in­di­vid­u­als. Fur­ther, the CPU as a whole is re­pro­gram­ma­ble through mi­croc­o­de, such as to work around er­rors in the chip de­sign, so what those CPUs com­pute changes.

    • CPUs sport in­creas­ingly opaque fea­tures, such as the man­age­ment en­gi­nes/se­cure en­claves, like the In­tel Man­age­ment En­gine (with a JVM for pro­gram­ma­bil­ity; Ruan 2014 & SGX), or AMD’s Plat­form Se­cu­rity Proces­sor (PSP) or An­droid’s TEEs or Ti­tan chips; these hard­ware mod­ules typ­i­cally are full com­put­ers in their own right, run­ning in­de­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”). In­tel’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 se­cu­rity im­pli­ca­tions con­cerned Google enough to launch a project to re­move MINIX from its CPUs & its Ti­tan chip to cryp­to­graph­i­cally ver­ify firmware on boot.

      • any float­ing-point unit may be Tur­ing-com­plete through en­cod­ing into float­ing-point op­er­a­tions in the spirit of FRACTRAN19
      • the MMU can be pro­grammed into a page-fault weird ma­chine 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 al­low some­thing like Wang tiles), but for ex­am­ple Ap­ple’s A9 mo­bile sys­tem-on-a-chip goes far be­yond sim­ply a du­al-core ARM CPU and GPU as like Intel/AMD desk­top CPUs, it in­cludes the se­cure en­clave (a phys­i­cally sep­a­rate ded­i­cated CPU core), but it also in­cludes an im­age co-proces­sor, a mo­tion/voice-recog­ni­tion co­proces­sor (par­tially to sup­port Sir­i), and ap­par­ently a few other cores. These ASICs are some­times there to sup­port AI tasks, and pre­sum­ably spe­cial­ize in ma­trix mul­ti­pli­ca­tions for neural net­works; as re­cur­rent neural net­works are Tur­ing-com­plete… Other com­pa­nies have rushed to ex­pand their sys­tem-on-chips as well, like Mo­torola or Qual­comm

    • Mark Er­molov 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 ar­chi­tec­tures all rep­re­sent­ed:

      It’s amaz­ing how many het­ero­ge­neous CPU cores were in­te­grated in In­tel Sil­ver­mon­t’s Moore­field SoC (ANN): x86, ARC, LMT, 8051, Au­dio DSP, each run­ning own firmware and sup­port­ing JTAG in­ter­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 au­then­ti­ca­tion on a Ap­ple T1/T2 SoC (us­ing an ARM CPU) in­de­pen­dent of the lap­top OS, which can, of course, be hacked to run Linux

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

    These man­age­ment or de­bug­ging chips may be ‘ac­ci­den­tally’ left en­abled on ship­ping de­vices, like the Via C3 CPUs’s em­bed­ded ARM CPUs.

  • GPUs have >100s of sim­ple GPU cores, which can run neural net­works well (which are highly ex­pres­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 ad­di­tion to all the other units men­tioned, there is an in­de­pen­dent base­band proces­sor run­ning a pro­pri­etary re­al­time OS for han­dling ra­dio 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 us­ing some­thing like L4. Base­band proces­sors have been found with back­doors, in ad­di­tion to all their vul­ner­a­bil­i­ties.

    Given ARM CPUs are used in most of these em­bed­ded ap­pli­ca­tions, it’s no sur­prise ARM likes to boast that “a mod­ern smart­phone will con­tain some­where be­tween 8 and 14 ARM proces­sors, one of which will be the ap­pli­ca­tion proces­sor (run­ning An­droid or iOS or what­ev­er), while an­other 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 in­for­ma­tion, as they are smart cards which can in­de­pen­dently run Java Card ap­pli­ca­tions (ap­par­ently NFC chips may also be like this as well), some­what like the JVM in the In­tel Man­age­ment En­gine. 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 op­er­at­ing sys­tem or ac­cel­er­at­ing disk en­cryp­tion or do­ing wear lev­el­ing; these can be hacked.

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

  • USB/Thunderbolt ca­bles/de­vices, or moth­er­board­-at­tached de­vices: an em­bed­ded proces­sor on de­vice is needed for ne­go­ti­a­tion of data/power pro­to­cols at the least for ca­bles/­bat­ter­ies/charg­ers21, and may be even more heavy duty with mul­ti­ple ad­di­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 di­rectly sub­vert­ing the host via DMA by in­-be­tween IOMMU units, but the devil is in the de­tails…

  • 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 go­ing back to smart tele­types)

  • …

So a desk­top or smart­phone can rea­son­ably be ex­pected to have any­where from 15 to sev­eral thou­sand “com­put­ers” (in the sense of a Tur­ing-com­plete de­vice 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 ex­ploited by an ad­ver­sary for sur­veil­lance, ex­fil­tra­tion, or at­tacks against the rest of the sys­tem.

None of this is un­usual 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 do­ing batch pro­cess­ing while ad­di­tional smaller com­put­ers took care of high­-speed I/O op­er­a­tions that would oth­er­wise choke the main com­put­ers with in­ter­rupts.

In prac­tice, aside from the com­puter se­cu­rity com­mu­nity (as all these com­put­ers are in­se­cure and thus use­ful at­tack routes), users don’t care that our com­put­ers, un­der the hood, are in­sanely com­plex and more ac­cu­rately seen as a mot­ley menagerie of hun­dreds of com­put­ers awk­wardly yoked to­geth­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.

Un­til it stops work­ing as ex­pect­ed.

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

  2. Dwarf Fortress pro­vides clock­work mech­a­nisms, so TC is un­sur­pris­ing; but the wa­ter is im­ple­mented as a sim­ple cel­lu­lar au­toma­tion, so there might be more ways of get­ting TC in DF! The DF wiki cur­rently lists 4 po­ten­tial ways of cre­at­ing logic gates: the flu­ids, the clock­work mech­a­nisms, mine-carts, and crea­ture/an­i­mal logic gates in­volv­ing doors+­pres­sure-sen­sors.↩︎

  3. The full PDF spec­i­fi­ca­tion is no­to­ri­ously bloat­ed. For ex­am­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 in­cludes its own weird sub­set of JavaScrip­t). The Adobe PDF viewer in­cludes 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 im­ple­mented us­ing domino logic.↩︎

  5. Ear­lier ver­sions re­quired play­ers to take all pos­si­ble ac­tions, but the 2019 pa­per claims to re­move this as­sump­tion and force all ac­tions, ren­der­ing the con­struc­tion fully me­chan­i­cal.↩︎

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

  7. “48. The best book on pro­gram­ming for the lay­man is Al­ice in Won­der­land; but that’s be­cause 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 is­n’t. This is a spe­cific pat­tern of re­duc­tion­ism, and many in­stances of ‘think­ing out­side the box’ are other pat­terns, like putting on an­other lay­er, or elim­i­nat­ing the sys­tems in ques­tion en­tire­ly.↩︎

  9. Feyn­man:

    The phe­nom­e­non of ac­cept­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 ex­cel­lent ex­am­ple. There are sev­eral ref­er­ences to pre­vi­ous flights; the ac­cep­tance and suc­cess of these flights are taken as ev­i­dence of safe­ty. But ero­sion and blowby are not what the de­sign ex­pect­ed. They are warn­ings that some­thing is wrong. The equip­ment is not op­er­at­ing as ex­pect­ed, and there­fore there is a dan­ger that it can op­er­ate with even wider de­vi­a­tions in the un­ex­pected and not thor­oughly un­der­stood way. The fact that this dan­ger did not lead to cat­a­stro­phe be­fore is no guar­an­tee that it will not the next time, un­less it is com­pletely un­der­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 un­der­stood. They did not oc­cur equally on all flights and all joints; some­times more, and some­times less. Why not some­time, when what­ever con­di­tions de­ter­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 be­haved as if they un­der­stood it, giv­ing ap­par­ently log­i­cal ar­gu­ments to each other often de­pend­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 ex­am­ple from En­der’s Game is worth not­ing: if vic­tory in Bat­tle School is de­fined by 4 sol­diers at the cor­ner of the en­emy gate & some­one pass­ing through, then why not—shades of Eu­risko—skip fight­ing en­tirely & go straight for the gate?↩︎

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

    Schatz’s ex­hor­ta­tion to play­ers to move against the ar­chi­tec­ture, not with it, to un­cover a scene’s pos­si­ble crimes, is use­ful not only in the world of games. Ig­nor­ing the paths laid out by ar­chi­tects and even re­mak­ing a space from within are some of the most fun­da­men­tal ways in which bur­glars mis­use the built en­vi­ron­men­t…In one of the most in­ter­est­ing mo­ments in Bill Ma­son’s mem­oir, he sees that ar­chi­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 ex­plains that his in­tended prize was locked in­side a room whose door was too closely guarded for him to slip through. Then he re­al­izes the ob­vi­ous: he has been think­ing the way the ho­tel wanted him to think—the way the ar­chi­tects had hoped he would be­have—look­ing for doors and hall­ways when he could sim­ply carve a new route where he wanted it. The en­su­ing re­al­iza­tion de­lights him. “Elated at the idea that I could cut my own door right where I needed one,” he writes, Ma­son sim­ply breaks into the ho­tel suite ad­ja­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 us­ing 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 ar­chi­tec­tural surgery, pure and sim­ple.

    Lat­er, Ma­son ac­tu­ally mocks the idea that a per­son would re­main re­liant on doors, mak­ing fun of any­one who thinks bur­glars, in par­tic­u­lar, would re­spect the lim­i­ta­tions of ar­chi­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 re­spectable peo­ple would, through the door pro­vided for the pur­pose. Maybe that ex­plains 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 ar­chi­tec­ture, spa­tial cap­tives in a world some­one else has de­signed for them.

    Some­thing about this is al­most un­set­tlingly bril­liant, as if it is non­bur­glars who have been mis­us­ing the built en­vi­ron­ment this whole time; as if it is non­bur­glars who have been un­will­ing to ques­tion the world’s most ba­sic spa­tial as­sump­tions, too scared to think past the tyranny of ar­chi­tec­ture’s long-held be­hav­ioral ex­pec­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 it­self is often more like tis­sue pa­per, 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 ma­gi­cian Teller, of Penn & Teller, puts this well in in­ter­views: what makes stage magic work is hard work. Teller, “Teller Re­veals His Se­crets: The small­er, qui­eter half of the ma­gi­cian duo Penn & Teller writes about how ma­gi­cians ma­nip­u­late the hu­man mind” 2012

    I think you’ll see what I mean if I teach you a few prin­ci­ples ma­gi­cians em­ploy when they want to al­ter your per­cep­tion­s…­Make the se­cret a lot more trou­ble than the trick seems worth. You will be fooled by a trick if it in­volves more time, money and prac­tice than you (or any other sane on­look­er) would be will­ing to in­vest. 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 en­to­mol­o­gist who pro­vided slow-mov­ing, cam­er­a-friendly cock­roaches (the kind from un­der 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 se­cret com­part­ment out of foam-core (one of the few ma­te­ri­als cock­roaches can’t cling to) and worked out a de­vi­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 ma­gi­cians.

    Or in his Hutt­son 2015 in­ter­view:

    Matt: “So why don’t you ex­plain all your tricks?”

    Teller: “Be­cause the short ex­pla­na­tion—the ex­pla­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 se­cret to mak­ing a de­cep­tive piece of magic is you do it by the ugli­est pos­si­ble means. It’s com­plex, it’s un­ro­man­tic, it’s un­clever. Be­cause there are no big se­crets. There is no safe full of magic se­crets some­where. Jim Stein­meyer said he thinks most of the pub­lic be­lieves there’s a big safe that con­tains all the magic se­crets. The biggest job for a ma­gi­cian, he says, is to con­ceal the fact that that safe is emp­ty. Be­cause every magic se­cret is just a mi­nor mod­i­fi­ca­tion of some­thing that you fully un­der­stand in every­day life. Take sus­pend­ing some­thing with a thread, for ex­am­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 ma­gi­cian’s us­ing 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 ob­scure se­cret in that. You learned that play­ing in your grand­moth­er’s sewing box. Every magic ‘se­cret’ is hid­ing in plain sight in the every­day world. It’s not news, and em­i­nently drab.”

    ↩︎

  14. Hou­dini’s trick of Sir Arthur Co­nan Doyle ex­em­pli­fies these strate­gies. No one would ex­pect 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 as­sis­tant with­out Doyle notic­ing, or the as­sis­tant to ma­nip­u­late a mag­netic pole be­hind a small sus­pended slate board, hid­ing it in the view­ers’ pre­cise blind spot in or­der to make it ap­pear as if the chalk were hov­er­ing in mid-air & writ­ing by it­self. Doyle did not, and dis­be­lieved Hou­dini’s state­ment it was merely a trick. But Doyle should have re­mem­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!

    Ol­son & Raz 2020 give fur­ther ex­am­ples, and demon­strate how this can be use­ful for run­ning psy­chol­ogy ex­per­i­ments.↩︎

  15. Speak­ing of ‘so­cial en­gi­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 su­per­fi­cial so­cial net­work­ing so sur­pris­ing to so many? Per­haps its suc­cess is a hint that the un­der­ly­ing logic of so­cial in­ter­ac­tions are much more ab­stractable than, and not as rich & sub­tle as, we’d pre­fer to think.↩︎

  16. We adopt La­m­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 ex­am­ple of this kind of men­tal­ity is noted by pkaye on HN

    Re­minds of when I was do­ing firmware de­vel­op­ment and the ASIC team would ask if they could toss in a ex­tra Cor­tex-M3 core to solve spe­cific con­trol prob­lems. Those cores would be used as pro­gram­ma­ble state ma­chines. For the ASIC team toss­ing in a ex­tra core was free com­pared to cus­tom logic de­sign. How­ever for the firmware team it would be an­other job to write and test that firmware. We had de­signs with up­wards of 10 Cor­tex-M3 cores. I’ve heard from a friend at an­other em­ployer had some­thing like 32 such cores and it was a pain to de­bug.

    ↩︎

  18. Eg a 2017 In­tel Core i9-7900X CPU has ~24MB cache to­tal, 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 ap­par­ently harm­less FP op­er­a­tions which still en­code a (deep) NN by ex­ploit­ing FP set­tings en­abling non­lin­ear­i­ties. See also “Ad­ver­sar­ial Re­pro­gram­ming of Neural Net­works”, El­sayed et al 2018 & Neekhara et al 2018. A re­lated topic is “ma­chine teach­ing”: Zhu 2013, Zhu 2015, Wang et al 2018, Su­cholut­sky & Schon­lau 2020.↩︎

  20. Ar­rigo Tri­ulzi in 2008 de­moed an ex­ploit sys­tem which com­bined a hack of the (com­pu­ta­tion­ally lim­it­ed) NIC and GPU to run in­de­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 un­ex­pected com­po­nent is a tiny cir­cuit board with a mi­cro­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 en­ables 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 In­stru­ments MSP430 mi­cro­con­troller, roughly as pow­er­ful as the proces­sor in­side the orig­i­nal Mac­in­tosh. [The proces­sor in the charger is a MSP430F2003 ul­tra low power mi­cro­con­troller with 1kB of flash and just 128 bytes of RAM. It in­cludes a high­-pre­ci­sion 16-bit ana­log to dig­i­tal con­vert­er. More in­for­ma­tion is here.]”↩︎