Exact loop histories require unbounded memory
Abstract
A walk can return to its starting point while leaving a record that keeps growing. On a cube, counting every directed crossing loses which face loop came first; two retained states recover that distinction. Exact recovery of every reduced loop word requires unbounded memory. We characterize precisely which pairs of repetitions leave every device with a prescribed state count in the same state, and obtain the shortest universal pair within this family. Holding length and all crossing counts fixed still gives exponentially many distinct words. A randomized recorder with M retained states recovers a uniformly chosen member of an N-word family with probability at most min(1, M/N). A stack computes the record directly as edges arrive, with an explicit orientation rule. These results determine the memory capacity for the specified record. A physical application requires a process whose retained observable is that record.
