Quantcast

How Real Computers Are Built in Virtual Worlds

By Alex Castle

Everything I need to know about computer science, I learned in Minecraft.

I like to build PCs. Not as much as our resident PC columnist, maybe, but I still get a real kick out of ordering a bunch of components and spending an afternoon putting a PC together. I think that earns me a little nerd cred. But you know what earns you a LOT of nerd cred? Building a fully functioning PC—in Minecraft.

My favorite thing about projects like these are that not only are they an incredible example of the maker spirit, they’re a great teaching tool for something a lot of people don’t understand—how, at a deep level, the computer they use every day actually works. Today, we're going to look at some of the crazy things people build in Minecraft and other video games, and how they explain some of the most fundamental lessons of computer science.

The Basics of Turing Machines

If you spend very long hanging out in the sorts of seedy places people where gather to discuss building virtual computers, you’re going to hear the term “Turing Machine” thrown around. For instance, you might have seen that somebody built a Turing Machine in Dwarf Fortress but I’ll be damned if you’re going to be able to figure out what that thing does just from looking at the diagram.

So let’s talk a bit about Turing Machines. It’s a complicated topic, but also a tenant of modern computer science—so if you can pick this up, consider your daily enrichment quota fulfilled.

Photo credit: Flickr user maria_keays via Creative Commons.

A Turing Machine is a conceptual machine composed of four parts:

1) A strip of tape, upon which are printed some number of symbols (letters, numbers, whatever. It doesn’t matter, as long as the set of symbols is defined in advance).

2) A head, which can read and write one symbol on the tape at a time.

3) Some finite set of internal states.

4) A set of rules that govern the machine’s behavior.

The machine, as thought up by Alan Turing, is able to read and write symbols on the tape, as well as to move the tape right or left, and to switch its internal states. Every time it makes a move, it reads the symbol it’s now over, and asks the following question:

“Given the symbol I currently see, and my current state of mind: What symbol should I write in its place? Should I move the tape? Should I switch to a different state of mind?”

In the Turing Machine’s set of rules, there’s an answer. And that’s all it does—read and write symbols according to its set of rules and internal states.

If it sounds a bit fuzzy, check out this video of a LEGO Turing Machine that does basic addition. The “tape” is a strip of flippable LEGO pieces, but otherwise it’s a very literal interpretation of a Turing Machine:

This LittleBigPlanet Turing Machine is a little hard to follow, but is also a fairly basic Turing Machine:

A core idea in computer science is that almost every computer is really just a very complex Turing Machine. No matter how powerful your gaming rig is, its binary input and output could be perfectly simulated by a Turing Machine with an arbitrarily long tape, an arbitrarily large set of instructions and states, that moves arbitrarily quickly. Of course, it would be physically impossible to actually build such a machine out of paper tape and physical gears, but that’s why it’s a conceptual machine. Whether it’s tapes and gears or RAM and a CPU, the concepts are the same. And your PC is one--albeit a fairly more complicated machine than one built with LEGO.

So that’s why you’ll frequently see Turing Machine’s built in games—it’s a sort of proof-of-concept. It may be practically impossible to build a working CPU in a game, but if you can build a functioning Turing Machine of any complexity, you’ve proven that it’s at least conceptually possible. So even though the Turing Machine built in Conway’s Game of Life doesn’t actually much resemble a computer as you know it, understand that they’re similar at heart.

Taking Turing Machines to the Next Level

So, the next question is, what does it take to get beyond building a simple Turing Machine, and into the realm of what we would call a “computer?” The answer is another fundamental part of computer science—you need to be able to implement binary logic, and in particular you have to have a moderately efficient way to create logic gates.

A logic gate takes one or more input signals, and produces a single output single, based on a simple logic rule. For example, the AND logic gate takes two inputs, and activates its output only if both inputs are themselves activated. To illustrate logic gates, I’ve made a couple of simple circuits in Logic.ly, a logic simulator that’s free to play around with, and is a great way to try this stuff out yourself. Here’s an AND gate and an OR gate-- The switches represent inputs, the light bulbs represent outputs, and the symbols in the middle are the logic gates themselves:

