• gnramires 2 days ago

    Nice! I wonder if there are studies of Turing completeness for those systems?

    • danwills a day 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:

      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 20 hours 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).

    • shortrounddev2 a day ago

      Doesn't seem to work for me on librewolf but it could just be my very restrictive privacy settings

      • undefined 2 days ago
        [deleted]
        • gitroom a day ago

          [dead]