Thinking more about the cellular automaton stuff: okay, so Game of Life is Turing complete. But the question is whether we can pin down properties that GoL has that Turing machines don’t have.
I have a vague recollection that parallel Turing Machines are a thing, but this paper claims that the actual formalisms are disappointing. One nice thing about Game of Life is that the way that different programs interact internally (via game of life physics) is also how they interact with each other. Whereas any multi-tape Turing Machine (even one with clever rules about how to integrate inputs from multiple tapes) wouldn’t have that property.
I feel like I’m not getting beyond the original idea that Game of Life could have adversarial robustness in a way that Turing Machines don’t. But it feels like you’d need to demonstrate this with some construction that’s actually adversarially robust, which seems difficult.
But it feels like you’d need to demonstrate this with some construction that’s actually adversarially robust, which seems difficult.
I agree it’s kind of difficult.
Have you seen Nicholas Carlini’s Game of Life series? It starts by building up logical gates up to a microprocessor that factors 15 in to 3 x 5.
Depending on the adversarial robustness model (e.g. every second the adversary can make 1 square behave the opposite of lawfully), it might be possible to make robust logic gates and circuits. In fact the existing circuits are a little robust already—though not at the tune of 1 square per tick, that’s too much power for the adversary.
No I agree with that. I thought the tree design already involved weighted sums overpowering each other, but I think that was premature.
Thinking more about the cellular automaton stuff: okay, so Game of Life is Turing complete. But the question is whether we can pin down properties that GoL has that Turing machines don’t have.
I have a vague recollection that parallel Turing Machines are a thing, but this paper claims that the actual formalisms are disappointing. One nice thing about Game of Life is that the way that different programs interact internally (via game of life physics) is also how they interact with each other. Whereas any multi-tape Turing Machine (even one with clever rules about how to integrate inputs from multiple tapes) wouldn’t have that property.
I feel like I’m not getting beyond the original idea that Game of Life could have adversarial robustness in a way that Turing Machines don’t. But it feels like you’d need to demonstrate this with some construction that’s actually adversarially robust, which seems difficult.
I agree it’s kind of difficult.
Have you seen Nicholas Carlini’s Game of Life series? It starts by building up logical gates up to a microprocessor that factors 15 in to 3 x 5.
Depending on the adversarial robustness model (e.g. every second the adversary can make 1 square behave the opposite of lawfully), it might be possible to make robust logic gates and circuits. In fact the existing circuits are a little robust already—though not at the tune of 1 square per tick, that’s too much power for the adversary.