Z80 Homebrew Computer Part 2 -- Turing Completeness, Register Machine Compiler

◷ 15 min read

✏ published 2021-06-07

Jack Leightcap

Contents

- Abstract

- Unlimited Register Machine Description and Instruction Set

- "Formal" Definition

- Instruction Set

- Program Execution

- Program Examples

- Example 1: Adder

- Example 2: Decrement

- URM Compiler

- URM Compilation: Instruction Compilation

- URM Compiler Implementation: AWK

- Conclusion

Abstract

In the first part of this series, I asked:

Has adding RAM actually increased the class of programs this computer can run?

with an answer of:

and I'll use the formal "appeal to I mean yeah probably" to claim it's now Turing Complete.

In this post I'll show this was not the case! What I missed was that the Z80 already has a built-in way of maintaining state — its registers! This post will show that the Z80, even without RAM, is fully Turing Complete by means of a executing an Unlimited Register Machine (URM).

This is demonstrated by writing a compiler (in AWK!) from a URM program to Z80 assembly.

Unlimited Register Machine Description and Instruction Set

URMs are an example of a mathematical idealisation of what it means for something to be a computer.

The study of register machines came from a need to have one of these mathematical idealizations that actually reflected how a real computer works; compared to something like lambda calculus which is totally unintelligible to any commercial processor.

There's a lot of academic literature about URMs (largely from the 1960s-1970s) — here, I'll be using the very approachable definitions found in Cutland: Computability: An Introduction to Recursive Function Theory (1980).

"Formal" Definition

A lot of the descriptions of these mathematical idealizations are bogged down by very precise definitions that obscure the underlying elegance, in my opinion, so here I'm going to have a fast-and-loose formal definition so you can jump right into examples.

A URM has an infinite number of registers R1, R2, R3, ...; where each Rn contains a natural number rn.

  R1   R2   R3   R4   ...
+----+----+----+----+------
| r1 | r2 | r3 | r4 |
+----+----+----+----+------

In addition, there's a single instruction register that contains a natural number indicating the next instruction to execute.

The state of all registers is modified by a finite ordered set of instructions (I1, I2, I3, ..., Is), which constitute a program denoted P of size s. These instructions are defined by the instruction set.

Instruction Set

The instruction set consists of four very basic instructions,

Instruction   Effect
------------+-----------------------
Z(n)        | rn := 0
            | Ik := Ik + 1
------------+-----------------------
S(n)        | rn := rn + 1
            | Ik := Ik + 1
------------+-----------------------
T(m,n)      | rn := rm
            | Ik := Ik + 1
------------+-----------------------
J(m,n,q)    | Ik := Iq iff rm == rn,
            | Ik := Ik + 1 otherwise
------------+-----------------------

some of these instructions are actually redundant — see Minsky Computation: Finite and Infinite Machines (1967), and the definition of Minsky's eponymous Minsky Machines, for what constitutes the "bare minimum" instruction set for register machines.

Program Execution

The execution of instructions is defined by the instruction set as a kind of look-up table. The two remaining considerations for program execution are initialization and halting.

Program initialization simply initializes each register ri to some value ai:

(r1, r2, r3, ...) := (a1, a2, a3, ...)

In practice, a finite (and usually pretty small) number of registers n are initialized to some value; it's convenient to then say all other registers are initialized to zero:

(r1, r2, r3, ..., rn, ...) := (a1, a2, a3, ..., an, 0, 0, 0, ...)

Programs halt based on the simple rule that if the instruction register "jumps off the end" of the program; the program halts. This can occur in a few ways:

Program Examples

So, what do programs look like given this model?

Example 1: Adder

Surely a good program to have is one that can add numbers. It can be a fun puzzle to try and sus this problem out from the given instruction set.

Here's a three-register solution,

 // initialize r1 = a, r2 = b
 // computes r1 = a + b
 1: J(3,2,5)
 2: S(1)
 3: S(3)
 4: J(1,1,1)

