Does a Three-Dimensional Android Dream of Four-Dimensional Sheep?

Introduction

A computer is a mathematical structure cast in silicon. But what does it mean to treat a computer as a mathematical object rather than just a piece of hardware?

We can work with it just as we would with a square, a triangle, or a coordinate system: define its rules, change its structure, and see what follows.

To explore that idea, we’ll build computers in two, three, and four dimensions, and write instructions for them.

We’ll use the classic Turing machine as our starting point. First, let’s briefly look at how it works and how this abstraction relates to a modern computer.

The Core of the Machine

Imagine an unbounded tape divided into cells. Each cell can hold a symbol, and a head moves along the tape: it reads a symbol, can replace it with another, and moves one cell to the left or right.

The symbols can be anything: letters, digits, hieroglyphs, tally marks, or circles. A standard Turing machine only requires us to choose a finite set of symbols in advance — an alphabet that includes a symbol for a blank cell. Zeros and ones have no special status here.

The machine has an internal state and a table of rules. Each rule specifies an action based on two things: the current state and the symbol being read. For example: “In state A, when you encounter a circle, replace it with a tally mark, move right, and switch to state B.” Computation is built out of these elementary steps.

Suppose we agree to represent numbers by counting tally marks: ||| means three. We place the head on the first mark and give it this program: move right as long as you encounter tally marks; when you reach a blank cell, write one more and halt. The result is ||||—four. The machine has added one, even though it has neither a built-in calculator nor a special addition instruction.

Formula and Silicon

Let’s mentally rearrange how this machine is organized.

Replace the tape with addressable memory. Number the cells and allow the machine to access them by their numbers — their addresses — without passing through every cell in between. Add a few working cells called registers, along with an arithmetic logic unit, so that we no longer have to build every addition out of lengthy movements of the head.

Put the program in the same memory as the data. To do this, encode instructions as symbols: “load a value,” “add,” “store the result,” “jump to a specified address.” A control unit will read these entries and carry out the corresponding actions. Together with the registers and the arithmetic logic unit, it forms our simplified processor.

The idea of a program stored in memory is not foreign to the original model, either: a universal Turing machine can read an encoded description of another machine from its tape and reproduce that machine’s behavior.

Add a program counter — a register holding the address of the next instruction. The processor now repeats this cycle:

Fetch an instruction → decode it → execute it → determine the address of the next instruction.

Instructions normally execute in sequence. But a conditional jump instruction can change the order depending on the result of a computation — and that gives us branches and loops.

For example, a program that adds two numbers might look like this:

0: Load the value from memory cell 100 into register A
1: Add the value from memory cell 101 to A
2: Store A in memory cell 102
3: Halt

The instructions occupy cells 0–3, the input data is in 100 and 101, and the result goes into 102. The program and the data share the same memory—this is a key principle of the von Neumann architecture. Add input and output, and we have a recognizable computer design.

Zero, One

So far, we have been working with symbols and rules. To implement this construction physically, we need to map the symbols to distinguishable states of a device.

In an electronic circuit, it is convenient to use two voltage ranges: “low” and “high,” labeled 0 and 1. It is easier to distinguish these reliably, with some tolerance for noise, than to distinguish many closely spaced levels. Sequences of these binary symbols can encode numbers, letters, and processor instructions alike.

A computer does not have to be binary: other ways of representing information are possible. Binary is a convenient engineering choice, not a mathematical requirement for computation. What’s more, 0 and 1 themselves do not necessarily represent numbers: their meaning depends on the encoding and how they are processed.

Adding Dimensions

In an ordinary Turing machine, memory is organized as a one-dimensional tape: each cell has two neighbors, and the head moves left or right. But what stops us from arranging the cells differently? Here, dimensions describe the layout of the memory tape.

In the one-dimensional version, it is simply a line of cells along which we can move up or down. In two dimensions, it becomes an infinite matrix — a grid of cells. In three dimensions, the tape is gone altogether: we have a lattice of cubes, and the head can move between neighboring cubes — forward and backward, left and right, as well as up and down.

In four dimensions, the storage becomes an unbounded lattice whose cells can be thought of as tesseracts — the four-dimensional counterparts of cubes. Depicting such an object as clearly as a cube is no longer easy: we have to use projections.

Mathematically, however, it has a perfectly definite description. Just as the boundary of a three-dimensional cube consists of six two-dimensional squares, the boundary of a tesseract consists of eight three-dimensional cubes.

The machine itself, though, does not need to visualize anything. Each cell’s address now contains four coordinates instead of three. The head moves by changing one of them by one unit in the positive or negative direction, giving it eight possible directions. The rules for reading and writing symbols remain the same.

Let’s keep everything else: a finite set of arbitrary symbols, internal states, and a table of rules. The head still reads one cell, can change its contents, and then moves according to a rule. Only the geometry of its routes will change.

Graph Paper

Replace the tape with an unbounded grid. The head’s position is now given by two integer coordinates — (x, y). Instead of two directions of movement, we have four: left, right, up, and down. Moving diagonally in a single step is not allowed. We have a two-dimensional Turing machine.

For example, let’s write the symbols ABC in one row and teach the machine to copy them into the neighboring row. It follows the same route for each symbol: read it, remember it using the internal state, move one cell up, write a copy, return down, and move right. When it encounters a blank cell in the original row, it halts.

Before:         After:

· · · ·         A B C ·
A B C ·         A B C ·

A dot denotes a blank cell. The head cannot see an entire row at once and does not copy it in a single action: the result emerges from individual reads, writes, and movements between neighboring cells.

A Lattice of Cubes

