Nice! I wonder if there are studies of Turing completeness for those systems?
danwills•8mo ago
I've wondered that too! Uskate world has some features that are a bit like GOL gliders/spaceships, and I found some settings that I thought were a bit reminiscent of GOL on an extension I did to Gray Scott to add coupled 'history' and 'wave' reagents to it:
I think universality in RD sims is extremely likely (almost a given) but probably quite hard to prove.. I guess all it would really need is a working/stable basic primitive like a NAND gate kinda thing though?
gnramires•8mo ago
That definitely seems like it could be universal :)
Yes, and I think the question of stability is very interesting, specially as those are continuous systems with non-local effects. To prove universality, you're probably going to need to prove that small perturbations that might be inevitable (unless values decay in finite distances) maintain a given behavior, with "regenerative" properties: analogous to fan-in/fan-out in electronic gates (basically, iterated gate applications need to have points or basins of attraction, usually 0 or 1, such that if your system gets noisy, this noise is eventually eliminated and the signal "regenerated"). If you can build a NAND gate within a kind of cell, and show that it's stable w.r.t perturbations, and has regenerative output, I think that would be enough (in that case not only universality is achieved in a technical sense, but in a very robust sense as well) to build a TM.
The spaces of parameters that achieve Turing completeness would be really cool to see as well.
Preferably, your cell should output a "packet", which should permit, given a synchronization source, that this packet travel toward other cells but also avoid other packets traveling in say an orthogonal direction, that is, you should allow wire crossings. If your system doesn't allow wire crossings, I suspect you may be able to prove Turing completeness is impossible, at least I believe you can prove (left as an exercise :) ) that realizing some circuits may require crossings. Alternatively, you can build gates/cells with multiple inputs and multiple outputs, such that effectively one of the gates allows for information to cross over.
Note: I believe this difficulty of building complex systems in 2 dimensions might partially explain why we live in 3 dimensions! It's just very hard for a complex life form to evolve in a 2D system because of, among other things, this connectivity difficulty (in 3D you can basically just route wires/tubes anywhere :) ), this is assuming some form of a generalized Copernican Principle (that we exist probabilistically in possible universes). 4 dimensions and higher may produce similar connectivity difficulties, but in terms of too much connectivity instead of too little. I presume we can explain to a significant understand the whys of why physics is it the way is in our universe using this principle (which appears to me to be a generalization of the Anthropic principle).
danwills•8mo ago
Yeah awesome I totally agree that the potential seems to be there for universality in RD systems like the one I posted, and also that stability is going to be absolutely key to the idea working at all! Thankfully Gray-Scott and similar systems have already been shown to be resistant to noise (there's an example in gollygang/Ready at Patterns/GrayScott1984/Lesmes_noisy.vti)
I also 100% agree about the wiring-problem when simulating things in 2D! However I've seen how moving-solitons behave a lot, and although they are probably more sensitive, I just can't believe that they are ultimately that different to GOL gliders.. and so I would hope that all that would be required to be able to cross wires would be making enough space, and some careful synchronization (offset modulo-synced clock states) to allow streams to cross without interfering!
Here's way too much soliton-fun I had ages ago in a video:
I think that how solitons can behave when they are affected by both their own diffused-history and the wave-equation results of their past states, is just so fascinating!
In terms of whether non-local effects might come-in and ruin the completeness-party, most RDs have a diffusion-coefficient and I think there's probably some fairly good guarantees around rate-of-information-propagation there especially for RDs that don't use the wave-equation. The one I posted in my first reply does use wave, but it actually might not need to use it in order to be able to achieve its overall behavior! And even when using wave-equation, the max propagation-rate is still limited by the wave-diffusion coefficient!
I think there are several ideas in your comment that are absolutely getting to the heart of the matter: Building some kind of predictable 'cell' that can take moving-solitons in its 'input ports' and results in a logical result via moving-solitons exiting its 'output ports', all perfectly synchronized to work with coupled 'cells'. It does sound pretty hard! But I think that with a concerted effort, and with the potential frameworks that could be built-into gollygang/Ready with a dedicated coder who's interested in all of this, then some progress could definitely be made!
shortrounddev2•8mo ago
Doesn't seem to work for me on librewolf but it could just be my very restrictive privacy settings
gnramires•8mo ago
danwills•8mo ago
https://youtu.be/W6sO8ZkgU9s?si=ESgUWb5OfZ97P2hk
I think universality in RD sims is extremely likely (almost a given) but probably quite hard to prove.. I guess all it would really need is a working/stable basic primitive like a NAND gate kinda thing though?
gnramires•8mo ago
Yes, and I think the question of stability is very interesting, specially as those are continuous systems with non-local effects. To prove universality, you're probably going to need to prove that small perturbations that might be inevitable (unless values decay in finite distances) maintain a given behavior, with "regenerative" properties: analogous to fan-in/fan-out in electronic gates (basically, iterated gate applications need to have points or basins of attraction, usually 0 or 1, such that if your system gets noisy, this noise is eventually eliminated and the signal "regenerated"). If you can build a NAND gate within a kind of cell, and show that it's stable w.r.t perturbations, and has regenerative output, I think that would be enough (in that case not only universality is achieved in a technical sense, but in a very robust sense as well) to build a TM.
The spaces of parameters that achieve Turing completeness would be really cool to see as well.
Preferably, your cell should output a "packet", which should permit, given a synchronization source, that this packet travel toward other cells but also avoid other packets traveling in say an orthogonal direction, that is, you should allow wire crossings. If your system doesn't allow wire crossings, I suspect you may be able to prove Turing completeness is impossible, at least I believe you can prove (left as an exercise :) ) that realizing some circuits may require crossings. Alternatively, you can build gates/cells with multiple inputs and multiple outputs, such that effectively one of the gates allows for information to cross over.
Note: I believe this difficulty of building complex systems in 2 dimensions might partially explain why we live in 3 dimensions! It's just very hard for a complex life form to evolve in a 2D system because of, among other things, this connectivity difficulty (in 3D you can basically just route wires/tubes anywhere :) ), this is assuming some form of a generalized Copernican Principle (that we exist probabilistically in possible universes). 4 dimensions and higher may produce similar connectivity difficulties, but in terms of too much connectivity instead of too little. I presume we can explain to a significant understand the whys of why physics is it the way is in our universe using this principle (which appears to me to be a generalization of the Anthropic principle).
danwills•8mo ago
I also 100% agree about the wiring-problem when simulating things in 2D! However I've seen how moving-solitons behave a lot, and although they are probably more sensitive, I just can't believe that they are ultimately that different to GOL gliders.. and so I would hope that all that would be required to be able to cross wires would be making enough space, and some careful synchronization (offset modulo-synced clock states) to allow streams to cross without interfering!
Here's way too much soliton-fun I had ages ago in a video:
https://www.youtube.com/watch?v=Naj_J8aznyk&t=12s
I think that how solitons can behave when they are affected by both their own diffused-history and the wave-equation results of their past states, is just so fascinating!
In terms of whether non-local effects might come-in and ruin the completeness-party, most RDs have a diffusion-coefficient and I think there's probably some fairly good guarantees around rate-of-information-propagation there especially for RDs that don't use the wave-equation. The one I posted in my first reply does use wave, but it actually might not need to use it in order to be able to achieve its overall behavior! And even when using wave-equation, the max propagation-rate is still limited by the wave-diffusion coefficient!
I think there are several ideas in your comment that are absolutely getting to the heart of the matter: Building some kind of predictable 'cell' that can take moving-solitons in its 'input ports' and results in a logical result via moving-solitons exiting its 'output ports', all perfectly synchronized to work with coupled 'cells'. It does sound pretty hard! But I think that with a concerted effort, and with the potential frameworks that could be built-into gollygang/Ready with a dedicated coder who's interested in all of this, then some progress could definitely be made!