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.
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.
> 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.