Contents > General-purpose Computer

Overview

The following general-purpose computer is a deterministic linear bounded automaton that emulates an 8-bit processor and up to 64 KiB of RAM. As with the abstract machines, it employs an infinite array abstraction for storage. A process loads a machine code program into the first L bytes of the array, it pads out the program with two zeros, and it reserves 21 bytes for a state register:

The machine code program is a sequence of bytes representing instructions and data. At execution time, the computer restricts the program to accessing its own bytes, as opposed to the entire array. This means, the loaded program is the initial state of the computer’s RAM. Its length, L, establishes the RAM size and a fixed address space, 0‥L−1, where L ≤ 65,536 bytes, the maximum RAM size.

A segment of the state register contains the address of the next instruction to execute. To fetch the instruction, the computer slides the state register across RAM, applying a function, fetchLoadStore, to each byte along the way. When the state register reaches the instruction’s address, fetchLoadStore copies the instruction to a segment of the state register.

Similarly, a segment of state register may contain the address of a byte to load or store. If present, when the state register reaches that address, fetchLoadStore copies a RAM byte to a state register byte, or vice versa.

After the computer slides the state register across RAM, it applies a function, decodeExecute, to decode and execute the fetched instruction. It puts calculated results in segments of the state register.

The following pseudocode summarizes the computer. The inner loop on line 2 slides the state register leftward and the inner loop on line 7 slides the state register rightward.

while true
  for x ← L−1 down to 1
    ax‥ax+23 ← fetchLoadStore(ax‥ax+23)
    slideRegister(x+3, −1)
  a0‥a23 ← fetchLoadStore(a0‥a23)
  a3‥a23 ← decodeExecute(a3‥a23)
  for x ← 0 to L−2
    ax‥ax+23 ← fetchLoadStore(ax‥ax+23)
    slideRegister(x+3, 1)
  aL−1‥aL+22 ← fetchLoadStore(aL−1‥aL+22)
  aL+2‥aL+22 ← decodeExecute(aL+2‥aL+22)

fetchLoadStore operates on the state register bytes, ax+3‥ax+23, and three extra bytes immediately left of the state register, ax‥ax+2. The state register slides left only as far as address 3 to enable fetchLoadStore to simultaneously engage the state register and the leftmost machine code byte (line 5). Likewise, the two padding bytes enable fetchLoadStore to simultaneously engage the state register and the rightmost machine code byte (line 10).

decodeExecute operates exclusively on the state register. It defers execution of load and store instructions to fetchLoadStore since it does not engage RAM.