Up to this point, we’ve been talking about Turing machines — specifically, the longest-known 5- and 6-state machines that eventually halt. We ran the 5-state champion to completion and built visualizations to explore its behavior. But the discovery that it’s the longest halting machine with 5 states — and the identification of the 6-state contender — came from extensive research and formal proofs, not from running them step-by-step.

That said, I’ve built a Rust-based visualizer that can emulate these machines for trillions of steps — just enough to explore their early behavior. But even 10 trillion steps isn’t an atom in a drop of water in the ocean compared to the full runtime of the 6-state machine. And running it as far as we did doesn’t get us any closer to understanding why it runs so long.

Aside: Rust “interpreted” the Turing machines up to some point — reading their transition tables and applying the rules step by step. You could also say it “emulated” them, in that it reproduced their behavior exactly. I avoid the word “simulated”: a simulated elephant isn’t an elephant, but a simulated computer is a computer.

Returning to our central challenge: we want to understand what makes a short program run for a long time. Instead of analyzing these Turing machines, let’s construct a Rust program whose 10↑↑15 runtime is clear by design.

Our challenge is to write a small Rust program that runs for at least 10↑↑15 steps, using any amount of zero-initialized memory.

To achieve this, we’ll compute the value of 10↑↑15 in a way that guarantees the program takes at least that many steps. The ↑↑ operator is called tetration—recall from Rule Set 4 that ↑↑ stacks exponents: for example, 10↑↑3 means 10^(10^10). It’s an extremely fast-growing function. We will program it from the ground up.

Rather than rely on built-in operators, we’ll define tetration from first principles:

• Tetration, implemented by the function tetrate, as repeated exponentiation
• Exponentiation, via exponentiate, as repeated multiplication
• Multiplication, via multiply, as repeated addition
• Addition, via add, as repeated increment

Each layer builds on the one below it, using only zero-initialized memory and in-place updates.

We’ll begin at the foundation — with the simplest operation of all: increment.

Increment

Here’s our definition of increment:

fn increment(increment_acc: &mut BigUint) {
*increment_acc += 1u32;
}

For example:

let mut b = BigUint::from(4u32);
print!("++{b}\t= ");
increment(&mut b);
assert_eq!(b, BigUint::from(5u32));
println!("{b}");

Output:

++4     = 5

We’re using BigUint, a type from the num-bigint crate that represents arbitrarily large unsigned integers—limited only by available memory. In this article, we’ll pretend memory is infinite.

To keep things simple and consistent with our rules, we’ll restrict ourselves to just a few operations on BigUint:

• Creating a BigUint::ZERO
• In-place increment (+= 1u32) and decrement (-= 1u32)
• Comparison with BigUint::ZERO

We don’t allow copying, cloning, or arithmetic beyond increment and decrement. All work is in-place — no temporary values.

Each function among our computation layers follows a consistent structure: it updates a mutable accumulator in place. Most functions also take an input value a, but increment—being the simplest—does not. We give our accumulators descriptive names like increment_acc, add_acc, and so on to make each operation clear and to prepare for later sections, where multiple accumulators will appear together.

Addition

With increment defined, we next define addition as repeated incrementing.

fn add(a: u32, add_acc: &mut BigUint) {
for _ in 0..a {
// We in-line `increment` manually, to keep our work explicit.
*add_acc += 1u32;
}
}

The function adds a to add_acc by incrementing add_acc a times.

Aside: You might wonder why add doesn't just call our increment function. We could write it that way—but we're deliberately in-lining each level by hand. This keeps all loops visible, makes the control flow explicit, and helps us reason precisely about how much work our function does.

Let’s use our new add function:

let a = 2;
let mut b = BigUint::from(4u32);
print!("{a} + {b}\t= ");
add(a, &mut b);
assert_eq!(b, BigUint::from(6u32));
println!("{b}");

Output:

2 + 4     = 6

Even though BigUint supports direct addition, we don’t use it. We're deliberately working at the most primitive level possible—incrementing by 1u32—to keep the logic simple and slow, and to make the amount of work explicit.

As with increment_acc, we update add_acc in place, with no copying or temporary values. The only operation we use is += 1u32, repeated a times.

Next, we define multiplication.

Multiplication

With addition in place, we can now define multiplication as repeated addition. Here’s the function:

fn multiply(a: u32, multiply_acc: &mut BigUint) {
let mut add_acc = BigUint::ZERO;
for () in multiply_acc.count_down() {
for _ in 0..a {
add_acc += 1u32;
}
}
*multiply_acc = add_acc;
}

This multiplies a by the value of multiply_acc by adding a to add_acc once for each time multiply_acc can be decremented. Then it stores the result back into multiply_acc.

