Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Preprint
Data sources: ZENODO
addClaim

Exact loop histories require unbounded memory

Authors: Washburn, Jonathan;

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.

Powered by OpenAIRE graph
Found an issue? Give us feedback