let's walk through how 1 + 2 would be executed.

  R1   R2   R3
+----+----+----+
| 1  | 2  | 0  |    Initial state
+----+----+----+

+----+----+----+
| 1  | 2  | 0  |    I1: J(3,2,5)   0 ?= 2, false, go to I2
+----+----+----+

+----+----+----+
| 2  | 2  | 0  |    I2: S(1)       r1 += 1, go to I3
+----+----+----+

+----+----+----+
| 2  | 2  | 1  |    I3: S(3)       r3 += 1, go to I4
+----+----+----+

+----+----+----+
| 2  | 2  | 1  |    I3: J(1,1,1)   1 ?= 1, true, jump to I1 (compare to itself, unconditional jump)
+----+----+----+

+----+----+----+
| 2  | 2  | 1  |    I1: J(3,2,5)   1 ?= 2, false, go to I2
+----+----+----+

+----+----+----+
| 3  | 2  | 1  |    I2: S(1)       r1 += 1, go to I3
+----+----+----+

+----+----+----+
| 3  | 2  | 2  |    I3: S(3)       r3 += 1, go to I4
+----+----+----+

+----+----+----+
| 3  | 2  | 2  |    I4: J(1,1,1)   1 ?= 1, true, jump to I1
+----+----+----+

+----+----+----+
| 3  | 2  | 2  |    I4: J(3,2,5)   2 ?= 2, true, jump to I5
+----+----+----+

+----+----+----+
| 3  | 2  | 2  |    I5: HALT       no more instructions! halted
+----+----+----+

Voilà! Like stated, r1 = 1 + 2.

This can be much easier to understand if instead presented as a state diagram.

            START
              |
              v
         ___________
        /           \  YES
  +---> | r3 ?= r2  | -----> HALT
  |     \___________/
  |           |
  |           | NO
  |           v
  |     +-----------+
  |     | r1 = r1+1 |
  |     +-----------+
  |           |
  |           |
  |           v
  |     +-----------+
  +-----| r3 = r3+1 |
        +-----------+

It's funny; writing these URM programs makes assembly seems like a super high-level, feature-full programming language. Writing this adder program equivalently for the Z80,

// compiled URM that computes b = b + c

INIT:
    ld b, 2
    ld c, 1
I1:
    ld a, c
    cp d
    jp z, I5
I2:
    inc b
I3:
    inc d
I4:
    ld a, b
    cp b
    jp z, I1
I5:
    // b contains 2 + 1 = 3
    halt

of course, if we had the luxury of having an add instruction (like the Z80 does), we could've just said:

add b, c

but clearly we've proved that addition can be performed just fine without even having an add instruction.

Example 2: Decrement

Ok, hopefully that example wasn't too much torture. Don't worry, I'm not going to walk through another program fully, just present another relatively simple program that proves that decrementing a number is possible. Well, kind of decrement — because registers only contain natural (non-negative) values, we instead say this computes the function

            / x - 1   if x > 0
  dec(x) = <
            \ 0       if x == 0

A 4-register solution,

 // initialize r1 = x
 // computes r1 = (x == 0) ? 0 : x - 1
 1: J(1,4,8)
 2: S(3)
 3: J(1,3,7)
 4: S(2)
 5: S(3)
 6: J(1,1,3)
 7: T(2,1)

At first, the state of the registers is set up to look like

  R1   R2   R3
+----+----+----+
| x  | 0  | 1  |
+----+----+----+

During the main loop of the program, the state of the registers looks like

  R1   R2     R3
+----+----+--------+
| x  | k  | k + 1  |
+----+----+--------+

The program loops, increasing k, until x == k + 1; then the answer is k.

Well, this is actually kind of a 3-register solution; register 4 is being used as a constant zero and is never modified. Again, compared to the equivalent solution in Z80 assembly,