Let’s use multiply:

let a = 2;
let mut b = BigUint::from(4u32);
print!("{a} * {b}\t= ");
multiply(a, &mut b);
assert_eq!(b, BigUint::from(8u32));
println!("{b}");

Output:

2 * 4     = 8

As in the previous functions, we perform all computation in-place, using no copying, temporary values, or built-in arithmetic. The only operations allowed are incrementing, decrementing, and zero comparisons.

You might wonder what this line does:

for () in multiply_acc.count_down()

Because BigUint doesn't support loops like for _ in 0..n, we use a custom method .count_down(). It loops as long as the value is nonzero, decrementing it by 1 at each time. This gives us a controlled, in-place version of "loop n times," even when n is arbitrarily large.

We’ve built multiplication from repeated addition. Now it’s time to go a layer further: exponentiation.

Exponentiation

We define exponentiation as repeated multiplication. As before, we’ll perform every multiplication step in-place, using only zero-initialized memory.

Here’s the function:

fn exponentiate(a: u32, exponentiate_acc: &mut BigUint) {
assert!(
a > 0 || *exponentiate_acc != BigUint::ZERO,
"0^0 is undefined"
);
let mut multiply_acc = BigUint::ZERO;
multiply_acc += 1u32;
for () in exponentiate_acc.count_down() {
let mut add_acc = BigUint::ZERO;
for () in multiply_acc.count_down() {
for _ in 0..a {
add_acc += 1u32;
}
}
multiply_acc = add_acc;
}
*exponentiate_acc = multiply_acc;
}

This raises a to the power of exponentiate_acc, using only incrementing, decrementing, and loop control. We initialize multiply_acc to 1 with a single increment—because repeatedly multiplying from zero would get us nowhere. Then, for each time exponentiate_acc can be decremented, we multiply the current result (multiply_acc) by a. As with the earlier layers, we inline the multiply logic directly instead of calling the multiply function—so the control flow and step count stay fully visible.

Here’s how we use exponentiate:

let a = 2;
let mut b = BigUint::from(4u32);
print!("{a}^{b}\t= ");
exponentiate(a, &mut b);
assert_eq!(b, BigUint::from(16u32));
println!("{b}");

Output:

2^4     = 16

Aside: And how many times is += 1u32 called? Obviously at least 2⁴ times—because our result is 2⁴, and we reach it by incrementing from zero. More precisely, the number of increments is:

• 1 increment — initializing multiply_acc to one
Then we loop four times, and in each loop, we multiply the current value of multiply_acc by a = 2, using repeated addition:

• 2 increments — for multiply_acc = 1, add 2 once
• 4 increments — for multiply_acc = 2, add 2 twice
• 8 increments — for multiply_acc = 4, add 2 four times
• 16 increments — for multiply_acc = 8, add 2 eight times

That’s a total of 1 + 2 + 4 + 8 + 16 = 31 increments, which is 2⁵-1. In general, the number of calls to increment will be exponential, but the number is not the same exponential that we are computing.

With exponentiation defined, we’re ready for the top of our tower: tetration.

Tetration

Here’s the function:

fn tetrate(a: u32, tetrate_acc: &mut BigUint) {
assert!(a > 0, "we don’t define 0↑↑b");
let mut exponentiate_acc = BigUint::ZERO;
exponentiate_acc += 1u32;
for () in tetrate_acc.count_down() {
let mut multiply_acc = BigUint::ZERO;
multiply_acc += 1u32;
for () in exponentiate_acc.count_down() {
let mut add_acc = BigUint::ZERO;
for () in multiply_acc.count_down() {
for _ in 0..a {
add_acc += 1u32;
}
}
multiply_acc = add_acc;
}
exponentiate_acc = multiply_acc;
}
*tetrate_acc = exponentiate_acc;
}

This computes a ↑↑ tetrate_acc, meaning it exponentiates a by itself repeatedly, tetrate_acc times.

For each decrement of tetrate_acc, we exponentiate the current value. We in-line the entire exponentiate and multiply logic again, all the way down to repeated increments.

Here’s how we use tetrate:

let a = 2;
let mut b = BigUint::from(3u32);
print!("{a}↑↑{b}\t= ");
tetrate(a, &mut b);
assert_eq!(b, BigUint::from(16u32));
println!("{b}");

Output:

2↑↑3     = 16

As expected, this computes 2^(2^2) = 16. You can run this yourself on the Rust Playground.

We can also run tetrate on 10↑↑15. It will start running, but it won’t stop during our lifetimes — or even the lifetime of the universe:

let a = 10;
let mut b = BigUint::from(15u32);
print!("{a}↑↑{b}\t= ");
tetrate(a, &mut b);
println!("{b}");