Register Machines

This Demonstration allows an exploration of the register machines discussed in chapter 3 of A New Kind of Science. Register machines are treated as logical abstractions of physical registers used in electronic devices. Registers are often used to store information to be used for storing data and performing calculations.

In this Demonstration, register machines are capable of two possible instructions: incrementing and decrement-jumping (the register is decremented in all cases except for empty registers, where a different instruction is performed). Register machines are capable of demonstrating complex and random behavior, as well as performing simple arithmetic such as addition and subtraction. They also have properties of universality, and provide a simple example of computation exhibited by modern computer processors. A halted state (an state where is the number of instructions in the program) has been added to discover discrete functions as demonstrated in Snapshot 5.

Here is the chosen color scheme: green represents a nonzero value or "1", yellow is the background color, and red represents a register overflow.

The register machine is displayed in two different forms: as a program counter and its registers or as the program. In the program view the arrows indicate the flow of execution through the program—the register to be modified and the modifier are displayed. A blank arrow is used to indicate the direction of the decrement-jump.

The register machine stores several key values—the registers store key values (in unary format) and the program counter stores values of the location of the current instruction being executed within the program. Time is represented down the axis.

Snapshot 1 : an example of somewhat random and conditional behavior in a register machine and its program counter; register 1 is cleared, and then oscillates until registers 2 and 3 are clear

Snapshot 2 : the program view of the register machine in Snapshot 1, as an example of a simple program exhibiting complex behavior

Snapshot 3 : an example of complex and conditional behavior in a register machine

Snapshot 4 : an example of overflow of register 3; should this occur then increase the register size

Snapshot 5 : an example of a computation: register 1 = Ceiling[register 1 / 2] and clearing register 2

Snapshot 6 : the program view of the computation described in Snapshot 5; notice that the seventh instruction is a "halted state"

Snapshot 7 : an example of an operation: clear register 3 and do not modify registers 1 and 2

Snapshot 8 : an example of an operation: clear registers 2 and 3 and do not modify register 1

Snapshot 9 : the program view of the operation described in Snapshots 7 and 8; notice that by starting at different points within the program, you can perform several functions with the one program

Snapshot 10 : an example of a computation: register 1 = register 1 + register 2, clear register 2, and then clear register 1

Snapshot 11 : the program view of the operation described in Snapshot 10

This Demonstration is constrained to a maximum of:

- three registers,

- six instructions,

- eight-bit registers, and

- ninety units execution time.

From an exploration of the various combinations, you can see that register machines are capable of exhibiting complex and random behavior. Register machines are also capable of performing elementary operations such as addition and subtraction. However, register machines can perform multiple operations based on starting simple programs at different points within the program, as demonstrated in Snapshots 7 to 9. Also, optimization of low-level code is possible by identifying the fastest program that meets functional requirements through testing all possible combinations of instructions, such as the program described in Snapshots 5 and 6 (as this computation only requires 4 low-level instructions before halting).

This Demonstration is based on a project undertaken by the author at the NKS Summer School 2007. For further information please see the external link to the NKS Summer School 2007.