{"id":1902,"date":"2014-07-04T10:16:46","date_gmt":"2014-07-04T14:16:46","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1902"},"modified":"2016-12-10T04:37:32","modified_gmt":"2016-12-10T09:37:32","slug":"the-power-of-the-digi-comp-ii-my-first-conscious-paperlet","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1902","title":{"rendered":"The Power of the Digi-Comp II: My First Conscious Paperlet"},"content":{"rendered":"

Foreword:<\/strong> Right now, I have a painfully-large stack of unwritten research papers. \u00a0Many of these are “paperlets”: cool things I noticed\u00a0that I want\u00a0to tell people\u00a0about, but\u00a0that would require a lot more development before they became\u00a0competitive for any major\u00a0theoretical computer science conference. \u00a0And what with the baby, I simply don’t have time anymore for the kind of obsessive, single-minded, all-nighter-filled effort needed to bulk\u00a0my paperlets up. \u00a0So starting today, I’m going to try turning some of my paperlets into blog posts. \u00a0I don’t mean advertisements or sneak previews for papers, but replacements<\/strong> for papers: blog posts that constitute the entirety of what I have\u00a0to say for now about some research topic. \u00a0“Peer reviewing” (whether signed or\u00a0anonymous) can take place in the comments section, and “citation” can be done by URL. \u00a0The hope is that, much like with 17th<\/sup>-century scientists who communicated results by letter, this will make it easier to get my\u00a0paperlets done: after all, I’m not writing Official Papers, just blogging for\u00a0colleagues and\u00a0friends.<\/em><\/p>\n

Of course, I’ve often basically\u00a0done this before—as have many other academic bloggers—but now I’m going to go about it more consciously. \u00a0I’ve thought\u00a0for years\u00a0that the Internet would\u00a0eventually change the norms of scientific\u00a0publication much\u00a0more radically than it so far has: that yes, instant-feedback tools like blogs and StackExchange and MathOverflow\u00a0might have another decade or two at the periphery of progress, but their eventual destiny is at the center. \u00a0And now that I have tenure, it hit\u00a0me that I can do more than prognosticate about such things. \u00a0I’ll start small: I won’t go direct-to-blog\u00a0for big papers, papers that cry out for\u00a0LaTeX formatting, or joint papers. \u00a0I\u00a0certainly won’t do it\u00a0for papers\u00a0with students who need official publications for their professional advancement. \u00a0But for things like today’s post—on the power of a wooden mechanical computer now installed in the lobby of the building\u00a0where I work—I hope you agree that the Science-by-Blog Plan fits well.<\/em><\/p>\n

Oh, by the way, happy July 4th<\/sup> to American readers! \u00a0I hope you find that a paperlet about the logspace-interreducibility of a few\u00a0not-very-well-known computational models captures everything that the holiday is about.<\/em><\/p>\n

\n

The Power of the Digi-Comp II<\/strong><\/h2>\n

by Scott Aaronson<\/p>\n

Abstract<\/strong><\/h3>\n

I study the Digi-Comp II, a wooden mechanical computer whose only moving parts are balls, switches, and toggles. \u00a0I show that the problem of simulating (a natural abstraction of) the Digi-Comp, with a polynomial number of balls, is complete for CC<\/strong><\/a> (Comparator Circuit), a complexity class defined by Subramanian in 1990 that sits between NL<\/strong> and P<\/strong>. \u00a0This explains why the Digi-Comp is capable of addition, multiplication, division, and other arithmetical tasks, and also\u00a0implies new tasks of which the Digi-Comp is\u00a0capable (and that indeed are complete for it), including the Stable Marriage Problem, finding a lexicographically-first perfect matching, and the\u00a0simulation of other Digi-Comps. \u00a0However, it also suggests that the Digi-Comp is not<\/em> a universal computer (not even in the circuit sense), making it a very interesting way to fall short of Turing-universality. \u00a0I observe that even with an exponential number of balls, simulating the Digi-Comp remains in P<\/strong>, but I leave open the problem of pinning down its complexity more precisely.<\/p>\n

Introduction<\/strong><\/h3>\n

To celebrate\u00a0his 60th<\/sup> birthday, my colleague Charles Leiserson<\/a>\u00a0(who some of you might know as the “L” in the CLRS<\/a>\u00a0algorithms textbook) had a striking contraption installed in the lobby of the MIT Stata Center. \u00a0That contraption, pictured below,\u00a0is a custom-built, supersized version of a wooden mechanical computer from the 1960s called the Digi-Comp II<\/a>, now manufactured and sold by a company called Evil Mad Scientist<\/a>.<\/p>\n

\"\"<\/p>\n

Click here<\/a> for a short video showing the Digi-Comp’s operation (and here<\/a> for the user’s manual). \u00a0Basically, the way it works is this: a bunch of balls (little steel balls in the original version, pool balls in the supersized version) start at the top and roll to the bottom, one by one. \u00a0On their way down, the balls may encounter black toggles, which route each incoming ball either left or right. \u00a0Whenever this happens, the weight of the ball flips the toggle\u00a0to the opposite setting: so for example, if a ball goes\u00a0left, then the next ball to encounter the same toggle\u00a0will go right, and the ball after that will go left, and so on. \u00a0The toggles thus\u00a0maintain a “state” for the computer, with each toggle\u00a0storing one bit.<\/p>\n

Besides the toggles, there are\u00a0also “switches,” which the user can set at the beginning to route every incoming ball either left or right, and whose settings aren’t changed by the balls. \u00a0And then there are various wooden tunnels and ledges, whose function is simply to direct the balls in a desired way as they roll down. \u00a0A ball could reach different locations,\u00a0or even the same\u00a0location in different\u00a0ways, depending on the settings of the toggles and switches\u00a0above that location. \u00a0On the other hand, once we fix\u00a0the toggles and switches, a ball’s motion\u00a0is completely determined: there’s no random or chaotic element.<\/p>\n

“Programming” is done by configuring the toggles and switches\u00a0in some desired\u00a0way, then loading a desired number of balls at the top and letting them go. \u00a0“Reading the output” can be done by looking at the final configuration of some subset of the toggles.<\/p>\n

Whenever a ball reaches the bottom, it hits a lever\u00a0that causes\u00a0the next ball to be released from the top. \u00a0This ensures that the balls go through the device one at a time, rather than all at once. \u00a0As we’ll see, however, this is mainly\u00a0for aesthetic reasons, and maybe also for the mechanical reason that the toggles wouldn’t work properly if two or more\u00a0balls hit them at once. \u00a0The actual logic of the machine doesn’t care about the\u00a0timing<\/em> of the balls; the sheer number<\/em> of balls that go through is all\u00a0that matters.<\/p>\n

The Digi-Comp II, as sold, contains a few other features:\u00a0most notably, toggles that can be controlled by other toggles (or switches). \u00a0But I’ll defer discussion of that feature to later. \u00a0As we’ll see, we already get a quite interesting model of computation without it.<\/p>\n

One final note: of course the machine that’s sold has a fixed size and a fixed geometry. \u00a0But for theoretical purposes, it’s much more interesting to consider an arbitrary<\/em> network of toggles and switches (not necessarily even planar!), with arbitrary size, and with an arbitrary number of balls fed into it. \u00a0(I’ll give a more formal definition in the next section.)<\/p>\n

The Power of the Digi-Comp<\/strong><\/h3>\n

So, what exactly can the Digi-Comp do<\/em>? \u00a0As a first exercise, you should\u00a0convince yourself that, by simply putting a bunch of toggles in a line and initializing them all to “L” (that is, Left), it’s easy to set up\u00a0a binary counter<\/em>. \u00a0In other words, starting from\u00a0the configuration, say, LLL (in which three toggles all point left), as successive balls pass through we can enter the\u00a0configurations RLL, LRL, RRL, etc. \u00a0If we interpret L as 0 and R as 1, and treat the first bit as the least significant, then we’re simply counting from 0 to 7 in binary. \u00a0With 20 toggles, we could instead count to 1,048,575.<\/p>\n

\"counter\"<\/a><\/p>\n

But counting is not the most interesting\u00a0thing we can do. \u00a0As Charles eagerly demonstrated to me, we can also set up the Digi-Comp to perform binary addition, binary multiplication, sorting, and even long division. \u00a0(Excruciatingly<\/em> slowly<\/em>, of course: the Digi-Comp might need even more work\u00a0to multiply 3\u00d75, than existing quantum computers need\u00a0to factor the result!)<\/p>\n

To me, these demonstrations served only as proof that, while Charles might call<\/em> himself a theoretical computer scientist, he’s really a practical person at heart. \u00a0Why? \u00a0Because a theorist would know that the real question is not what the Digi-Comp can do, but rather what it can’t<\/em> do! \u00a0In particular, do we have a universal computer on our hands here, or not?<\/p>\n

If the answer is\u00a0yes, then it’s amazing that such a simple contraption of balls and toggles could already take\u00a0us over the threshold of universality. \u00a0Universality would immediately explain why<\/em> the Digi-Comp is capable of multiplication, division, sorting, and so on. \u00a0If, on the other hand, we don’t have universality, that too is extremely interesting—for we’d then face the challenge of explaining how the Digi-Comp can do so\u00a0many things without<\/em> being universal.<\/p>\n

It might be said\u00a0that the Digi-Comp is certainly<\/em>\u00a0not a universal computer, since if nothing else, it’s incapable of infinite loops. \u00a0Indeed, the number of steps that a given Digi-Comp can execute\u00a0is bounded by\u00a0the number of balls, while the number of bits it can store is bounded by\u00a0the number of toggles: clearly we don’t have a Turing machine. \u00a0This is true, but doesn’t really\u00a0tell us what we want to know. \u00a0For, as discussed\u00a0in my last post<\/a>, we can consider not only\u00a0Turing-machine universality, but also\u00a0the weaker (but still interesting) notion of circuit-universality<\/em>. \u00a0The latter means the ability to simulate, with reasonable efficiency, any Boolean circuit of AND, OR, and NOT gates—and hence, in particular, to\u00a0compute any Boolean function on any fixed number of input bits (given enough resources), or to simulate any polynomial-time Turing machine (given polynomial resources).<\/p>\n

The formal way to ask whether something is circuit-universal, is to ask whether the problem of simulating the thing is P<\/strong>-complete<\/a>. \u00a0Here P<\/strong>-complete (not to be confused with NP<\/strong>-complete!) basically means the following:<\/p>\n

There exists a polynomial p such that any S-step Turing machine computation—or equivalently, any Boolean circuit with at most S gates—can be embedded\u00a0into our system if we allow the use of poly(S) computing elements (in our case, balls, toggles, and switches).<\/em><\/p>\n

Of course, I need to tell you what I mean by the weasel phrase “can be embedded into.” \u00a0After all,\u00a0it wouldn’t be too\u00a0impressive\u00a0if the Digi-Comp could “solve” linear programming, primality testing, or other highly-nontrivial problems, but only via “embeddings” in which we<\/em> had to do essentially all the work, just to decide how to configure the toggles and switches! \u00a0The standard way to handle this issue\u00a0is to demand that the embedding be “computationally simple”: that is, we should be able to carry out the embedding in L<\/strong><\/a> (logarithmic space), or some other complexity class believed to be much smaller than the class (P<\/strong>, in this case) for which we’re trying to prove completeness. \u00a0That way, we’ll be able to say that our\u00a0device really was<\/em> “doing something essential”—i.e., something that our\u00a0embedding procedure couldn’t efficiently do for itself—unless<\/em> the larger complexity class collapses with the smaller one (i.e., unless L<\/strong>=P<\/strong>).<\/p>\n

So then, our question is whether simulating the Digi-Comp II is a\u00a0P<\/strong>-complete problem under L<\/strong>-reductions, or alternatively, whether the problem is in some complexity class believed to be smaller than P<\/strong>. \u00a0The one last thing we need is a formal definition of “the problem of simulating the Digi-Comp II.” \u00a0Thus, let DIGICOMP be the following problem:<\/p>\n

We’re given as inputs:<\/p>\n