5 ms·
An interesting counterpoint would be the Hashlife algorithm [1] for the game of life which is able to simulate the game of life at a scale and size well beyond
by contravariant 6y ago
An interesting counterpoint would be the Hashlife algorithm [1] for the game of life which is able to simulate the game of life at a scale and size well beyond any reasonable physical limits.
[1]: https://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 https://www.drdobbs.com/jvm/an-algorithm-for-compressing-spa...
- bronzeage 6y agoThere are no counterpoints because every turing complete simulation can't be made significantly more efficient. Any improvement would contradict the fact complexity classes classes strictly contain but aren't equal to each other. The most efficient way to run a universal turing machine on general input is to just run it.
- contravariant 6y agoTrue, but complexity doesn't necessarily have anything do to with time and space, that's all I really wanted to point out.
- skissane 6y agoI don't see how complexity classes are relevant here. If we accept that simulated time can run more slowly than real time – if it can take 10 seconds of computation time to simulate 1 second of simulation time – then complexity classes have no real relevance. Time complexity classes are just about how long a computation takes, and given an arbitrary amount of time to run the simulation in, and an arbitrary simulation rate (number of real seconds per a simulated second), it can take however long it takes. Even space complexity classes are not necessarily an issue. If the simulation runs out of storage, you can always suspend it, go provision more, and then resume it. The people in the simulation would never notice their suspension. It would only be a hard limit if some computation required more storage than could ever be provisioned, such as more bits than could fit in the observable universe. However, I doubt accurately simulating the contents of all contemporary human minds would need anywhere near that many bits.
- lupire 6y agoWhat do you mean "well beyond any reasonable physical limits?"
- contravariant 6y agoWell there's no direct translation from the game of life to the real world, but for any reasonable value for the size of a cell or the timer per simulation step there are simulations that are impractically large or take an impractically long time were you to try to build a full physical simulation of them.