Additionally out there: A Rust model of this text.
talks about making Python packages sooner [1, 2, 3], however what if we pursue the alternative purpose? Let’s discover the right way to make them slower — absurdly slower. Alongside the way in which, we’ll study the character of computation, the function of reminiscence, and the size of unimaginably giant numbers.
Our guiding problem: write quick Python packages that run for a very very long time.
To do that, we’ll discover a sequence of rule units — every one defining what sort of packages we’re allowed to write down, by putting constraints on halting, reminiscence, and program state. This sequence isn’t a development, however a sequence of shifts in perspective. Every rule set helps reveal one thing completely different about how easy code can stretch time.
Listed here are the rule units we’ll examine:
- Something Goes — Infinite Loop
- Should Halt, Finite Reminiscence — Nested, Fastened-Vary Loops
- Infinite, Zero-Initialized Reminiscence — 5-State Turing Machine
- Infinite, Zero-Initialized Reminiscence — 6-State Turing Machine (>10↑↑15 steps)
- Infinite, Zero-Initialized Reminiscence — Plain Python (compute 10↑↑15 with out Turing machine emulation)
Apart: 10↑↑15 is just not a typo or a double exponent. It’s a quantity so giant that “exponential” and “astronomical” don’t describe it. We’ll outline it in Rule Set 4.
We begin with essentially the most permissive rule set. From there, we’ll change the foundations step-by-step to see how completely different constraints form what long-running packages appear like — and what they will educate us.
Rule Set 1: Something Goes — Infinite Loop
We start with essentially the most permissive guidelines: this system doesn’t have to halt, can use limitless reminiscence, and may include arbitrary code.
If our solely purpose is to run without end, the answer is fast:
whereas True:
crossThis program is brief, makes use of negligible reminiscence, and by no means finishes. It satisfies the problem in essentially the most literal approach — by doing nothing without end.
In fact, it’s not fascinating — it does nothing. However it provides us a baseline: if we take away all constraints, infinite runtime is trivial. Within the subsequent rule set, we’ll introduce our first constraint: this system should finally halt. Let’s see how far we will stretch the working time below that new requirement — utilizing solely finite reminiscence.
Rule Set 2: Should Halt, Finite Reminiscence — Nested, Fastened-Vary Loops
If we would like a program that runs longer than the universe will survive after which halts, it’s simple. Simply write two nested loops, every counting over a hard and fast vary from 0 to 10¹⁰⁰−1:
for a in vary(10**100):
for b in vary(10**100):
if b % 10_000_000 == 0:
print(f"{a:,}, {b:,}")You’ll be able to see that this program halts after 10¹⁰⁰ × 10¹⁰⁰ steps. That’s 10²⁰⁰. And — ignoring the print—this program makes use of solely a small quantity of reminiscence to carry its two integer loop variables—simply 144 bytes.
My desktop pc runs this program at about 14 million steps per second. However suppose it may run at Planck pace (the smallest significant unit of time in physics). That might be about 10⁵⁰ steps per yr — so 10¹⁵⁰ years to finish.
Present cosmological fashions estimate the warmth loss of life of the universe in 10¹⁰⁰ years, so our program will run about 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 occasions longer than the projected lifetime of the universe.
Apart: Sensible considerations about working a program past the top of the universe are exterior the scope of this text.
For an added margin, we will use extra reminiscence. As an alternative of 144 bytes for variables, let’s use 64 gigabytes — about what you’d discover in a well-equipped private pc. That’s about 500 million occasions extra reminiscence, which provides us about one billion variables as an alternative of two. If every variable iterates over the complete 10¹⁰⁰ vary, the whole variety of steps turns into roughly 10¹⁰⁰^(10⁹), or about 10^(100 billion) steps. At Planck pace — roughly 10⁵⁰ steps per yr — that corresponds to 10^(100 billion − 50) years of computation.
Can we do higher? Effectively, if we permit an unrealistic however fascinating rule change, we will do a lot, significantly better.
Rule Set 3: Infinite, Zero-Initialized Reminiscence — 5-State Turing Machine
What if we permit infinite reminiscence — as long as it begins out totally zero?
Apart: Why don’t we permit infinite, arbitrarily initialized reminiscence? As a result of it trivializes the problem. For instance, you might mark a single byte far out in reminiscence with a
0x01—say, at place 10¹²⁰—and write a tiny program that simply scans till it finds it. That program would take an absurdly very long time to run — however it wouldn’t be fascinating. The slowness is baked into the information, not the code. We’re after one thing deeper: small packages that generate their very own lengthy runtimes from easy, uniform beginning situations.
My first thought was to make use of the reminiscence to depend upward in binary:
0
1
10
11
100
101
110
111
...We will try this — however how do we all know when to cease? If we don’t cease, we’re violating the “should halt” rule. So, what else can we attempt?
Let’s take inspiration from the daddy of Laptop Science, Alan Turing. We’ll program a easy summary machine — now often called a Turing machine — below the next constraints:
- The machine has infinite reminiscence, laid out as a tape that extends endlessly in each instructions. Every cell on the tape holds a single bit: 0 or 1.
- A learn/write head strikes throughout the tape. On every step, it reads the present bit, writes a brand new bit (0 or 1), and strikes one cell left or proper.
- The machine additionally has an inner variable referred to as state, which may maintain certainly one of n values. For instance, with 5 states, we would identify the attainable values A, B, C, D, and E—plus a particular halting state H, which we don’t depend among the many 5. The machine at all times begins within the first state, A.
We will specific a full Turing machine program as a transition desk. Right here’s an instance we’ll stroll via step-by-step.
- Every row corresponds to the present tape worth (0 or 1).
- Every column corresponds to the present state (A via E).
- Every entry within the desk tells the machine what to do subsequent:
- The first character is the bit to write down (0 or 1)
- The second is the route to maneuver (L for left, R for proper)
- The third is the subsequent state to enter (A, B, C, D, E, or H, the place H is the particular halting state).
Now that we’ve outlined the machine, let’s see the way it behaves over time.
We’ll refer to every second in time — the complete configuration of the machine and tape — as a step. This contains the present tape contents, the pinnacle place, and the machine’s inner state (like A, B, or H).
Under is Step 0. The pinnacle is pointing to a 0 on the tape, and the machine is in state A.
Taking a look at row 0, column A in this system desk, we discover the instruction 1RB. Which means:
- Write 1 to the present tape cell.
- Transfer the pinnacle Proper.
- Enter state B.
Step 0:
This places us in Step 1:
The machine is now in state B, pointing on the subsequent tape cell (once more 0).
What is going to occur if we let this Turing machine preserve working? It should run for precisely 47,176,870 steps — after which halt.
Apart: With a Google sign up, you’ll be able to run this your self by way of a Python pocket book on Google Colab. Alternatively, you’ll be able to copy and run the pocket book domestically by yourself pc by downloading it from GitHub.
That quantity 47,176,870 is astonishing by itself, however seeing the complete run makes it extra tangible. We will visualize the execution utilizing a space-time diagram, the place every row reveals the tape at a single step, from prime (earliest) to backside (newest). Within the picture:
- The primary row is clean — it reveals the all-zero tape earlier than the machine takes its first step.
- 1s are proven in orange.
- 0s are proven in white.
- Mild orange seems the place 0s and 1s are so shut collectively they mix.
In 2023, a web-based group of newbie researchers organized via bbchallenge.org proved that that is the longest-running 5-state Turing machine that finally halts.
Need to see this Turing machine in movement? You’ll be able to watch the complete 47-million-step execution unfold on this pixel-perfect video:
Or work together with it instantly utilizing the Busy Beaver Blaze internet app.
The video generator and internet app are a part of busy-beaver-blaze, the open-source Python & Rust mission that accompanies this text.
It’s laborious to consider that such a small machine can run 47 million steps and nonetheless halt. However it will get much more astonishing: the group at bbchallenge.org discovered a 6-state machine with a runtime so lengthy it may well’t even be written with extraordinary exponents.
Rule Set 4: Infinite, Zero-Initialized Reminiscence — 6-State Turing Machine (>10↑↑15 steps)
As of this writing, the longest working (however nonetheless halting) 6-state Turing machine recognized to humankind is:
A B C D E F
0 1RB 1RC 1LC 0LE 1LF 0RC
1 0LD 0RF 1LA 1RH 0RB 0REHere’s a video displaying its first 10 trillion steps:
And right here you’ll be able to run it interactively by way of an internet app.
So, if we’re affected person — comically affected person — how lengthy will this Turing machine run? Greater than 10↑↑15 the place “10 ↑↑ 15” means:
That is not the identical as 10¹⁵ (which is only a common exponent). As an alternative:
- 10¹ = 10
- 10¹⁰ = 10,000,000,000
- 10^10^10 is 10¹⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰, already unimaginably giant.
- 10↑↑4 is so giant that it vastly exceeds the variety of atoms within the observable universe.
- 10↑↑15 is so giant that writing it in exponent notation turns into annoying.
Pavel Kropitz introduced this 6-state machine on Might 30, 2022. Shawn Ligocki has an incredible write up explaining each his and Pavel’s discoveries. To show that these machines run so lengthy after which halt, researchers used a mixture of evaluation and automatic instruments. Reasonably than simulating each step, they recognized repeating constructions and patterns that may very well be confirmed — utilizing formal, machine-verified proofs — to finally result in halting.
Up so far, we’ve been speaking about Turing machines — particularly, the longest-known 5- and 6-state machines that finally halt. We ran the 5-state champion to completion and watched visualizations to discover its conduct. However the discovery that it’s the longest halting machine with 5 states — and the identification of the 6-state contender — got here from intensive analysis and formal proofs, not from working them step-by-step.
That mentioned, the Turing machine interpreter I inbuilt Python can run for hundreds of thousands of steps, and the visualizer written in Rust can deal with trillions (see GitHub). However even 10 trillion steps isn’t an atom in a drop of water within the ocean in comparison with the complete runtime of the 6-state machine. And working it that far doesn’t get us any nearer to understanding why it runs so lengthy.
Apart: Python and Rust “interpreted” the Turing machines as much as some level — studying their transition tables and making use of the foundations step-by-step. You may additionally say they “emulated” them, in that they reproduced their conduct precisely. I keep away from the phrase “simulated”: a simulated elephant isn’t an elephant, however a simulated pc is a pc.
Returning to our central problem: we wish to perceive what makes a brief program run for a very long time. As an alternative of analyzing these Turing machines, let’s assemble a Python program whose 10↑↑15 runtime is clear by design.
Rule Set 5: Infinite, Zero-Initialized Reminiscence — Plain Python (compute 10↑↑15 with out Turing machine emulation)
Our problem is to write down a small Python program that runs for at the least 10↑↑15 steps, utilizing any quantity of zero-initialized reminiscence.
To realize this, we’ll compute the worth of 10↑↑15 in a approach that ensures this system takes at the least that many steps. The ↑↑ operator is known as tetration—recall from Rule Set 4 that ↑↑ stacks exponents: for instance, 10↑↑3 means 10^(10^10). It’s a particularly fast-growing perform. We’ll program it from the bottom up.
Reasonably than depend on built-in operators, we’ll outline tetration from first ideas:
- Tetration, applied by the perform
tetrate, as repeated exponentiation - Exponentiation, by way of
exponentiate, as repeated multiplication - Multiplication, by way of
multiply, as repeated addition - Addition, by way of
add, as repeated increment
Every layer builds on the one under it, utilizing solely zero-initialized reminiscence and in-place updates.
We’ll start on the basis — with the only operation of all: increment.
Increment
Right here’s our definition of increment and an instance of its use:
from gmpy2 import xmpz
def increment(acc_increment):
assert is_valid_accumulator(acc_increment), "not a legitimate accumulator"
acc_increment += 1
def is_valid_accumulator(acc):
return isinstance(acc, xmpz) and acc >= 0
b = xmpz(4)
print(f"++{b} = ", finish="")
increment(b)
print(b)
assert b == 5Output:
++4 = 5We’re utilizing xmpz, a mutable arbitrary-precision integer sort supplied by the gmpy2 library. It behaves like Python’s built-in int when it comes to numeric vary—restricted solely by reminiscence—however in contrast to int, it helps in-place updates.
To remain true to the spirit of a Turing machine and to maintain the logic minimal and observable, we prohibit ourselves to only a few operations:
- Creating an integer with worth 0 (
xmpz(0)) - In-place increment (
+= 1) and decrement (-= 1) - Evaluating with zero
All arithmetic is finished in-place, with no copies and no non permanent values. Every perform in our computation chain modifies an accumulator instantly. Most capabilities additionally take an enter worth a, however increment—being essentially the most fundamental—doesn’t. We use descriptive names like increment_acc, add_acc, and so forth to make the operation clear and to help later capabilities the place a number of accumulators will seem collectively.
Apart: Why not use Python’s built-in
intsort? It helps arbitrary precision and may develop as giant as your reminiscence permits. However it’s additionally immutable, that means any replace like+= 1creates a new integer object. Even should you assume you’re modifying a big quantity in place, Python is definitely copying all of its inner reminiscence—regardless of how massive it’s.
For instance:
x = 10**100
y = x
x += 1
assert x == 10**100 + 1 and y == 10**100Regardless that
xandybegin out similar,x += 1creates a brand new object—leavingyunchanged. This conduct is ok for small numbers, however it violates our guidelines about reminiscence use and in-place updates. That’s why we usegmpy2.xmpz, a mutable arbitrary-precision integer that really helps environment friendly, in-place adjustments.
Addition
With increment outlined, we subsequent outline addition as repeated incrementing.
def add(a, add_acc):
assert is_valid_other(a), "not a legitimate different"
assert is_valid_accumulator(add_acc), "not a legitimate accumulator"
for _ in vary(a):
add_acc += 1
def is_valid_other(a):
return isinstance(a, int) and a >= 0
a = 2
b = xmpz(4)
print(f"Earlier than: id(b) = {id(b)}")
print(f"{a} + {b} = ", finish="")
add(a, b)
print(b)
print(f"After: id(b) = {id(b)}") # ← examine object IDs
assert b == 6Output:
Earlier than: id(b) = 2082778466064
2 + 4 = 6
After: id(b) = 2082778466064The perform provides a to add_acc by incrementing add_acc one step at a time, a occasions. The earlier than and after ids are the identical, displaying that no new object was created—add_acc was really up to date in place.
Apart: You would possibly surprise why
adddoesn’t simply name ourincrementperform. We may write it that approach—however we’re intentionally inlining every stage by hand. This retains all loops seen, makes management move express, and helps us cause exactly about how a lot work every perform performs.
Regardless that gmpy2.xmpz helps direct addition, we don’t use it. We’re working on the most primitive stage attainable—incrementing by 1—to maintain the logic easy, deliberately gradual, and to make the quantity of labor express.
As with increment_acc, we replace add_acc in place, with no copying or non permanent values. The one operation we use is += 1, repeated a occasions.
Subsequent, we outline multiplication.
Multiplication
With addition in place, we will now outline multiplication as repeated addition. Right here’s the perform and instance utilization. In contrast to add and increment, this one builds up a brand new xmpz worth from zero and returns it.
def multiply(a, multiply_acc):
assert is_valid_other(a), "not a legitimate different"
assert is_valid_accumulator(multiply_acc), "not a legitimate accumulator"
add_acc = xmpz(0)
for _ in count_down(multiply_acc):
for _ in vary(a):
add_acc += 1
return add_acc
def count_down(acc):
assert is_valid_accumulator(acc), "not a legitimate accumulator"
whereas acc > 0:
acc -= 1
yield
a = 2
b = xmpz(4)
print(f"{a} * {b} = ", finish="")
c = multiply(a, b)
print(c)
assert c == 8
assert b == 0Output:
2 * 4 = 8This multiplies a by the worth of multiply_acc by including a to add_acc as soon as for each time multiply_acc will be decremented. The result’s returned after which assigned to c. The unique multiply_acc is decremented to zero and consumed within the course of.
You would possibly surprise what this line does:
for _ in count_down(multiply_acc):Whereas xmpz technically works with vary(), doing so converts it to a regular Python int, which is immutable. That triggers a full copy of its inner reminiscence—an costly operation for big values. Worse, every decrement step would contain allocating a brand new integer and copying all earlier bits, so what needs to be a linear loop finally ends up doing quadratic complete work. Our customized count_down() avoids all that by decrementing in place, yielding management with out copying, and sustaining predictable reminiscence use.
We’ve constructed multiplication from repeated addition. Now it’s time to go a layer additional: exponentiation.
Exponentiation
We outline exponentiation as repeated multiplication. As earlier than, we carry out all work utilizing solely incrementing, decrementing, and in-place reminiscence. As with multiply, the ultimate result’s returned whereas the enter accumulator is consumed.
Right here’s the perform and instance utilization:
def exponentiate(a, exponentiate_acc):
assert is_valid_other(a), "not a legitimate different"
assert is_valid_accumulator(exponentiate_acc), "not a legitimate accumulator"
assert a > 0 or exponentiate_acc != 0, "0^0 is undefined"
multiply_acc = xmpz(0)
multiply_acc += 1
for _ in count_down(exponentiate_acc):
add_acc = xmpz(0)
for _ in count_down(multiply_acc):
for _ in vary(a):
add_acc += 1
multiply_acc = add_acc
return multiply_acc
a = 2
b = xmpz(4)
print(f"{a}^{b} = ", finish="")
c = exponentiate(a, b)
print(c)
assert c == 16
assert b == 0Output:
2^4 = 16This raises a to the ability of exponentiate_acc, utilizing solely incrementing, decrementing, and loop management. We initialize multiply_acc to 1 with a single increment—as a result of repeatedly multiplying from zero would get us nowhere. Then, for every time exponentiate_acc will be decremented, we multiply the present outcome (multiply_acc) by a. As with the sooner layers, we inline the multiply logic instantly as an alternative of calling the multiply perform—so the management move and step depend keep totally seen.
Apart: And what number of occasions is
+= 1referred to as? Clearly at the least 2⁴ occasions—as a result of our result’s 2⁴, and we attain it by incrementing from zero. Extra exactly, the variety of increments is:• 1 increment — initializing
multiply_accto 1Then we loop 4 occasions, and in every loop, we multiply the present worth of
multiply_accbya = 2, utilizing repeated addition:
• 2 increments — formultiply_acc = 1, add 2 as soon as
• 4 increments — formultiply_acc = 2, add 2 twice
• 8 increments — formultiply_acc = 4, add 2 4 occasions
• 16 increments — formultiply_acc = 8, add 2 eight occasions
That’s a complete of 1 + 2 + 4 + 8 + 16 = 31 increments, which is 2⁵-1. Basically, the variety of calls to increment will likely be exponential, however the quantity is just not the identical exponential that we’re computing.
With exponentiation outlined, we’re prepared for the highest of our tower: tetration.
Tetration
Right here’s the perform and instance utilization:
def tetrate(a, tetrate_acc):
assert is_valid_other(a), "not a legitimate different"
assert is_valid_accumulator(tetrate_acc), "not a legitimate accumulator"
assert a > 0, "we do not outline 0↑↑b"
exponentiate_acc = xmpz(0)
exponentiate_acc += 1
for _ in count_down(tetrate_acc):
multiply_acc = xmpz(0)
multiply_acc += 1
for _ in count_down(exponentiate_acc):
add_acc = xmpz(0)
for _ in count_down(multiply_acc):
for _ in vary(a):
add_acc += 1
multiply_acc = add_acc
exponentiate_acc = multiply_acc
return exponentiate_acc
a = 2
b = xmpz(3)
print(f"{a}↑↑{b} = ", finish="")
c = tetrate(a, b)
print(c)
assert c == 16 # 2^(2^2)
assert b == 0 # Verify tetrate_acc is consumedOutput:
2↑↑3 = 16This computes a ↑↑ tetrate_acc, that means it exponentiates a by itself repeatedly, tetrate_acc occasions.
For every decrement of tetrate_acc, we exponentiate the present worth. We in-line the complete exponentiate and multiply logic once more, all the way in which right down to repeated increments.
As anticipated, this computes 2^(2^2) = 16. With a Google sign-in, you’ll be able to run this your self by way of a Python pocket book on Google Colab. Alternatively, you’ll be able to copy the pocket book from GitHub after which run it by yourself pc.
We will additionally run tetrate on 10↑↑15. It should begin working, however it gained’t cease throughout our lifetimes — and even the lifetime of the universe:
a = 10
b = xmpz(15)
print(f"{a}↑↑{b} = ", finish="")
c = tetrate(a, b)
print(c)Let’s examine this tetrate perform to what we discovered within the earlier Rule Units.
Rule Set 1: Something Goes — Infinite Loop
Recall our first perform:
whereas True:
crossIn contrast to this infinite loop, our tetrate perform finally halts — although not anytime quickly.
Rule Set 2: Should Halt, Finite Reminiscence — Nested, Fastened-Vary Loops
Recall our second perform:
for a in vary(10**100):
for b in vary(10**100):
if b % 10_000_000 == 0:
print(f"{a:,}, {b:,}")Each this perform and our tetrate perform include a hard and fast variety of nested loops. However tetrate differs in an essential approach: the variety of loop iterations grows with the enter worth. On this perform, in distinction, every loop runs from 0 to 10¹⁰⁰-1—a hardcoded certain. In distinction, tetrate’s loop bounds are dynamic — they develop explosively with every layer of computation.
Rule Units 3 & 4: Infinite, Zero-Initialized Reminiscence — 5- and 6-State Turing Machines
In comparison with the Turing machines, our tetrate perform has a transparent benefit: we will instantly see that it’s going to name += 1 greater than 10↑↑15 occasions. Even higher, we will additionally see — by building — that it halts.
What the Turing machines provide as an alternative is a less complicated, extra common mannequin of computation — and maybe a extra principled definition of what counts as a “small program.”
Conclusion
So, there you may have it — a journey via writing absurdly gradual packages. Alongside the way in which, we explored the outer edges of computation, reminiscence, and efficiency, utilizing all the things from deeply nested loops to Turing machines to a hand-inlined tetration perform.
Right here’s what shocked me:
- Nested loops are sufficient.
In the event you simply need a quick program that halts after outliving the universe, two nested loops with 144 bytes of reminiscence will do the job. I hadn’t realized it was that easy. - Turing machines escalate quick.
The soar from 5 to six states unleashes a dramatic leap in complexity and runtime. Additionally, the significance of beginning with zero-initialized reminiscence is apparent on reflection — however it wasn’t one thing I’d thought of earlier than. - Python’s
intsort can kill efficiency
Sure, Python integers are arbitrary precision, which is nice. However they’re additionally immutable. Which means each time you do one thing likex += 1, Python silently allocates a brand-new integer object—copying all of the reminiscence ofx, regardless of how massive it’s. It feels in-place, however it’s not. This conduct turns efficient-looking code right into a efficiency entice when working with giant values. To get round this, we use thegmpy2.xmpzsort—a mutable, arbitrary-precision integer that permits true in-place updates. - There’s one thing past exponentiation — and it’s referred to as tetration.
I didn’t know this. I wasn’t acquainted with the ↑↑ notation or the concept exponentiation may itself be iterated to kind one thing even faster-growing. It was stunning to learn the way compactly it may well specific numbers which can be in any other case unthinkably giant.
And since I do know you’re asking — sure, there’s one thing past tetration too. It’s referred to as pentation, then hexation, and so forth. These are half of an entire hierarchy often called hyperoperations. There’s even a metageneralization: techniques just like the Ackermann perform and fast-growing hierarchies seize whole households of those capabilities and extra. - Writing Tetration with Specific Loops Was Eye-Opening
I already knew that exponentiation is repeated multiplication, and so forth. I additionally knew this may very well be written recursively. What I hadn’t seen was how cleanly it may very well be written as nested loops, with out copying values and with strict in-place updates.
Thanks for becoming a member of me on this journey. I hope you now have a clearer understanding of how small Python packages can run for an astonishingly very long time — and what that reveals about computation, reminiscence, and minimal techniques. We’ve seen packages that halt solely after the universe dies, and others that run even longer.
Please comply with Carl on In the direction of Information Science and on @carlkadie.bsky.social. I write on scientific programming in Python and Rust, machine studying, and statistics. I have a tendency to write down about one article per thirty days.