For a long time I've been thinking about building one based on relays. The problem is that I would need a lot of relays just to achieve anything very simple. My solution: think about the simplest computer architecture I could come up with, and the simplest one was a NAND computer. In this architecture, the program is a simple loop with instructions all in the same format: input addess 1, input address 2, output address. The only supported instruction simply writes at the output address the result of a NAND operation of the input addresses.
Since any circuit can be built using only NAND's, this computer can simulate any circuit, including the circuit of a Turing complete CPU. It certainly would be very slow, but relatively simple to build. I still have to think about a good type of memory for this machine. Maybe one day I'll take the courage to build it.
For something simpler than the computer described in the article, you might be interested in Usagi Electric's UE-1 vacuum tube computer. Construction is nearing completion, and it's documented on Youtube:
Yes, code executes directly from a literal loop of paper tape, and more specifically, there is only one loop (the paper tape loop), and every instructions executes at every iteration.
Yet it can do what any other computer can do (in terms of computation, not I/O), because not every instruction has to actually effectively do something in each iteration, and it is a cornerstone of theoretical computer science that you can transform every program into one represented in an academic language called "WHILE", which is restricted to exactly that principle: It only consists of a single outer WHILE loop, and then inside the loop you have a bunch of conditions.
The problem with ultra low gate counts is always memory. No matter how simple your CPU is, you still need at least thousands of discrete components for it to do anything useful, unless you resort to something like Williams tubes or delay lines. (Torsion wire delay line is probably the most practical form of memory for a computer like this)
You can build an interesting CPU core out of whatever, and then connect it to a silicon SRAM chip, and still say you built an interesting CPU core out of whatever.
I started designing this, designed one using transistors instead, and built half of that.
But I think you can built an 8-bit relay version of my 16-bit transistor CPU core with on the order of 400 DPDT relays, which is on the order of $1000, plus a comparably big bag of diodes, which is much less than $1000. This includes registers (10 of them), control and sequencing logic (including a diode microcode matrix), but not RAM, which you wouldn't want to make from relays. (To make an 8-bit version you'd probably have to add another 3 upper address registers, to still have 16-bit addresses.)
Yup, having an emulator for another, more complex architecture running on the very simple architecture is common amongst projects like this. Linux on Intel 4004 does exactly this: https://dmitry.gr/?r=05.Projects&proj=35.+Linux4004
And its predecessor project(s) do as well.
Usagi's UE-1 was already mentioned as another vacuum tube computer. It indeed just runs instructions in a loop, and runs every instruction in each loop (but not every instruction is always effective).
> For a long time I've been thinking about building one based on relays.
When I was in 7th grade, around 55 years ago, I used a relay to make what was, both literally and figuratively, a 2-bit computer. Got an A+ on the math class project though! :)
Since any circuit can be built using only NAND's, this computer can simulate any circuit, including the circuit of a Turing complete CPU. It certainly would be very slow, but relatively simple to build. I still have to think about a good type of memory for this machine. Maybe one day I'll take the courage to build it.