Building a Computer from NAND Gates: Turing Complete Game Review

Whenever people talk about building a computer starting from NAND logic gates, the first thing that usually comes to mind is the legendary course nand2tetris. This course teaches you how to actually build a working computer (running on a simulator).

Starting from foundational theory, you begin at the hardware level with logic gates and various circuit design instructions, write necessary components yourself, design an assembly language and instruction set, and finally write software-level programming languages—even covering compilers and assemblers. Basically, after finishing nand2tetris, you truly understand how computers work under the hood.

Turing Completeness

If you break down the tasks of a CPU, you’ll find that most operations are doing calculations: basic arithmetic, bit shifting, matrix multiplication, and so forth. So, how can we know whether a computer is capable of computing everything that is “computable”?

Take a full adder as an example. You encounter it in the game to perform addition, and subtraction can be achieved with addition using two’s complement. But what about multiplication? What about the sine function? Or cosine?

We could keep adding new hardware circuits like multipliers, sine calculators, or cosine calculators, but that would be a never-ending endeavor. There are simply too many formulas in the world to implement all of them directly in hardware circuits.

Alan Turing introduced the concept of Turing completeness in his paper. Simply put, if we can store the address of the currently executing instruction (the Program Counter) and determine the next state based on the current instruction (Registers), we can achieve Turing completeness. It’s truly fascinating: Turing proved that such an architecture can solve any computable function.

Visualizing Digital Logic

Recently on Steam, I discovered the game Turing Complete. Its core concept is practically identical to nand2tetris (though it stops at assembly language), starting from logic gates and gradually assembling a Turing-complete computer.

Through visualization, the game turns writing code into draggable logic gates. Its real-time interactivity makes it much easier for players to observe truth table changes on the fly.

Wiring connections simplifies the hassle of scribbling truth tables on paper. Toggling between 1 and 0 (ON and OFF) with a simple mouse click eliminates the need for software installations or HDL (Hardware Description Language) code, allowing players to focus directly on core concepts from the very beginning.

A CPU can be broken down into circuits built from countless NAND gates. Your goal is to clear levels step by step starting from logic gates, ultimately producing a working computer.

You combine logic gates into various circuits, including registers, memory, multiplexers, and demultiplexers, with mini-levels designed to familiarize you with circuit behaviors. Whenever you complete a level, the game packages your assembled circuit into a usable component. As you advance, you accumulate more components, and later levels feature increasingly complex circuits requiring more components and wiring.

The Road to Turing Completeness

A major milestone in the game is achieving Turing completeness. Once you complete the “WORKING COMPUTER” level, you realize that all the circuits you painstakingly built were leading up to this moment. This level requires you to satisfy several conditions:

• Determine which operation to execute based on the bits of the bytecode: ADD, XOR, OR, etc.
• Program Counter: keeps track of the current execution address
• Determine whether to execute a jump (jump to a specified address) based on certain bits: implement six conditions (greater than, less than, equal to, always, never)
• 5 registers

What makes this game fun is that no two players’ circuits look entirely the same; everyone develops their own style and implementation approach.

Once you finish this, you have essentially built all the functions required for a computer—a significant milestone. However, the game doesn’t end there. Next, it asks you to use your assembled computer to complete specific level challenges, such as:

• Computing mod 4: Initially, the game has you click through bytecode manually

  

• Computing 2 * pi * r: Next, you can write using an editor where you can name your own instructions and create your own instruction set

• Solving a maze: writing code to navigate a maze

If you truly engage your brain and play through these levels hands-on, you can absorb a tremendous amount of computer architecture knowledge. Paired with a textbook for deeper understanding, your fundamentals could easily end up stronger than those of quite a few software engineers.

Evolving Existing Circuits

Once you complete the game’s challenges using assembly language, you’ll start adding more advanced elements to the existing architecture. For instance: why are registers limited in number, yet programs can support so many variables? The answer is RAM. Consequently, the game next asks you to incorporate RAM, handle memory addressing, and accomplish designated tasks.

