Simulating Time With Square-Root Space (And With Details)

We will go in-depth into the proof that for all functions t(n) greater than or equal to n, every multitape Turing machine running in time t can be simulated in space only O(tlogt‾‾‾‾‾√). We will attempt to be completely self-contained. To that end, we will describe a necessary extension of the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024], which is the real surprise that makes the simulation possible.