// compiled URM that computes b = (b == 0) ? 0 : b - 1

INIT:
    ld b, 43
I1:
    ld a, e
    cp b
    jp z, I8
I2:
    inc d
I3:
    ld a, d
    cp b
    jp z, I7
I4:
    inc c
I5:
    inc d
I6:
    ld a, b
    cp b
    jp z, I3
I7:
    ld b, c
I8:
    // b contains 43 - 1 = 42
    halt

Neat!

URM Compiler

Naturally, the next step is to write a compiler to take care of the URM to Z80 assembly translation automatically. Writing a compiler is also a good way to formalize the capabilities of Z80 as an environment to execute a URM.

These examples show that there's a very direct mapping between the instructions of a URM and the actual instructions a CPU executes. This shows that register machines are in fact a good theoretical model of actual processor hardware.

In the theoretical model, there's an infinite number of registers that can hold any natural number. Of course, there's the clear limitation that the Z80 registers are hardly unlimited in count or the numbers they can hold! We're limited to values encodable by 8-bit (0 through 255), and the finite set of registers

type R = B | C | D | E | H | L | Ixh | Ixl | Iyh | Iyl

For those already very familiar with the Z80, there's actually a few pieces I'm leaving out here (A and F, shadow registers, stack pointer). There are technical reasons for excluding each, but the reason is beyond the scope of this post.

URM Compilation: Instruction Compilation

Considering how each instruction is compiled,

Z(n) =>
  ld n, 0

S(n) =>
  inc n

T(m,n) =>
  ld n, m

J(m,n,q) =>
  ld a, n
  cp m
  jp z q

This very linear mapping makes for a very straightforward compiler!

URM Compiler Implementation: AWK

This very straightforward text replacement is very easy with AWK. The gist is short enough to include here:

#!/usr/bin/awk -f

BEGIN {
    reg_map["1"] = "b"
    reg_map["2"] = "c"
    reg_map["3"] = "d"
    # ...

    FS = "[,|(|)|=]"
    icount = 0 # number of instruction lines
    rcount = 0 # number of register initialization lines

    print "INIT:"
}

/[0-9]+=[0-9]+/ {
    rcount++
    printf("\tld %s, %d\n", reg_map[$1], $2)
}

/Z\([0-9]+\)/ {
    icount++
    printf("I%d:\n\tld %s, 0\n", NR - rcount, reg_map[$2])
}

/S\([0-9]+\)/ {
    icount++
    printf("I%d:\n\tinc %s\n", NR - rcount, reg_map[$2])
}

/T\([0-9]+,[0-9]+\)/ {
    icount++
    printf("I%d:\n\tld %s, %s\n", NR - rcount, reg_map[$3], reg_map[$2])
}

/J\([0-9]+,[0-9]+,[0-9]+\)/ {
    icount++
    printf("I%d:\n\tld a, %s\n\tcp %s\n\tjp z I%d\n", NR - rcount, reg_map[$3], reg_map[$2], $4)
}

END {
    # specific output instructions for whatever machine...
    printf("I%d:\n\thalt\n", icount + 1)
}

You can find the rest of the source here.

Let's test it with the earlier add example!

; cat test/add.urm
1=3
2=5
J(3,2,5)
S(1)
S(3)
J(1,1,1)
; ./urm_z80.awk test/add.urm > add.asm
; cat add.asm
INIT:
  ld b, 3
  ld c, 5
I1:
  ld a, c
  cp d
  jp z I5
I2:
  inc b
I3:
  inc d
I4:
  ld a, b
  cp b
  jp z I1
I5:
  # output specific instructions
  halt
; $Z80_ASSEMBLER add.asm -o add.bin
; $Z80_EMU add.bin
> 8

When executed, this does indeed print 8!

We now have a complete compiler (written in AWK, very cursed).

Conclusion

Restating,

The Z80, with only ROM, can emulate → A URM, which is provably → Turing Complete!