Explanation

An abacus machine is a simplistic computer that has a bunch of boxes called registers and these are numbered 1, 2, 3, 4, etc. There is an unlimited supply of pebbles available outside the boxes. There is no limit on how many pebbles a register can hold.

Abacus machine programs are written down by having a bunch of circles called nodes that represent a command and the nodes are connected by arrows that tell the computer where to look for the next command to execute. Abacus machine programs only have two kinds of commands, an increment and a decrement.

• The increment command is written down by having a plus sign together with the number of a single register. What the command 8+ means is “Add one pebble (from the vast stockpile) to register 8, and then follow the exit arrow for the next command.” Increment commands have only a single exit arrow.
• The decrement command is written down by having a minus sign together with the number of a single register. There are two exit arrows for a decrement command. One of them is labeled with an ‘e.’ What the command 8- means is “If there are no pebbles in register 8, follow the e arrow for the next command. Otherwise, remove one pebble from register 8, and then follow the unlabeled exit arrow for the next command.”

By stringing enough of these commands together, one can compute any function that can be computed by any sort of computer.

For example, the above program has the net effect of multiplying the number of pebbles in register 1 by the number of pebbles in register 2 and putting this number of pebbles in register 3. The idea is that the abacus machine starts at the entry arrow in the upper lefthand corner; empties out register 4; empties out register 3; then for every pebble it takes out of register 2, it goes through the loops at the bottom a bunch of times adding pebbles into register 3 (and adding pebbles into 4 and 1 to keep track of some temporary variables); and then it eventually exits through the arrow in the upper right hand corner, at which time the abacus machine stops.

The following program takes the first register n and second register m and puts the exponential m^n into the third register. The exit arrow with "Function is undefined" could be supplemented to add a pebble to some register. to signify that zero to the zero power is not a well-defined quantity.

More abacus computer programs can be found on the page for my logic course.

The Busy Beaver Problem

The running time of an abacus computer program is the number of computational steps to get from the start arrow (given a certain initial state of the registers) to the exit arrow.

An n-node busy beaver is a program with exactly n-nodes that starts and ends with all registers being empty and has the longest running time of any such program. The busy beaver problem is to find the busy beavers for various values of n. The function r(n) can be defined to be the running time of the n-node busy beavers, that is, the longest running time of any program with exactly n nodes that starts and ends with all registers being empty. The function r(n) is not a computable function, but we can find its magnitude for some values of n.

The following listing gives some values for r that are correct (unless I made a programming error).
r(1) = 1
r(2) = 3
r(3) = 5
r(4) = 10
r(5) = 16
r(6) = 27
r(7) = 43

Two 1-node programs that each run for 1 step:

A single 2-node program that runs for 3 steps:

Two 3-node programs that each run for 5 steps:

Because the blue arrow is never used, it could point to any of the existing nodes.

A single 4-node program that runs for 10 steps:

A single 5-node program that runs for 16 steps:

A single 6-node program that runs for 27 steps:

A single 7-node program that runs for 43 steps:

The above busy beavers were found with an exhaustive search of all possible programs by a computer program I wrote, so I am fairly sure that they are correct. Less certain are the programs with 8 or more nodes. It is easy to see a pattern for the above programs. A sequence of increment nodes in numerical order, ending with a single decrement register in the same order with its non-e exit arrows going as far to the left as possible without reaching a corresponding increment node. This pattern cannot generate a busy beaver for all values of n, but I wonder how far the pattern will work.