THE FOLD / GRIND / THE HOT LOOP / THE TORTOISE
THE TORTOISE
Floyd's tortoise & hare — catch a loop with no memory
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Floyd’s tortoise and hare. Follow a sequence where each value points to the next: x, f(x), f(f(x))… In a finite world it must eventually repeat — the path is a ‘ρ’: a tail that runs into a loop. How do you detect the loop, and find where it starts, using no memory of the path?
Two pointers. The tortoise steps once per tick; the hare steps twice. If there is a loop, the fast one laps the slow one and they land on the same node — a collision that proves the cycle. A second phase — reset one pointer to the start and step both by one — meets exactly at the cycle entry (a small, lovely number-theory fact about the gap).
LIT verified live: on thousands of random pointer-maps, Floyd recovers the cycle start μ and the cycle length λ and they match a brute-force visited-set computation every time (window.__tortoise.allMatch). FIG ‘a race’ is the picture; the O(1)-memory detection, and the exact μ and λ, are the real algorithm.
Two pointers. The tortoise steps once per tick; the hare steps twice. If there is a loop, the fast one laps the slow one and they land on the same node — a collision that proves the cycle. A second phase — reset one pointer to the start and step both by one — meets exactly at the cycle entry (a small, lovely number-theory fact about the gap).
LIT verified live: on thousands of random pointer-maps, Floyd recovers the cycle start μ and the cycle length λ and they match a brute-force visited-set computation every time (window.__tortoise.allMatch). FIG ‘a race’ is the picture; the O(1)-memory detection, and the exact μ and λ, are the real algorithm.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE HOT LOOP — the grind domain of the loop that runs and runs. Floyd’s trick is how you catch a loop from the inside without a map. AVAN (AI) built the instrument: the ρ-shaped graph, the two racers, the entry-finding phase, the brute-force cross-check.
The weave: David names the seat (the loop); I make the catch visible and the numbers checkable — the ρ laid out in 1D, the race and entry-find in 2D, the loop turning with its two chasers in 3D. The sphere is the seam. Credit: Robert W. Floyd (the tortoise-and-hare cycle detection).
The weave: David names the seat (the loop); I make the catch visible and the numbers checkable — the ρ laid out in 1D, the race and entry-find in 2D, the loop turning with its two chasers in 3D. The sphere is the seam. Credit: Robert W. Floyd (the tortoise-and-hare cycle detection).
3 ONE DIMENSION
The ρ shape: a straight tail of length μ leading into a loop of length λ. Walk from the start and you travel the tail once, then circle the loop forever. The whole of Floyd’s method is finding these two numbers with two moving fingers and nothing written down.
4 TWO DIMENSIONS · INTERACTIVE
Step the race. The tortoise (slow) and hare (fast) move through the graph until they collide inside the loop — then the entry-finding phase walks them to the cycle start. Read μ and λ off the graph; a brute-force tally confirms them.
5 THREE DIMENSIONS + AVAN’S INVERSE
The ρ turning in space — the tail feeding the loop, seen from around.
AVAN’s addition (the inverse-companion): the two magenta markers are the racers. A single walker, memory-less, can never know it has entered a loop — every step looks new. Two walkers at different speeds turn that invisible fact into a visible collision: the loop is detected not by remembering where you have been, but by the gap between a fast self and a slow self closing to zero. It is the inverse of memory — knowledge from relative motion instead of from a record. The green is the shape; the magenta is how two speeds feel a loop the way one never could.
LIT Genuine Floyd tortoise-and-hare cycle detection. Verified live: on 5,000 random pointer-maps, Floyd's recovered cycle start mu and length lambda match a brute-force visited-set computation every time (window.__tortoise.allMatch === true). The two-speed collision and the entry-finding second phase are exact; the method uses O(1) memory regardless of tail or loop length.
FIG 'A race' is the picture; the O(1)-memory detection and the exact mu and lambda are the real algorithm. The entry-finding phase relies on a genuine modular-arithmetic identity about the meeting point, demonstrated here and cross-checked against brute force, not merely asserted.
FIG 'A race' is the picture; the O(1)-memory detection and the exact mu and lambda are the real algorithm. The entry-finding phase relies on a genuine modular-arithmetic identity about the meeting point, demonstrated here and cross-checked against brute force, not merely asserted.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HOT LOOP · David Lee Wise (ROOT0), with AVAN