Now replace the grid with an unbounded lattice of cells, which we can picture as a space filled with little cubes. Each cell has three coordinates — (x, y, z). The four previous directions are joined by two more: along the third axis, in the positive and negative directions.

The movement rule becomes: in a single step, one coordinate changes by one unit while the others remain unchanged. For example:

(3, 2, 0) → (3, 2, 1)

Let’s extend our copying program. First, the machine turns the row ABC into two identical rows, as in the previous example. Then it copies the resulting rectangle into the neighboring layer along the z axis. This gives us a 3 × 2 × 2 block: two layers, each containing two rows of ABC.

A Lattice of Tesseracts

The next step is no harder mathematically: add a coordinate, w. A cell's address now looks like (x, y, z, w), and the number of movement directions rises to eight. We can extend this construction to any fixed finite number of dimensions: cells are identified by tuples of integer coordinates and contain symbols from a finite alphabet.

A four-dimensional lattice is hard to visualize, but we do not need to visualize it to work with it. We can think of it as a sequence of three-dimensional spaces labeled by their values of w. The transition

(3, 2, 1, 0) → (3, 2, 1, 1)

moves the head to a cell with the same x, y, and z, but in the neighboring space along the fourth coordinate.

The program can now copy the 3 × 2 × 2 block from the layer w = 0 into the layer w = 1. The result is a four-dimensional 3 × 2 × 2 × 2 block containing eight copies of the original row.

On Simulation

An interesting consequence of the Turing machine’s design is that a lower-dimensional machine can simulate a higher-dimensional one. It is precisely this ability to simulate one another that makes Turing machines with different numbers of dimensions equivalent in computational power, though not necessarily in speed.

The other direction is straightforward: a two-dimensional machine can simply use a single row to simulate the one-dimensional classic. But let’s look at how a one-dimensional memory tape could simulate a two-dimensional one. The trick is to replace the cells’ spatial arrangement with their addresses.

Suppose our two-dimensional memory contains three symbols: A in cell (0,0), B in cell (1,0), and C in cell (1,1). Instead of drawing a grid, we write the following on an ordinary tape:

#0,0:A #1,0:B #1,1:C#

Each entry means “cell coordinates — cell contents,” and # separates the entries. For example, 1,0:B reads as “the cell at coordinates (1,0) contains the symbol B.”

An entire address does not fit into a single tape cell. Each character occupies its own cell: the number 123 is written as three digits, and a negative coordinate also needs a minus sign. The alphabet therefore remains finite, even though we can write arbitrarily large coordinates. This is consistent with the ordinary Turing machine model: a finite set of symbols, but an unbounded tape.

What about the rest of the infinite plane? We can agree that any cell whose coordinates are absent from the list is blank.

Besides the memory contents, we need to store the simulated machine’s current state and the coordinates of its head. Let’s add those at the beginning:

q0;1,0;# 0,0:A# 1,0:B# 1,1:C#

This means: “The machine is in state q0, its head is at cell (1,0), and the memory description follows.”

Suppose the simulated machine has this rule:

In state q0, upon reading B, write D, move up, and switch to state q1.

We can build a table of these rules into the simulator’s program. Alternatively, we can write it on the tape as well and teach the simulator to read it as data: this is exactly the principle behind a universal Turing machine.

The one-dimensional simulator now does the following:

• Finds the matching entry. It scans the list sequentially, comparing the coordinates with the stored head position, (1,0). It finds 1,0:B.
• Applies the rule. It replaces B with D.
• Updates the head and state descriptions. We have agreed that moving up increases the second coordinate: (1,0) becomes (1,1), and q0 becomes q1.

The tape now looks like this:

q1;1,1;# 0,0:A# 1,0:D# 1,1:C#

The two-dimensional head has taken a step upward, even though the simulator’s real head has only been moving left and right all this time. On the next simulated step, it will look for the entry 1,1:C.

To compare two addresses, it can compare their symbols one by one, moving between the entries and marking the characters it has already checked. To increment a coordinate, it needs to modify the written number, handling any necessary carry. Comparison, copying, and adding one are all implemented using ordinary rules for reading, writing, and moving along the tape.

Conclusion

Thousands of years ago, a nameless person was sitting and resting. Perhaps he lived in Mesopotamia, India, China, or on the shores of the Mediterranean — or somewhere in the Germanic forests, or, for that matter, in either of the Americas, or in Africa.

In any case, this person was resting, and he noticed the wooden board he had just eaten from. He imagined several copies of it, then arranged them to form a small box. He found the result intriguing.

Perhaps he then wondered how he could describe this little game of imagination on parchment, so he could return to it later and maybe show it to people he knew.

He could define the first board as a set of points, describe the space containing them using a three-dimensional coordinate system, and move the cloned sets of points along its axes.

Perhaps this was how, entirely by accident, people discovered a previously unknown space and began to explore it — like someone carrying a torch who has stumbled upon an ancient, unexplored dungeon.

After centuries of exploring this space, the British mathematician Turing tried to formalize the notion of an algorithm in order to solve a well-known mathematical problem of his time, which can be stated as follows:

Can we devise a universal mechanical algorithm that takes an arbitrary mathematical statement as input and determines, in a finite number of steps, whether it follows from a given set of axioms?

In the course of this work, Turing managed to formalize the work of a human computer — a common occupation at the time — as an abstract machine with a one-dimensional memory tape and a head that could move left and right.

This particular mathematical structure was named the Turing machine, and its operating principle became the foundation of how computers work to this day.

After centuries and even millennia of exploring the mathematical dungeon, people unearthed something whose impact on this planet might rank alongside the emergence of the first single-celled life.

And we may well be the generation that gets to see it with our own eyes.