OpenAI's one-tape TM simulation implies RAM time t fits in SPACE[t^4/5]
KortenOliver · x · 2026-10-07
KortenOliver points out that OpenAI's one-tape Turing machine simulation (assuming correctness) immediately implies RAM time t lies in SPACE[t^(4/5)]. He wonders why the paper didn't mention this corollary, noting it was the whole point of his question. Ryan Williams replies, conceding he omitted a polylog factor in his earlier tweet.
Related event: OpenAI Turing Machine Simulation Implies New RAM Space Bound(3 posts)→