Starting from NAND Logic Gates - Turing Complete Game Review

In the past, when discussing the topic of NAND logic gate-based computers, the first thing that comes to mind is the amazing course nand2tetris. This course teaches you how to build a functioning computer (running on a simulator) from the ground up.

Starting from the most basic theories, you learn about hardware-level logic gates and various circuit design instructions. You will write the necessary components yourself, design assembly language and instruction sets, and finally, you will write software-level programming languages, including compilation and assembly. Essentially, upon completing nand2tetris, you will understand how a computer operates behind the scenes.

Turing Completeness

When breaking down the work of a CPU, you'll find that most operations involve computations—such as addition, bit shifting, and matrix multiplication. So, how can we determine whether a computer is capable of computing all "computable things"?

For example, in games, you encounter a full adder, which performs addition operations, while subtraction can be accomplished using the concept of complements through addition. But what about multiplication? What about the sine function? Or the cosine function?

We could continuously add new hardware circuits like multipliers, sine function generators, and cosine function generators, but this approach would be endless, as there are countless formulas in the world, making it impossible to implement them all in hardware.

Turing proposed the theory of Turing completeness in his paper. Simply put, if we can store the address of the currently executing instruction (Program Counter) and derive the next state (Register) based on the current instruction, we can achieve Turing completeness. This is quite fascinating because Turing demonstrated that such a structure could solve all computable functions.

Visualizing Digital Logic

Recently, I discovered the game Turing Complete on Steam. Its concept closely mirrors that of nand2tetris (but only up to assembly language), starting from logic gates and gradually assembling a Turing-complete computer.

This game visualizes the coding process by transforming code writing into draggable logic gates, making it easier for players to observe changes in truth tables through real-time interaction.

By simplifying the process of writing truth tables on paper with a drag-and-drop interface; and using mouse clicks to toggle between 1 and 0 (ON and OFF), it eliminates the need for software installation and HDL description language, allowing players to start from the core concept.

A CPU can be decomposed into countless circuits composed of NAND logic gates. Your goal is to start from logic gates and complete levels step by step, ultimately building a working computer.

You will combine various circuits, including registers, memory, multiplexers, and demultiplexers, with various mini-challenges to help familiarize you with circuit characteristics. Upon completing levels, the game rewards you with the components you assembled, and as you progress, the number of components increases. The circuits in later levels become increasingly complex, requiring more components and connections.

The Path to Turing Completeness

A significant milestone in the game is Turing completeness. After completing the WORKING COMPUTER level, you'll realize that all the circuits you've painstakingly assembled were leading up to this moment. This level requires you to meet several conditions:

• Determine which operation to execute based on the bits of the byte code: ADD, XOR, OR, etc.
• Program Counter: Keep track of the program execution position.
• Decide whether to execute a jump (to a specified address) based on a specific bit: six conditions must be implemented (greater than, less than, equal to, always, never).
• Five registers.

What makes this game enjoyable is that the circuits drawn by each player are not identical; they have their own styles and implementation methods.

After completing this, you've essentially achieved the functionalities required for a computer, marking an important milestone. However, the game does not end here. Next, it will require you to use the circuit you've built to meet specified requirements, such as:

• Calculating mod 4: At the beginning of the game, you'll be asked to use byte code to gradually explore this.

  

• Calculating 2 * pi * r: Afterward, you can use the editor to write your own commands and create your instruction set.

• Navigating mazes: Write code to navigate through mazes.

If you actually engage your brain and hands to complete the game levels, I believe you can absorb a lot of knowledge about computer organization. Coupled with textbooks for further understanding, you might even find your foundation to be more solid than some engineers.

Evolving Existing Circuits

Once you complete the designated levels using assembly language, you'll begin to add more advanced features to the existing framework. A simple example is: why are there a limited number of registers, yet the program allows for many variables? The answer is RAM. Therefore, the next step in the game will require you to integrate RAM for addressing and fulfill specified functionalities.

