Introduction
Turing Complete is a videogame that allows you to build your very own computer completely from scratch and then program it! It’s essentially the book Code by Charles Petzold but in a game format - it is one of those games I did not expect it to be as fun as it turned out to be. Turing Complete is in my opinion the best way to learn about the basics of computer processors and is a great preparation for emulation projects (or at least it helped me understand things better) - it is one of those games that I’ve played through twice (and was significantly faster the second time around)
Here the trailer:
What do you do in Turing Complete?
Building the OVERTURE architecture
Turing Complete starts off with formal logic and lets you build your first logical components, such as the NAND, XOR nad NOR gates. Using these simpler components you then start building more complex ones step-by-step. You’ll learn about how to build memory components, adders, buses, switches, decoders, program counters and so on and so on - on the way you’ll learn the basics of binary arithmetic, hexadecimal numbers. How you wire components together is left completely up to you, the only thing that matters is that you pass the final test - though it is nice to use as little wires in the process as possible - this alongside hints is the only way the game guides you.
The next step is to finally assemble your first CPU together - you implement conditions, registers, instruction decoders and work with memory - this way you create the OVERTURE prcoessor.
I can’t believe I haven’t made a screenshot of my OVERTURE processor - but one can see it in the background here - I was also writing a maze solver program in assembly.
The OVERTURE is an excellent example of a von Neumann architecture - the program contains both the data and the program. I like to think of the program as the band of a turing machine and the ALU and counter perform operations on it, depending on what is on the band. The next step was then to program in binary (and to create your own assembly language to make the program readable instead of using the instructions manual) and solve little programming puzzles.
Building the LEG architecture
The next step was to build the LEG processor - this is an example of a RISC processor (a processor where all the commands have the same length) - the memory of the LEG processor is split into the program and the RAM (where the data is saved) thus the LEG belong to the Harvard architecture family.
From here on the game is more laissez-faire, the outputs of your components are not checked for accuracy. You implement new components, implement a bit shift, RAM, stack (including pushing and popping to/from the stack), division and functions. And then at long last my very own RISC processor was done:
My 8-bit LEG processor with 6 registers (where R5 is used for the RAM).
The COND which was used to evaluate conditions
The ALU, which was used to perform mathematical operations on the saved values.
And finally the Stack
Debugging the LEG often took me days. Here’s one example, I tried solving the towers of Hanoi, a famous problem best solved with recursion, but it imploded, here’s my first custom assembly code:
ADD+IMM2 IO 0 0 # max(nr)
ADD+IMM2 IO 0 1 # source
ADD+IMM2 IO 0 2 # destination
ADD+IMM2 IO 0 3 # spare
# move magnet to 0,1,2 comm: 0,1,2
# toggle magnet on/of comm: 5
label hanoi
# if disk_nr is 0:
If_Eq+IMM2 0 0 move1 # move disk from source to dest
#else
#move(disk_nr-1, source, spare, dest)
ADD+IMM2 0 0 STACK # nr
ADD+IMM2 1 0 STACK # source
ADD+IMM2 2 0 STACK # dest
ADD+IMM2 3 0 STACK # spare
SUB+IMM2 0 1 0 # nr-1
ADD+IMM2 2 0 4 # temp = dest
ADD+IMM2 3 0 2 # R2 = spare
ADD+IMM2 4 0 3 # R3 = temp = dest
JUMP 0 0 hanoi
#move disk from source to dest
ADD+IMM2 STACK 0 3 # spare
ADD+IMM2 STACK 0 2 # dest
ADD+IMM2 STACK 0 1 # source
ADD+IMM2 STACK 0 0 # nr
ADD+IMM2 2 0 IO
ADD+IMM1+IMM2 5 0 IO
ADD+IMM2 1 0 IO
ADD+IMM1+IMM2 5 0 IO
#move(disk_nr-1, spare, dest, source)
ADD+IMM2 0 0 STACK # nr
ADD+IMM2 1 0 STACK # source
ADD+IMM2 2 0 STACK # dest
ADD+IMM2 3 0 STACK # spare
SUB+IMM2 0 1 0 # nr-1
ADD+IMM2 1 0 4 # temp = source
ADD+IMM2 3 0 1 # R1 = spare
ADD+IMM2 4 0 3 # R3 = temp = source
JUMP 0 0 hanoi
If_Eq+IMM1+IMM2 0 0 end
label move1
ADD+IMM2 1 0 IO
ADD+IMM1+IMM2 5 0 IO
ADD+IMM2 2 0 IO
ADD+IMM1+IMM2 5 0 IO
RET 0 0 0
label end
Whenever I got stuck I talked to people on r/TuringComplete, explained my problem and how my assembly works to them and then I would usually get good advice. I find the problem of towers of Hanoi to be particularly memorable, because I got this hint: Use constants, give your variables meaninful names and make your code more clean. And wouldn’t you know it, when I rewrote my assembly in a more clean fashion the error got solved:
const nr 0
const src 1
const dest 2
const spare 3
const magnet 5
ADD+IMM2 IO 0 nr
ADD+IMM2 IO 0 src
ADD+IMM2 IO 0 dest
ADD+IMM2 IO 0 spare
label hanoi
# if disk_nr is 0:
If_not_Eq+IMM2 nr 0 hanoi_else # move disk from source to dest
ADD+IMM2 src 0 IO
ADD+IMM1+IMM2 magnet 0 IO
ADD+IMM2 dest 0 IO
ADD+IMM1+IMM2 magnet 0 IO
RET 0 0 0
label hanoi_else
#else
#move(disk_nr-1, source, spare, dest)
ADD+IMM2 nr 0 STACK
ADD+IMM2 src 0 STACK
ADD+IMM2 dest 0 STACK
ADD+IMM2 spare 0 STACK
SUB+IMM2 nr 1 nr
ADD+IMM2 dest 0 4 # register 4 = tmp
ADD+IMM2 spare 0 dest
ADD+IMM2 4 0 spare
JUMP 0 0 hanoi
#move disk from source to dest
ADD+IMM2 STACK 0 spare
ADD+IMM2 STACK 0 dest
ADD+IMM2 STACK 0 src
ADD+IMM2 STACK 0 nr
ADD+IMM2 src 0 IO
ADD+IMM1+IMM2 magnet 0 IO
ADD+IMM2 dest 0 IO
ADD+IMM1+IMM2 magnet 0 IO
#move(disk_nr-1, spare, dest, source)
SUB+IMM2 nr 1 nr
ADD+IMM2 src 0 4
ADD+IMM2 spare 0 src
ADD+IMM2 4 0 spare
JUMP 0 0 hanoi
#If_Eq+IMM1+IMM2 0 0 end
RET 0 0 0
Hurray! The game ends with challenging assembly programming problems, which are to be solved with the LEG processor and your own assembly language 🤠
Incredibly satisfying
My LEG-processor sorting numbers using selection sort - this is oddly satisfying.Building the OVERTURE and the LEG processors has been a surprisingly fun and educational adventure. Although Turing Complete is very basic and mainly made for nerds who want to build their own processor(s), it is a deeply immersive game and well deserving of its 5/5