What I'm really wondering is, how much do different memory timing models affect the theory of algorithms?
Everyone here is used to thinking of memory-access as constant-time, but in the theory of algorithms, the standard model used is not a random-access model (which, when fully exploited, allows doing certain things unreasonably fast -- like, linear-time multiplication!), but rather the multi-tape Turing machine model. These tapes are 1-dimensional, effectively making memory access require linear time, larger than the cube-root time discussed here!
Since cube-root time, or using a multidimensional tape, seems more physical, I've often wonder how changing to this -- not necessarily to 3 dimensions, you understand, but to any number of dimensions d -- would affect the theory. (Or if we lived in hyperbolic space, where perhaps memory access could take logarithmic time.) Would it be meaningfully different? Hopefully not, but I have no idea! I've never seen anything on the question, though. Anyone know of anything?
Everyone here is used to thinking of memory-access as constant-time, but in the theory of algorithms, the standard model used is not a random-access model (which, when fully exploited, allows doing certain things unreasonably fast -- like, linear-time multiplication!), but rather the multi-tape Turing machine model. These tapes are 1-dimensional, effectively making memory access require linear time, larger than the cube-root time discussed here!
Since cube-root time, or using a multidimensional tape, seems more physical, I've often wonder how changing to this -- not necessarily to 3 dimensions, you understand, but to any number of dimensions d -- would affect the theory. (Or if we lived in hyperbolic space, where perhaps memory access could take logarithmic time.) Would it be meaningfully different? Hopefully not, but I have no idea! I've never seen anything on the question, though. Anyone know of anything?