3 ms·

So, for "pure" tasks which take input and produce output only at the very end, the Hashlife algorithm [0] allows you to run arbitrarily many generations of life

So, for "pure" tasks which take input and produce output only at the very end, the Hashlife algorithm [0] allows you to run arbitrarily many generations of life in constant time at the expense of a huge internal cache (memory usage). That is, with Hashlife you can trade memory for computational efficiency. That means that for a sufficiently difficult task like mining bitcoin, this computer could be simulated faster than any conventional computer could run at the expense of using more memory. My question: does anybody know what the ratio of trade-off between time and space is for Hashlife? I haven't been able to find anything from my searches. [0] https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife

CDSlice 6y ago
I'm not so sure this is correct. [0] says that Hashlife has logarithmic complexity on average. In the worst case it is O(n) since it could have to look at every element to see a pattern if one even exists [1]. Therefore the worst case for any algorithm running in a Life turing machine using HashLife is the same as if it was running directly on the machine. [0] https://fanf.livejournal.com/83709.html https://fanf.livejournal.com/83709.html [1] https://softwareengineering.stackexchange.com/questions/234548/what-are-the-consequences-of-hash-life-running-in-olog-n https://softwareengineering.stackexchange.com/questions/2345...
- CGamesPlay 6y ago
  Hmm, the phrasing on that first link does not lead to its stated conclusion: > Hashlife can take the same length of time to compute from generation N to generation 2N for any large enough N - it has logarithmic complexity. If 2N takes as much time as N, then 4N takes as much time as N, and so 8N takes as much as N, and so... (for any large enough N). This seems to indicate--asymptotically--constant time, not logarithmic.
travisoneill1 6y ago
Memory access is generally much slower than computation, so I don't think you could actually speed up mining in this manner.
ohazi 6y ago
Hashlife can theoretically "cache" a specific input and output, e.g. running an instruction on your simulated computer like "add r0, r1, r2" (when r0, r1, and r2 contain specific values that have already been used with this instruction, and assuming that any nearby internal state is also identical). But this doesn't let you magically mine bitcoin in fast-forward, because in order to mine bitcoin, you need to insert random bytes into your block and keep changing them until you get lucky and find a hash that starts with a certain number of zeroes. This effectively guarantees that you aren't going to have cached computation snippets that are big enough to skip any meaningful amount of work. At best, you might be able to fast-forward at the instruction level granularity, at which point you might as well be mining on your CPU.
im3w1l 6y ago
You could do the same without transforming to game of life. Iterate over all possible states the memory can be in, and emulate a cpu with that memory for N steps. But if you have 640 kilobytes memory (ought to be enough for anyone), that means your cache will have 2^640000 entries. When transforming to game of life every bit of memory becomes many cells in the grid, so the requirements for that would be even worse.

CDSlice 6y ago

I'm not so sure this is correct. [0] says that Hashlife has logarithmic complexity on average. In the worst case it is O(n) since it could have to look at every element to see a pattern if one even exists [1]. Therefore the worst case for any algorithm running in a Life turing machine using HashLife is the same as if it was running directly on the machine. [0] https://fanf.livejournal.com/83709.html https://fanf.livejournal.com/83709.html [1] https://softwareengineering.stackexchange.com/questions/234548/what-are-the-consequences-of-hash-life-running-in-olog-n https://softwareengineering.stackexchange.com/questions/2345...

CGamesPlay 6y ago
Hmm, the phrasing on that first link does not lead to its stated conclusion: > Hashlife can take the same length of time to compute from generation N to generation 2N for any large enough N - it has logarithmic complexity. If 2N takes as much time as N, then 4N takes as much time as N, and so 8N takes as much as N, and so... (for any large enough N). This seems to indicate--asymptotically--constant time, not logarithmic.

travisoneill1 6y ago

Memory access is generally much slower than computation, so I don't think you could actually speed up mining in this manner.

ohazi 6y ago

Hashlife can theoretically "cache" a specific input and output, e.g. running an instruction on your simulated computer like "add r0, r1, r2" (when r0, r1, and r2 contain specific values that have already been used with this instruction, and assuming that any nearby internal state is also identical). But this doesn't let you magically mine bitcoin in fast-forward, because in order to mine bitcoin, you need to insert random bytes into your block and keep changing them until you get lucky and find a hash that starts with a certain number of zeroes. This effectively guarantees that you aren't going to have cached computation snippets that are big enough to skip any meaningful amount of work. At best, you might be able to fast-forward at the instruction level granularity, at which point you might as well be mining on your CPU.

im3w1l 6y ago

You could do the same without transforming to game of life. Iterate over all possible states the memory can be in, and emulate a cpu with that memory for N steps. But if you have 640 kilobytes memory (ought to be enough for anyone), that means your cache will have 2^640000 entries. When transforming to game of life every bit of memory becomes many cells in the grid, so the requirements for that would be even worse.