The original circuit can only use r1, r2, and r3 as fixed registers for calculations or jumps when executing instructions. This can complicate coding, so the game will require you to implement a structure with OPCODE, argument1, argument2, and result. Each program will read 4 bytes, and you must decode these 4 bytes so that the entire circuit can freely decide which register to use for parameters and where to store the result.

With RAM, the circuit architecture becomes more flexible. The next task is to implement stack functionality, allowing our circuit to store a series of contexts, laying the groundwork for implementing functions, which means the circuit will become even more complex.

Once you reach this stage, a new feature—scoring—will be unlocked. The ideal situation during circuit implementation is to perform as many operations simultaneously as possible because passing through more logic gates means more delay. The game will calculate the number of NAND gates used and the delay, allowing you to revise the circuit for better performance.

Most of the upcoming levels will involve modifying the existing architecture and using assembly language to complete more advanced mini-games.

Drawbacks

This game is still in development. While you don't need a solid IT foundation, it helps to have a basic understanding of what logic gates do and to have some familiarity with binary concepts, making it easier to get started.

Additionally, the guidance and hints within the game are quite sparse, often requiring you to struggle, experiment, and think critically about improving the circuits. Especially in later levels, the circuits become increasingly difficult, making it hard to enjoy the gameplay. The game interface is also not very user-friendly, and connecting lines can be quite tedious.

There have been many instances where the game abruptly crashes while I'm playing, especially in the later stages. I hope this issue will be addressed before the official release.

Can Playing Games Really Teach You Something?

Another example worth mentioning is the Nintendo Switch’s Scratch Coding! Instant Play First Game Design.

Its game tutorial design is excellent, providing numerous examples to guide you through implementing various features, detailing what you need for each implementation, and letting you run the code to see the results, prompting you to correct them. Needs → Implementation → Verification → Modification—this closely mirrors the actual development cycle. In this game, you don’t need to write any code; all functionalities are abstracted into individual "nodes," allowing for drag-and-drop interactions. The essence of programming is not the syntax itself, but the underlying logic of thought. Moreover, the documentation for starting game programming on the Nintendo Switch is exceptionally well-written, serving as a solid model for developers.

Turing Complete, however, is a bit more intense; essentially, you won’t find much in the way of step-by-step tutorials (I’m not sure if this will change after the official release), so you often have to figure things out on your own.

The benefit of gamification is that it allows us to skip all unnecessary installation setups and understanding of language symbols, diving directly into the core concepts. The author has abstracted the concepts of logic gates and truth tables into visual and draggable blocks, making it much more intuitive than writing code or text.

Reflections

This game has allowed me to revisit the fundamentals of computer architecture and to review nand2tetris. Although I had some exposure to similar courses in school, very few courses allow you to build a functioning computer from scratch. Even though most concepts were covered in school, hands-on experience with wiring circuits often presents challenges, making the accomplishment of assembling a circuit genuinely gratifying.

Of course, it’s not feasible to use the circuits assembled in the game in the real world, as functionality alone isn’t enough in practical applications. However, for beginners, this approach helps learners quickly grasp core concepts, making it highly recommended for anyone interested in understanding how computers work behind the scenes.

One phrase from the preview video left a deep 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.

However, after playing, I feel that the game's entry barrier is quite high. The teaching and explanations are very sparse, often written in a convoluted manner, requiring you to implement circuits right from the start. This can be particularly daunting for players unfamiliar with binary and digital logic. In later stages, the hints and explanations are almost nonexistent, and due to the difficulty level, hitting a wall and getting stuck is very common, making it less suitable as a purely entertaining game.

I even believe that with the advancements in computer technology in the 21st century, we can leverage powerful computational capabilities and visual effects to exponentially enhance learning. When studying digital logic, we often want to observe the relationship between input combinations and outputs, necessitating constant modifications to input values. This task can be cumbersome on paper, where we need to erase numbers, but on a computer, it is different—clicking the mouse can instantly change a 0 to a 1, with outputs updating in real-time.

• Reduced costs for feedback cycles.
• Immediate observation of results.

These two factors alone significantly boost our learning efficiency compared to individuals from decades ago.

References

This is a previous livestream. Although not all game content was streamed, most levels should be available there.