Ryan Williams explains how to simulate a word RAM on a single-tape TM
rrwilliams · x · 2026-10-07
Complexity theorist Ryan Williams clarifies: for a Word RAM with O(log t)-bit words, store its (address, word) memory pairs in t·poly(log t) tape cells, so each RAM step simulates in t·poly(log t) time — scan the tape for the target address, then write the new record. The thread stems from OpenAI's one-tape TM simulation result.
Related event: OpenAI Turing Machine Simulation Implies New RAM Space Bound(3 posts)→
More from Research
- New paper builds a scientific theory of atomic features: SAEs of all sizes share features — jessicadai_ · 2026-10-07
- Reward-DAgger: generalist reward models enable task-agnostic runtime monitoring for robots — ebiyik_ · 2026-10-07
- 80% of the past 3 years' math progress happened in a single day — aaron_lou · 2026-10-07
- NVIDIA's VeriFine Co-Evolves Policy and Judge to Scale Self-Improvement in Embodied Reasoning — nvidia · 2026-10-07
- Single Image to Full 3D Scene: Adaptive Chunking Extends Object Generators to Outdoor Rome — Jiraphon Yenphraphai · 2026-10-07
- EmbodiedSmith: Recursive Self-Improvement Flywheel Scales Embodied Training Data in Simulation — Yikai Qin · 2026-10-07