51–60 of 68 posts
See Quest for Tetris, a full processor implemented in Conway's Game of Life: https://codegolf.stackexchange.com/a/142673
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 t…
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://softw…
> 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.
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 t…
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.
It’s interesting watching the messy complexity resolve into patterns and order as you zoom out. It’s reminiscent of what it feels like to dig deeply into a metabolic or reproductive process in a cell and be overcome with the sheer complexity of it, then look at the back of your hand and realize it’s all happening right there, now. Basically it feels a bit like life.
The first time I heard of Conway's Game of Life I was blown away. It was an example of potentially incredible complexity that can be arranged to large scale patterns emerge. It was the first time I took the idea of the universe being simulated (or created) seriously. Even more fascinating for me is the idea that we can't analytically calculate the outcome. To find out what happens we have to simulate it. Even if the…
I've read Wolfram claim this, but as a conjecture, iirc. Is there a formal proof that in order to predict life patterns we essentially need to run the cellular automaton?
I have always wondered if intelligence could emerge from a game of life, given a massive board and sufficient random seeds.
It would be difficult. In particular, unlike in our world, it's very difficult to create anything like a stable membrane or barrier in the game of life. And patterns are extremely susceptible to falling apart if perturbed. So you would generally expect a game-of-life-based entity touching anything to die as a result.
This doesn't mean the patterns would visually look like cells and membranes though...
Earlier quoted context omitted.
The first time I heard of Conway's Game of Life I was blown away. It was an example of potentially incredible complexity that can be arranged to large scale patterns emerge. It was the first time I took the idea of the universe being simulated (or created) seriously. Even more fascinating for me is the idea that we can't analytically calculate the outcome. To find out what happens we have to simulate it. Even if the…
>we can't analytically calculate the outcome. To find out what happens we have to simulate it. I've read Wolfram claim this, but as a conjecture, iirc. Is there a formal proof that in order to predict life patterns we essentially need to run the cellular automaton?
Haha I posted this a few months ago: 4 points. HN is so random sometimes :D
Earlier quoted context omitted.
The first time I heard of Conway's Game of Life I was blown away. It was an example of potentially incredible complexity that can be arranged to large scale patterns emerge. It was the first time I took the idea of the universe being simulated (or created) seriously. Even more fascinating for me is the idea that we can't analytically calculate the outcome. To find out what happens we have to simulate it. Even if the…
>we can't analytically calculate the outcome. To find out what happens we have to simulate it. I've read Wolfram claim this, but as a conjecture, iirc. Is there a formal proof that in order to predict life patterns we essentially need to run the cellular automaton?
Cool and all that, but isn't this... practically and intellectually useless? Surely, you can build a computer using pebbles on the sea shore by aligning them in the specific order. How is that surprising?
They knew it was a low-quality question and so created a new account in order to post that comment. And despite knowing it was a crap comment, cared enough to make the effort to create the new account. I don't get some motivates some people.