Follow the Bouncing Ball: An Over-Literal Interpretation of ‘Mechanized Logic’

Developing your own intuitions is an underappreciated but absolutely essential part of understanding mathematics, computing, or science. In general, more concrete intuitions are also more useful intuitions, as the human mind has a better-developed set of tools for reasoning about familiar objects. (And perhaps this observation constitutes a definition of ‘familiarity’.) While it’s important to develop new intuitions about unfamiliar and sometimes surprising objects (this being a good argument for mathematics taking a place alongside literacy as a pillar of education), straightforward analogy to familiar phenomena can illuminate even the most dense and obscure of abstractions.

I’ve been preoccupied with work elsewhere for a while, and so I’d like to get back into the rhythm of writing here by dusting off an old analogical device that I cooked up a couple of years ago for trying to understand the relationship between formal logic and other branches of mathematics. The degree to which the device succeeds at this aim is questionable, but I think the device itself is interesting, if for no other reason that it brings such a strong spatial-mechanical flavor to such a highly abstract system. This spatial-mechanical flavor may even illuminate some surprising relationships. Whether or this revelation is actually useful, or just amusing isn’t clear, but after all, when does it ever hurt to take a new perspective?

So let’s begin.

One of the most basic constructions of formal logic is the truth table. Truth tables characterize logical predicates as a straightforward tabulation of some number of boolean variables. Formally, a truth table on N variables is a tabular representation of all the values of a function P : {0, 1}^N -> {0, 1}. (Throughout this presentation, P indicates some predicate on N boolean variables.) Informally, a truth table is nothing more than a table that characterizes which of some number of possible things have some property, and which don’t.

Suppose then that we have respective values v[i] for some collection of boolean variables x[i] and we want to determine whether P is true or false under these conditions. (That is, x[i] |-> v[i].) One procedure for determining the truth or falsity of P under these conditions would be to look up the entry v[1] … v[N] in the truth table for P. There are a number of ways this look-up could be structured, however. The most obvious involves a flat ordering of the rows, so that each is scanned exactly once until the sought-after row is reached. This is kind of dull, and moreover requires N look-ups in the worst case. A better organization (read: data representation) would be to arrange the values of P as leaf-nodes in a binary tree, denoted T, where each tier of nodes corresponds to one of the x[i]. By convention, assume that the [i]th tier, counting from top to bottom, corresponds to variable x[i], and that left and right branches from a node correspond to values of 0 and 1 respectively. There is now a one-to-one correspondence between possible combinations of v[i] and paths from the root node of T to the leaf nodes of T. Checking the v[i] one at a time, taking the left branch if v[i] = 0 and the right branch if instead v[i] = 1, a determination of the value of P will take no more comparisons than the height of T, which happens to be log_2(N).

Well, none of this is terribly surprising. What I’ve described above would be completely unremarkable if implemented on a digital computer, and would not even be the most efficient approach for many kinds of problems. Suppose, however, that we wanted to implement the computation of P as a mechanical artifact. While the implementation details would require heroic feats of material craftsmanship, the metaphorical descent of the index [i] through the tree could be implemented as a ball (which I’ll also call [i]) descending very literally under the force of gravity through a series of left-or-right chutes opened and closed e.g. by levers or knobs. At the bottom of the apparatus, which I’ll also call T, would be 2^n boxes, each one labelled according to a value of P given one of the possible combinations of the x[i]. Given values v[i] for the variables x[i], the value of P could then be determined as follows: the ball [i] would be dropped in at the top of the machine and roll through a series of left-or-right chutes until it fell through to one of the boxes at the bottom; if the value v[i] was false, the chutes at level [i] would be opened to allow the ball to roll to the left, otherwise the chutes would be opened to allow the ball to roll to the right.

(As an aside, what I’m describing bears a curious resemblance to the Plinko Machine featured on the popular television gameshow “The Price Is Right”. The difference between the predicate-tree machine featured here and Plinko is that the predicate-tree machine would need to be built for scrupulously predictable behavior, whereas Plinko appears designed to maximize the random and unpredictable bouncing of its [i]-token.)

Is this bouncing-ball mechanism for computing P any more interesting than the abstract binary tree algorithm? One thing that ought to be observed is that the bouncing-ball mechanism (hereafter referred to as B) used to implement the algorithm as a literal apparatus is necessarily constrained in ways that the abstract algorithm does not appear to be. Most conspicuously, the B machine is a physical (albeit imaginary) artifact and so must occupy some non-zero amount of space. The height of the machine will be proportional to the number of variables N (since one tier is needed for each one), and the width of the machine will grow as a function of 2^N, since one box will be needed for each possible combination of values for x[i]. What this means, for instance, is that the machine may become very wide at the bottom very quickly if variables are added to P. One engineering challenge that would certainly present implementers and maintainers of B would likely be finding a space large enough to accommodate the apparatus, especially if N is quite large.

