This is a Java applet that demonstates the operation of a two-register abacus. This is about the ultimate in RISC computing - a computer with two registers, and five operations: INCX, INCY, DECXJMP, DECYJMP, and HALT. It was shown by Minsky in 1967 that despite its simplicity this class of machines contains a machine that is "universal" - with the proper program (coded into the contents of its two registers!) it can simulate any computer whatsoever.

The INC* commands just increment one register. The DEC*JMP commands try to decrement, but if the contents of the register is 0 they branch to a different instruction instead. The HALT command just causes the machine to sit there and look pretty. The universal machine is a rather opaque hack involving several levels of simulation, and you cannot really see how it works at a glance. What I've exhibited here is a two-register abacus hard-wired to do the Collatz "3n+1" problem. Click on the big green button to start!

In this famous problem, you start with a number (a starting point of 7 is hardcoded into this version of the program; I hope that later versions will let you choose your own favorite number and do other cool things.) If the number's even you divide by 2; if it's odd you multiply by 3 and add 1. Then repeat until either you loop or you get to 1. Are there any loops? None have been found!

Conway has shown that a generalized version of the Collatz problem, using remainders modulo numbers larger than 2, is universal (meaning that it can simulate any computer) - so we may never know, because (as Turing showed) there are problems about computers that cannot be decided by any algorithm,and any universal computer can simulate these.)

Now, how does this applet work? Each little gold unit carries out one instruction; the symbols show which one, the color shows which register it acts on, and the pipes show how program control flows. To start off, we have the input number in register X, and register Y =0. We decrement X and check to see if we were successful, twice [let's assume, for the moment, that X hasn't yet reached 0] and then increment Y. Program control flows round the upper loop like this till X=0 at the first DECX unit (if X was initially even) or at the second (if X was initially odd.) If it exits at the first test Y is X₀/2 ; if at the second, (X₀-1)/2.

If control exits at the first test, it goes around the central 2-unit loop that alternately decrements Y and increments X. This copies Y into X. When this is done, the program re-enters the main loop.

If control exits at the second test, X was odd. We check to see if Y=0; if so, X was 1 and we are done. Otherwise, we increment Y again (to undo the unwanted side-effect of the test) and enter the bottom loop. This increments X (which is initially 0) at least 4 times, and six more times for each decrement that can be done to Y. Thus the new value of X is 6 (X₀-1)/2 + 4 = 3X+1. Thus, the actual values 7,22,11,... of the Collatz sequence are those that appear in X when Y=0.

What's the point of all this? In a recent paper, R. Paré, D. Pronk, and I consider the construction by which adjoint arrows, and unit and counit 2-cells, are freely added to a category. It is easy to determine whether two objects or arrows in the resulting bicategory are equivalent, but we show that the equivalence of 2-cells is in general undecidable! The proof involves a simulation of an arbitrary 2-register abacus by the bicategory generated in this way from a suitable category. The upper window shows a sequence of equivalent diagrams, corresponding to the states of the abacus.

It should be noted that not all the arrows in the same hom-set [that is, between the same pair of points] are the same. There are in fact infinitely many vertical arrows in the first and third position, one for each natural number; and in the center there are actually 16 arows, one for each program control state. Moreover, there are two 45-degree arrows (both in the same hom-set) and two shallowly-sloped arrows (side by side) for each pair (S,n) where S is a state and n is a number. Whether the arrows slope down to the left or to the right depends on whether the state acts on register X or register Y.

The graphics for the applet were raytraced using POV-Ray.