Building a computer in Conway's game of life • Hacker News Board

Re: Building a computer in Conway's game of life

#31

Post by CGamesPlay » Tue, Oct 20, 2020, 1:36 AM UTC

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

Re: Building a computer in Conway's game of life

#32

Post by CDSlice » Tue, Oct 20, 2020, 1:59 AM UTC

CGamesPlay wrote: post #31

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

Re: Building a computer in Conway's game of life

#33

Post by travisoneill1 » Tue, Oct 20, 2020, 2:02 AM UTC

CGamesPlay wrote: post #31

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…

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

Re: Building a computer in Conway's game of life

#34

Post by ohazi » Tue, Oct 20, 2020, 2:44 AM UTC

CGamesPlay wrote: post #31

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…

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.

Re: Building a computer in Conway's game of life

#35

Post by Aerroon » Tue, Oct 20, 2020, 2:48 AM UTC

jcims wrote: post #24

Aerroon wrote: post #17

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…

If you haven't seen it before this might blow you away haha - https://www.youtube.com/watch?v=ZKE8qK9UCrU All of this is happening in my body right now so i can type these letters: WTF

I would've loved videos like this when I was studying Biology! This kind of explanation with the video is amazingly clear. It reminds me a lot of how the signal is generated in eyes through the build up of charge after light hits the retina.

Re: Building a computer in Conway's game of life

#36

Post by rantwasp » Tue, Oct 20, 2020, 2:50 AM UTC

jcims wrote: post #24

Aerroon wrote: post #17

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…

If you haven't seen it before this might blow you away haha - https://www.youtube.com/watch?v=ZKE8qK9UCrU All of this is happening in my body right now so i can type these letters: WTF

my favorite is https://youtu.be/LQmTKxI4Wn4

once you look at microbiology you cannot unsee that it looks just like a massive, complicated stochasticaly-driven computer

Re: Building a computer in Conway's game of life

#37

Post by rantwasp » Tue, Oct 20, 2020, 2:52 AM UTC

beachy wrote: post #20

I have always wondered if intelligence could emerge from a game of life, given a massive board and sufficient random seeds.

yes.

without any spoilers there are literally tens of books out there that explore this very same idea. (some of them hard scifi)

Re: Building a computer in Conway's game of life

#38

Post by jcims » Tue, Oct 20, 2020, 3:18 AM UTC

rantwasp wrote: post #36

jcims wrote: post #24

Earlier quoted context omitted.

If you haven't seen it before this might blow you away haha - https://www.youtube.com/watch?v=ZKE8qK9UCrU All of this is happening in my body right now so i can type these letters: WTF

my favorite is https://youtu.be/LQmTKxI4Wn4 once you look at microbiology you cannot unsee that it looks just like a massive, complicated stochasticaly-driven computer

Whoa, that's crazy.

Every time I go down this rabbit hole I get re-convinced of panspermia. Maybe when I retire I'll study enough statistics and molecular biology to try to get my head around it. Or by then we'll be talking to aliens and the question will be moot.

Re: Building a computer in Conway's game of life

#39

Post by fblifeadvice645 » Tue, Oct 20, 2020, 3:21 AM UTC

rantwasp wrote: post #37

beachy wrote: post #20

I have always wondered if intelligence could emerge from a game of life, given a massive board and sufficient random seeds.

yes. without any spoilers there are literally tens of books out there that explore this very same idea. (some of them hard scifi)

you could at least give some names :)

Re: Building a computer in Conway's game of life

#40

Post by rantwasp » Tue, Oct 20, 2020, 3:36 AM UTC

fblifeadvice645 wrote: post #39

rantwasp wrote: post #37

Earlier quoted context omitted.

yes. without any spoilers there are literally tens of books out there that explore this very same idea. (some of them hard scifi)

you could at least give some names :)

greg egan

stephen wolfram

andrew gallimore

gerard hooft