Still, even these facts are not surprising: of course the physical realization of a symbolic system with exponential growth would also grow exponentially in its spatial dimensions. There is, however, a subtlety that has been overlooked. Every feature of the abstract tree algorithm for computing P has to be physically realized in order to implement B, including features that are not usually the subject of time- or space-complexity analyses. Varying these parameters has important and highly suggestive consequences for the interpretation of P that do no necessarily follow from the abstract algorithm. One of these features is the pointer that descends through the nodes of the tree toward the leaf nodes. This pointer is realized as the ball [i], and it too must obviously have non-zero dimension in order to be realized. Denote the diameter of the ball [i] as D. The chutes in B must be at least D wide in order for the machine to function, i.e. for the ball [i] to fall through to a box at the bottom. In the event that B must be fit into a space of fixed side, e.g. a building, there will be some design pressure to make the chutes as narrow as possible, which in turn will require D to be even smaller.

By varying some of the other features of the predicate P and its encoding, along with the dimensions of [i], some interesting analogies pop out. For example, suppose that, in order to control the explosive growth in the width of the machine at its base, the chutes become progressively narrower as they descend. If the ball is too large, it may become stuck before it reaches the bottom. Supposing that the too-large ball [i] is the only one available, is there any way to work around this difficulty? There is, provided that the values of P are “not too random”. For instance, suppose that some number of contiguous boxes all have the same label, say 0, and suppose that there is a horizontal interval I in the machine such that, below a certain depth H, all chutes lead to one of the 0-boxes. Then the machine B could be fitted with an “escape chute” that takes the ball to a single 0-box once it has entered the area bounded by H and I. If all of the 0-boxes could be accommodated in this way, the value of P would be known to be 0 whenever [i] was able to roll all the way out of the machine, and 1 if it got stuck.

These assumptions about the number of 0s and 1s in the value of P and their contiguous arrangement (read: entropy) are pretty strong, and will be invalid in a lot of cases. Things become even more difficult if N is allowed to be infinite. While it might seem strange to allow this in a supposedly mechanical-spatial setting, it’s instructive to consider the consequences. For example, B could still function in a least some such arrangements. If the infinite number of boxes at the bottom of the machine could be rearranged into finitely many regions of all-0s or all-1s, the escape-chute mechanism would allow the ball to roll out of the machine after some finite period of time (read: would allow the machine to terminate). Conversely, if the infinitely-numerous boxes cannot be rearranged into finitely many all-1s or all-0s regions, i.e. if there is at least one box whose label that does not differ from its left- and right-hand-side neighbors, then the ball might never roll to the bottom — either because it became stuck, or because it simply took infinitely long to traverse an infinite distance. Interesting, which of these latter two outcomes depends upon whether the infinite machine is allowed to grow to an infinite height with a non-infinitesimal value of D, or whether the height remains finite while the minimum chute-width D becomes infinitesimally small.

In particular, they won’t work for any cases where N is infinite. Here’s the reason: in the finite case, it will only take a finite length of time for the ball to roll to the bottom. If it’s known exactly how long it take the ball to roll to the bottom, it can be inferred that the ball is stuck whenever it fails to appear at the bottom of the machine within that period of time. Even in the infinite case, there may still be contiguous regions of 0s or 1s that can be compressed into an escape chute out of which the ball might appear after a finite length of time. In the infinite case, however, the ball might require an infinite duration to roll to the bottom, and so it will be impossible in general to tell whether the ball is rolling or stuck by waiting for it to appear at the bottom. Holding the height and width of the machine fixed and finite, D is readily interpreted as the degree of precision possible in determining the value of P, with perfect precision only possible in the case of a rearrangement into finitely many continuous regions of all-0s or all-1s.

The machine B also bears an interesting resemblance to John H. Conway’s reinterpretation of the Dedekind Cut in his classic “On Games and Numbers”. The Dedekind Cut is simply an inductive definition of each real number as a set of the two closest inductively-hypothesized numbers that are respectively less or greater. More concretely, the Dedekind Cut defines a real number as lying at a unique position between a set of lesser numbers and a set of greater numbers. Conway’s construction of each real number resembles the B machine in that it also involves a (possibly infinite) progression through a series of left-or-right decisions. Infinite paths through the machine then correspond quite precisely to Conway’s construction of the transcendental and transfinite numbers.

The possibility of rearranging the boxes at the bottom of B corresponds very precisely to the entropy of the predicate P. While entropy is a widely abused and misunderstood term, it may easily be though of as the degree to which information can be compressed into a smaller form without losing its meaning. It should be obvious that it won’t always be possible to rearrange the boxes at the bottom of B without also changing the value of P, no matter how the variables x[i] are remapped among the tiers. In general, the higher the entropy of P, the further down [i] will have to travel before it can hope to escape through an auxiliary chute; in the case of maximal entropy, [i] no escape-chutes are possible at all.

It’s also interesting, and only natural, to ask whether the B machine has anything to say about whether P is decidable. Clearly, P will be decidable whenever B can be constructed in such a way that [i] will always roll out of the machine after some finite time has passed. What about if P is not decidable? P is clearly undecidable in the infinite case for entropy sufficiently high. It is interesting to ask, however, what relation there may be between the entropy P and the size of D, all of which are very conspicuously tied to the question of decidability. While this question has been examined elsewhere, most conspicuously in Algorithmic Information Theory, I do not know whether there may be any combinatorial or geometric interpretations of interest, e.g. whether D, H, and I obey concrete number-theoretic relationships under certain conditions.

These all seem like interesting questions, and although I am certain that at least some of them are at least partially answered elsewhere, I am also fairly confident that not all of them have been answered completely. While I do not know the answers myself, it would be quite interesting to hear yet another interpretation.