A Simple CPU on the Game of Life - Part 4
by Nicholas Carlini 2021-12-30
This is the fourth article in a series of posts that I've been making on creating digital logic gates in the game of life. The first, couple of articles started out with how to create digital logic gates and use them in order to construct simple circuits. In this post we're going to actually build a first real computer: a (2-stage pipelined) unlimited register machine. And later on ([5]) we'll make an even better computer.
Pictured below is the execution of an unlimited register machine which is running a program that factors the number 15 it does this in just a few minutes. You might think that this is a simple task, but let me just remind you that it was only a few years ago that quantum computers managed this impressive feat.
Background
At this point I'm not going to explain what Conway's game of life is, or I use it to build circuits that run on the game of life. I've done that three times before and these backgrounds get boring to write. Fortunately for you, even though this is the fourth time I'm writing about this, in practice you only need to read the last post to get caught up enough for this one to make sense.
CPU Overview
Before you can reasonably understand why I'm making the desgn decisions I am, I finally have to tell you what a URM actually is. First described as a mathematical formaliziation of what is computable, a URM is a Turing complete, four-instruction CPU that should (in theory) have an unlimited numver of registers, each of which can hold unbounded integers. Because we're dealing with the real world, our CPU is going to allow just 16 registers, each of which will be able to hold four bits.
An unlimited register machine can do only three operations on the registers:
Increment (INC Rx) a target register by one. Decrement (DEC Rx) a target register by one. Jump (JNZ Rx, Addr) to a target instruction if the current register is nonzero.
... continue reading