I understand that many algorithms have space/time tradeoffs-that is, to run faster, you can do things like caching data, which reduces time taken in exchange for space consumed.

Given conservation of energy and spacetime equivalence, is there any relationship between the time saved by using extra space and vice versa? After all, extra running time consumes more energy-is this energy equivalent to the energy taken to store the extra data in any way, or the other way around?


1 Answer 1


There surely are results about space/time tradeoffs but I'm not familiar with them. I would, though, like to address two significant misconceptions in the question.

First, it's important to note that when computer scientists talk about space and time, we're not referring to physical space or time. We're referring to purely mathematical concepts that are independent of the physical universe. "Time" to a computer scientist is just the number of computation steps that have been executed, and "space" is just the number of items of data that have been stored. We're interested in these quantities because we believe that they are a good model for physical computation, but the quantities themselves are not physical. Turing machines don't have to obey conservation of energy because they're not physical systems: nowhere in the definition of Turing machines do you see any power source. Indeed, I'm not aware of any theoretical work treating energy as a computational resource. Surely, some must exist, but it's not a concept that has made its presence felt in theoretical CS. Note also that number of computation steps on an ordinary Turing machine actually doesn't correspond very closely to the time taken by a physical computer.

Second, in physics, there is no such thing as "spacetime equivalence". Spacetime is not simply a convenient four-dimensional notation that lets us write "location $(x,y,z)$ at time $t$" as the four-dimensional co-ordinate $(x,y,z,t)$. The fundamental point is that the metric used to compute "distance" in this four-dimensional space is not the standard Euclidean metric but the Minkowski metric, which treats space and time differently. (See What is spacetime (simple explanation)? on Physics.SE for more on this.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.