After reading about the HashLife algorithm, I found that it runs in O(log n). The Game of Life is also Turing Complete, so in theory we should be able to run any algorithm on a "computer" constructed in GoL.
As a consequence of HashLife's time complexity, could algorithms run faster? e.g. if an algorithm takes 10 seconds to run on a pc, could it run faster in HashLife on that same pc?
An example: An algorithm running takes a 1000 instructions to run. A certain computer can process 1 instruction per second. So that algorithm takes a 1000 seconds to run.
Now, if we take that same algorithm and run it on the "computer" in GoL. It would, because of HashLife being O(log n) take 3 seconds? (assuming O(log₁₀n))
I'm probably overlooking something, since this would be a very important discovery, but I still thought I'd ask about it here.