Logic gates are themselves composed of transistors, in a modern integrated circuit. Minecraft logic gates, on the other hand are built out of “redstone,” which provides some basic, transistor-like functions. Here’s a Minecraft AND gate:

Image credit: The Ultimate Collection of Redstone Circuits

So, besides logic gates, what do you need to build a computer? Pretty much nothing, actually. Almost everything in a computer can be built up from simple logic gates. For example, here’s a very simple latch built out of two NOR gates:

A latch is a circuit that, when given an input signal, will keep a steady output, until it’s given a different input, then it flips and maintains a second state, until it’s switched back to the first. In other words, it stores a binary value. You might even say it has memory.

This latch, and other ones like it are the basic building blocks of active memory in a computer. If the way the latch works doesn’t make sense to you, I encourage you to build it yourself in Logic.ly and try pushing the buttons to see what happens.

Here’s the exact same latch, built in Minecraft:

Image credit: The Ultimate Collection of Redstone Circuits

Does that mean logic gates are only the basis of memory? No, they’re the basis of everything. For example, here’s a circuit, built out of AND, XOR, and OR gates, that performs binary addition. Just enter two binary numbers using the two sets of four switches, and the lights display their sum:

Note that the numbers are entered from bottom up, so in the example above, the circuit is performing 1011 + 1011 = 10110 (or, in decimal, 11 + 11 = 22).

Here’s how a “full-adder” circuit looks in Minecraft. Note that you need one full-adder per bit that you want to be able to add, so in order to create a four-bit adder like the circuit above, you would need four of these Minecraft constructions:

Image Credit: Minecraft Wiki

You can build other circuits out of logic gates that do multiplication and subtraction and other simple arithmetic on binary numbers. If you then put all those arithmetic units together, and add a control circuit (also made of logic gates), that allows you to specify which arithmetic unit to use at any given time, you’ve just built an ALU, or an arithmetic logic unit.

If you take an ALU, and add it to some memory and a clock (a regular, repeating signal that allows all the parts of the circuitry to stay synchronized and progress through multiple instructions), you’ve created a very simple CPU. For completeness, here’s a basic clock generator in Minecraft:

Image credit: The Ultimate Collection of Redstone Circuits

Of course, there’s a lot more to processor architecture than just that, but those are the basic building blocks that you need in order to start putting together something like this:

I asked Laurens Weyn, the creator of the above “Redgame 3” computer, as well as the earlier Redgame 2 and Redgame about the challenges and limits building a full, functioning PC in Minecraft. Here’s what he said:

The hardest part is designing the processor and how it will all work. Too complicated, and it would be too hard to build and use. Too simple, and the computer won't be able to do much more than the really basic stuff. Using real life CPU designs in Minecraft isn't really a good idea either, since Minecraft physics is very different from real life physics, so computer designs are made specifically to work well and fast in Minecraft.

Though Minecraft has the capability of allowing for worlds eight times as big as Earth, only a small part of it is kept loaded...circuits will only function if they are close enough to the player.

The hardest part doesn't take the longest though, it just has the biggest impact on the build. It's a process called "bussing" that's the most boring and time consuming. It's basically the process of building all the wires that connect the components. In my latest computer, I spent weeks building nothing but bussing and testing the connections!

The biggest limit is a size limit. Though Minecraft has the capability of allowing for worlds 8 times as big as earth, only a small part of it is kept loaded, the rest is stored on the hard drive until you get close to it. What this means is that circuits will only function if they are close enough to the player. Now, for most things, this limit is more than enough, but for big projects, it's something that really needs to be considered.

There's also a limit to speed. Every small electronic operation takes a tenth of a second, and while that sounds fast, a computer can need hundreds of these to do just 1 function. Modern computers can do millions of operations a second, but the fastest I've gotten to was an operation every 2 seconds or so.

In other words, just because the building blocks are simple, don’t assume that building a Minecraft PC is anything less than a massive undertaking and a huge challenge. So why do people spend all that time doing it? Weyn credits the community, saying “The Minecraft community is also like a group of scientists; constantly finding new and more compact ways to do things. You don't need to be a scientific genius to contribute to the research the community is doing. It really makes you want to try it out for yourself and see if you can invent something new.”

If you want to try building some circuits yourself, a great place to get started is the official Minecraft “Redstone Creations” forum.