Labyrinths and universal computability

The computational power of circular mazes

Circular mazes (Labyrinths)

What does a maze represent?

Picture a circular maze (labyrinth) that forces a marble outward through concentric rings by falling through gaps. At each section, there are two possible exits controlled by tilting the maze—providing a binary input:

• Clockwise (CW) = 1

• Counter‑clockwise (CCW) = 0

The marble’s current section represents our system’s entire memory. Since the marble can’t roll back to previous sections, this creates a write-only stack where old information is permanently lost.

If we only allow the marble to move forward and make binary choices, the maze essentially becomes a Finite State Automaton (FSA). Each section of the maze corresponds to a state, and the marble’s choice determines the transition to the next state. An FSA can recognize regular languages. For example, strings that must start with "101", or patterns like “any number of 0s followed by any number of 1s.”

An example path through the maze (CCW, CCW, CW)

Stacks

Let’s add the ability to tilt the maze away from you such that the marble can fall back to a ring it just came from. This simple addition turns this into a stack that can push or pop 1s or 0s from the top.

3-layer circular maze (finite)

We can already run some pretty interesting algorithms!

Checking if “( [ ] )” is a balanced string:

• Current symbol: “(“ → Go CW (go to 1)

• Current symbol: “[“ → Go CCW (from 1 to 10)

• Current symbol: “]“ → Check if we’re in a red section → Go back (from 10 to 1)

• Current symbol: “)“ → Check if we’re in a blue section → Go back (from 1 to start)

Since we’re back at the start, this string is balanced. If we had underflowed, had something left over or mismatched the section check, the string would be considered unbalanced.

Infinite tapes

Now that we’ve established that a labyrinth can simulate a stack, let’s see how they can represent a tape of 1s and 0s with a pointer keeping track of position on the tape.

We store the numbers to the left of the pointer in stack 1, and numbers to the right (inclusive) in stack 2 with the top of each stack being closest to the pointer. To simulate moving the pointer one step to the right: pop from stack 2 and push it to stack 1. For left, do the opposite.

We’ve now established that with 2 mazes (2 stacks), we can simulate a pointer and a tape.

Turing machines

By combining the maze’s ability to simulate stacks and infinite tapes, we can now represent a Turing machine (TM). This is a model powerful enough to express any computable algorithm.

A Turing machine consists of:

• A tape that stores data (symbols)

• A read/write head (pointer position) that can move left or right along the tape

• A set of states that tell it what to do when it sees a particular symbol (0 or 1)

At every step in a Turing machine we:

1. Read the current symbol

2. Based on the current state and symbol, write a new symbol at that position (or keep it the same)

3. Move head left/right & switch to a new state

But how do we decide what to do at each position? Each state is linked to a branching conditional. You can think of states like a deck of cards with this printed on them:

State N:

- If head = 0, write (0/1) at current position, move head (R/L), move to state N_0

- If head = 1, write (0/1) at current position, move head (R/L), move to state N_1

Building it with mazes

The tape & head:

• Read symbol: we look at the digit on top of stack 2 (check which section maze 2’s marble is in).

• Write symbol: we pop from stack 2 and push the new value (roll marble #2 back and choose CW or CCW for new value).

State tracking & transitions:

Instead of using a deck of cards to store the state transitions, we can represent the state machine using an additional maze #3.

Each section in Maze 3 represents a state. We don’t need to keep track of state number since the section of the marble does this for us. Similar to before, each section has two exits:

• CW → taken if the tape head reads a 1

• CCW → taken if the tape head reads a 0

Each section is labeled with:

• What to write at the current head position (0 or 1)

• Which way to move the head (left or right).

Maze 3 with random instructions (finite)

Summary of how our maze machine works:

1. Read symbol under the head (check which section marble #2 is in)

   1. If 1 → rotate maze 3 CW

   2. If 0 → rotate maze 3 CCW

2. Read State represented by what maze 3’s new section is labeled

   1. Write at head: pop from stack 2 and push the 0 or 1 (roll marble #2 back and play CW or CCW)

   2. Move head: if direction is R → pop from stack 2 and push it to stack 1 (play marble #2’s section on marble #1, roll marble 2 back)

   3. Move head: if direction is L → pop from stack 1 and push it to stack 2 (play marble #1’s section on marble #2, roll marble 1 back)

3. Repeat!

We can program this computer via labeling maze #3.

Labyrinth Turing machine

That’s it. Three mazes. Three marbles. One universal computer.