Multi-Access Randomness Saves Space, Even for Halting AlgorithmsResearch Paper
Space complexity asks how much writable memory a computation needs. Randomness introduces another resource: a machine can consult a tape of independent fair bits without paying for those bits as work space. Whether it may return to an earlier random bit, and whether it must halt on every possible tape, affect the resulting model. These distinctions matter…