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 [1] https://softwareengineering.stackexchange.com/questions/2345...