The original circuit could only use fixed registers like r1, r2, and r3 for calculations or jumps when executing instructions. However, this makes writing code quite cumbersome. The game therefore asks you to implement an architecture structured around OPCODE, argument1, argument2, and result. The program reads 4 bytes each time, and you must decode these 4 bytes so the circuit can dynamically decide which registers to use for parameters and where to store the result.

With RAM and a more flexible circuit architecture in place, the next step is implementing a stack. This allows our circuit to store a sequence of execution contexts—the foundation for implementing functions later on—which means the circuit becomes even more complex.

Once you reach this stage, a new feature unlocks: scoring. Ideally, when implementing circuits, you want as many operations running in parallel as possible, because signals passing through more logic gates introduce greater delay. The game tallies your NAND gate count and tick delay, encouraging you to revisit and optimize your circuits for better performance.

Most subsequent levels involve modifying this existing architecture and using assembly language to solve more advanced mini-games.

Drawbacks

The game is still under active development. While it doesn’t require a deep IT background, you do need a general understanding of what logic gates do and a basic grasp of binary to get started comfortably.

Additionally, guidance and hints in the game are sparse. You often have to spend considerable time struggling, constantly trial-and-erroring, and iterating on your circuits. As the circuits grow increasingly difficult in later stages, it can sometimes feel less like playing a fun game. The UI isn’t particularly intuitive either, and routing wires can become quite painful.

The game also crashed on me unexpectedly multiple times, especially in the mid-to-late game where crashes became quite frequent. Hopefully, this will be ironed out upon full release.

Can You Really Learn from Games?

Another good example of this kind of game is Nintendo Switch’s Game Builder Garage.

Its tutorial design is superb: it uses numerous examples to explain what features you’re about to build, what you need to build them, lets you run the result, and guides you to fix issues. Requirements → Implementation → Verification → Iteration—it mirrors an actual software development lifecycle. You don’t have to write any code; every function is abstracted into interactive “Nodon” nodes that you connect visually. The essence of programming has never been syntax itself, but the thinking logic behind it. Moreover, the built-in function documentation in Game Builder Garage is so well-written it could serve as a model for developer docs everywhere.

Turing Complete is considerably more hardcore. You basically won’t find step-by-step hand-holding (not sure if that will change in the official release), so you’re mostly left to figure things out on your own.

The advantage of gamification is that we can skip all the unnecessary environment setups and esoteric syntax, diving straight into the core concepts. The developer abstracts logic gates and truth tables into visual, draggable components, which is far more intuitive than writing code or text.

Final Thoughts

This game allowed me to revisit the foundations of computer architecture and served as a great refresher on nand2tetris. Although I had encountered similar coursework in school, very few courses let you build a working computer entirely from scratch like this. Even though most concepts were things I had studied before, actually wiring things up still presents plenty of challenges, which made the satisfaction of finally getting a circuit to work all the more rewarding.

Of course, you can’t just take the circuits wired up in a game and use them in real life; real-world engineering involves far more than merely getting logic to work. But for beginners, this approach helps learners grasp core concepts much faster. I highly recommend this game to anyone curious about how computers work under the hood.

A quote from the trailer left a lasting impression on me:

If you try to make such projects, unseen by others, as perfect as any human could, you’ll develop skills that other professionals don’t have

That said, after finishing it, I feel the barrier to entry is quite high. The tutorials and explanations are minimal and often rather cryptic. Throwing you straight into building circuits from the start can be a steep wall for players unfamiliar with binary and digital logic. Later hints and explanations are practically non-existent. Given the difficulty, getting stuck and sitting in deep contemplation is completely normal, so it might not be suitable if you’re looking for purely casual entertainment.

I would even argue that with how mature computing technology has become in the 21st century, the computational power and visualization capabilities of computers can boost learning exponentially. When studying digital logic, we constantly want to observe relationships between inputs and outputs, which requires continually modifying input values. Doing this on paper is tedious because you constantly have to erase and rewrite numbers. On a computer, however, a single mouse click flips a 0 to a 1, and the output updates instantaneously.

• Drastically reduced feedback loops
• Instant observation of results

These two advantages alone make our learning efficiency vastly superior to what was possible decades ago.

References

Here are previous livestreams of my playthrough. While they don’t cover the entire game, most levels can be found here: