Cellular Automata Thread

This thread is for all discussion of cellular automata and their applications in computer science and programming. I decided to make it because I'm a computer science student who's recently become interested in the subject and I wanted to see what experience Lainons have with it, so post all your best cellular automata resources, tips, tricks and hot opinions here.

>>2594 sounds interesting, but it would be best if you could start the thread with some content. Do you have some code? A book? Anything? Why do you like cellular automatas?

From what I know, most information about CA can be found in 'A new kind of science' by Stephen Wolfram (book is available online for free, but in soykafty quality for some reason), but I've went through only few chapters... It sure is interesting topic, but I'm not sure if there is something more which can be achieved. It is proven that CA are universal, even the simplest ones (one dimension, one color in rule 110, there are several turing machines emulated in Conway's game of life etc) and 'priciple of coputational equality' or how Wolfram called seems like more of philosophical question...

>>2715 some interesting things can be proved about CA's in general. I vaguely remember that someone proved that you can't make a unique 'eden' configuration which is the only one that will produce a given state, which can be thought of as saying CA's can't be time-reversible. I'll look for the paper and come back, it was pretty interesting.

>>2716 Reversible CA's exist. But the majority are indeed not time reversible. On the other hand, every nonreversible CA on a grid of dimension d can be emulated by a reversible CA on a grid of dimension d+1.

>>2718 ah, I found that paper. Garden of Eden configurations are more special, in that they have no *previous* iteration. Reversible CA's cannot have Garden of Eden configurations. I couldn't find the paper itself online but wikipedia has an overview https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton)

>>2718 soykaf, I get the feeling that this is a pretty important theorem. It's very interesting.

>>2713 There are some books and papers out there, but there isn't really the same ready-made body of resources for CA that you see in some of the other threads, like the beginner programming thread or the web dev thread. CA-based programming isn't something a lot of people do yet, so I hope we can use this thread to build such a foundation of knowledge. Regrettably I don't yet have any CA-based code of my own, but it's something I'm hoping to try in C/C++ soon using some information I found in this paper on cellular automata for machine learning: https://cdn.intechopen.com/pdfs-wm/44535.pdf >>2718 I wonder if it may also possible to reverse that relationship and have every reversible CA be able to be emulated by a non-reversible CA.

>>2715 >A new kind of science I just put it on vola: https://volafile.org/r/kUFzLJ (bottom of the list). Beware however as this book is really only mediocre if that. Since Wolfram is a genius (wrote his PhD on Quarks at 18) this makes it doubly disappointing.

>>2723 I'm going to go through this at some point. I wonder if my life would be different if I'd done that when it came out. I'd never heard of CA then. Of course there are a bunch of different Wikipedia articles on different types of CA ranging from stochastic and quantum CAs to asynchronous and life-like CAs. They're used in many different areas of science including physics, chemistry, and biology, so if we had a /sci/ board there would be room for this thread there too. For this board though, this is what we're after: https://en.wikipedia.org/wiki/Automata-based_programming

I've recently been watching a lecture series on yt which is a pretty gentle introduction to finite-state automata, Turing machines, computability, etc. It parallels a uni course I'm doing on model theory, which is really nice. Anyway it's not really cellular automata programming, but I think it lays a pretty good foundation for digging into it later, which I really hope to do. Link is https://www.youtube.com/playlist?list=PLslgisHe5tBM8UTCt1f66oMkpmjCblzkt ... the lecturer is a bit of a kook, it's comfy.

>>2727 CAs are basically just a choice of abstraction. They're good for visualizing convolution equations because the rule for state change is spatially invariant. So anywhere you see convolution equations, you could choose to see CAs. For example repeatedly applying a gaussian blur to an image file could be seen as stepping through a CA with a state count equal to the image's bit depth.

>>2741 You sound like you have a good bit of experience with CAs. What have you used them for in the past and can any of it be carried over to programming or other STEM applications?

I think this thread could end up being almost as much of a research group as a discussion thread because the subject matter is largely unexplored outside of universities and other big ticket research communities. We should try to make some CA-based application development tools for the rest of Lainchan to use.

>>2770 First tell us about CA (plz)

>>2770 Do we have a github page yet? perhaps we can collaborate to create some interesting stuff. We could start with cellular 2 dimensional cellular automata and build a tetris like game or something.

>>2833 >>2834 I've been hunting for resources the last few days to serve as a foundation to develop people's interest and skills in CA, and here's what I've come up with so far. The basics here, to get people started with learning how many things grids of cells that evolve according to simple rules can do: https://en.wikipedia.org/wiki/Cellular_automaton mathworld.wolfram.com/CellularAutomaton.html Here's an article on CA from one of the developers of CelLab. It's pretty entry-level, but for those lainons who aren't familiar with it, it's a good jumping-off point: https://ricochet.com/434577/saturday-night-science-cellular-automata/ And here's a tutorial on implementing CA. The tutorial is in Processing, but most of the concepts and even some of the code itself can readily be used in C++: www.natureofcode.com/book/chapter-7-cellular-automata/ Here are some papers I hunted for the machine learning thread about using CA to create a genetic program, and also using genetic programs to create CA. http://academicworks.cuny.edu/cgi/viewcontent.cgi?article=1413&context=cc_conf_hic https://arxiv.org/ftp/arxiv/papers/0711/0711.2478.pdf http://ro.ecu.edu.au/cgi/viewcontent.cgi?article=1094&context=theses_hons Making a game with CA might be fun. A while back I thought about making a puzzle game that's like a combination of a physics puzzler and Myst, with a gripping, suspenseful storyline, and perhaps with CA-generated art and music as well. Or we could always make Project KIDS from Lain. Let's all love Lain.

Been working on a somewhat generalized grid-based simulation engine in rust. Right now it does Conway's Game of Life by default. Check it out~ https://github.com/jeremycooper/conway

https://www.youtube.com/watch?v=-kIx5HKosJc

>>2861 I'm not really a Rust guy, so I can't comment much on this. Good to see people working on CA stuff though. How long did it take you to build this and what can it simulate?

>>2866 Well, Conway's Game of Life is Turing universal, so it could theoretically simulate anything. I'm unclear as to what "somewhat generalized" means though.

>>2866 Took me about a week of hacking to get it to where it is right now. >>2867 By `somewhat generalized` I just mean that it's an engine that you input a set of state-based rules and it applies those rules to cells in a grid. On TOP of that, I made it do conway's game of life. So by generalized I mean it can use different rulesets.

>>2876 So it could potentially have a lot of applications, then. I wonder if it'd be useful to have a version written in another language. What made you decide to make it?

>>2878 Rust is pretty multi-platform so I don't see a direct need to have it ported to another language. Was needing a good project to use as practice, and GoL has always been really interesting to me. Hoping people can use it as a library for experimenting with different rulsets, or just as a fun command line utility (like `cmatrix` haah).

>>2882 I guess we can see about porting it over when and if the need to move it to a more specialized platform arises. Until then, a cellular automata simulation engine could use a robust plugin system. It'd be nice if it could be modded to handle numerous grid cell shapes, nested automata, interfacing with other programs and such.

>>2883 Right now you can pass in an anonymous function in place of selecting a prebuilt ruleset or using the DSL, so theoretically the framework for nested automata already exists. Different cell shapes and thus tessellation patterns will require a bit of thinking, not sure I've done something like that before, I do really like the idea though! A plugin system would be the most powerful way to make this as general and usable as possible but I'm not sure I would know how to get a foothold into building that aspect of it. Any ideas?

>>2884 >A plugin system would be the most powerful way to make this as general and usable as possible but I'm not sure I would know how to get a foothold into building that aspect of it. Any ideas? I don't know Rust, so I can't be of any help there. My only major thought right now is a custom cell shape editor to allow users to go above and beyond the presets.

>>2885 I think it could be reasonably simplified to a selection of number of sides to shape. As they would need to have some sort of rotational symmetry in order to stack right in the grid.

>>2886 If anyone needs more than that, they could write up a mod for it.

I'm trying to think of projects to do with CAs, because experienced programmers have told me that it's best to program with a specific goal in mind rather than just trying to learn it for the sake of passing a class or getting a job. I've considered trying to make a videogame-playing bot with CAs, build a CA that acts as control software for embedded systems, and create a CA-based personal assistant to do computing-related tasks for me. What should I try to do?

>>2954 I would continue following that advice and pick the specific application of CAs that personally interests you the most.

>>2886 Why not go even farther than that and have cells be internally represented as nodes, with each connection being represented as a "side"? You could even make rulesets that would create connections between nodes dynamically.

>>2745 nah i just have a math degree and spent a few weeks playing around with golly. my point in the previous post was that CAs are just an abstraction that can be useful for modelling. think of a CA like a turing machine or a network graph... they have theoretic value, but you aren't going to use a "CA library" in your code or anything. if you are looking at a system with CA-like behavior, it makes sense to model it with a CA. how familiar are you with this stuff? i don't want to talk down to you if you already get it, but there's a mathematical concept called a (spatial) convolution which will really help you understand what's going on with CAs. the basic idea is that the state of some node at time t+1 is a function of the states of the cells in its neighborhood at time t. this function is called the kernel, and is the same no matter which cell you apply it to (the function is the same, the "output" of the function will obviously change). CAs are a specific application of this concept. the function for determining if a particular cell lives or dies in the next time step is the kernel. the convolution equation applies this kernel to each cell.

>>2963 this is basically how CNNs work. i'd recommend representing the connectivity of cells in the network as an adjacency matrix. then you can simply multiply this matrix by the state vector of the network to obtain the next step. i've implemented this kind of thing in c using the BLAS library, and it ends up being pretty fast.

>>2964 Not him, and I don't know anything more than the outline of CA stuff, I study maths mostly. I'm taken aback at this idea of the transition rule being the kernel of an integral transform, where the original function represents the current state (if I understand what you've written correctly). But CAs are discrete and binary, right? so it'd be like an n-dimensional discrete convolution of the transition function with a kind of complicated step function representing the state? But this doesn't account for the role of neighbourhoods in CAs, so is it that there's a whole lot of simultaneous convolutions with limited domains, or is the kernel function defined using, like, indicator functions for neighbouring cells? Sorry, lots of questions, I'm gonna go educate myself about this a bit I think.

>>2972 i'll just write it out in tex later tonight. there's a few different ways to formulate this and i don't know which one is best without playing around with it for a bit. >But this doesn't account for the role of neighbourhoods in CAs you'd have function like this: >d((i,j),(i',j'))={true: (0,0)<(|i-i'|,|j-j'|)<=(1,1); false: otherwise} ...which would be convolved with a function mapping N^2->{'alive','dead'} >>2770 i'm down. lets come up with something cool for the lainzine.

>>2964 I get the CA concept, but I've never done anything with convolution equations before. Might take a look at that. There are some who think CAs may be more than a mere abstraction, though. I don't know a lot of the details, but I've read that there have been physicists who've speculated that the universe itself is a CA and that all physical processes on a fundamental level are CAs. >but you aren't going to use a "CA library" in your code or anything. The Wolfram Language actually does have a CA function. I've never heard of such a thing in any other language, but I wouldn't entirely rule out the idea of a CA library being made for other languages to allow them to do the same thing. >>2965 This is pure genius and I think I'm going to use it. It's much simpler than many of the implementations I've seen in CA tutorials, and that makes it a good choice for any application where computational power is at a premium, or where a great deal of complexity isn't needed.

>>2963 I like the way you think. I'll probably keep this current project purely grid-based, additionally, >>2965 make a really good point, at some point the line gets pretty blurred between those two concepts. That sort of math feels beyond me right now as I definitely let that skill atrophy for a while but I'll keep those terms floating around my head if I ever re-approach the n-sided cell simulation. Thanks!

>>2965 Do you think I could have a look at that code for reference? If you still have it around.

I found a neat video a while back of a continuous floating point version of conway's game of life https://www.youtube.com/watch?v=KJe9H6qS82I

I just found this automata generator which looks really cool: https://github.com/InfiniteSearchSpace/Automata-Totalistic-Gen-4 This person has a youtube channel where they used to upload the different automata they've created: https://www.youtube.com/channel/UCZD4RoffXIDoEARW5aGkEbg/videos

Best software to play around with CA: http://golly.sourceforge.net/ Tinker CA online: https://copy.sh/life/ CA wiki: http://www.conwaylife.com/wiki/Main_Page

>>3007 >>3013 Some very good stuff here. Hopefully this thread lasts long enough to justify making another one at some point. If it does, these resources should go in the OP of the new thread. >>2987 Also this.

>>3013 Do you know if the picture of the prime calculator on the golly homepage is done using the conway ruleset or an alternate one.

Update on the rust conway implementation: (https://github.com/jeremycooper/conway) Pretty much done with the cli and i've got some installation instructions as well as a description of the different options. alternate rulesets through external config files using a dsl will be the next big feature but until then if anyone feels like it they can add a new ruleset in world/rules/mod.rs, it should be relatively self explanatory but ask if you have questions. Any feedback or if you guys wouldn't mind even just testing this out I'd highly appreciate it!

>>3021 No, prime calculator was made using Wireworld rules: https://en.wikipedia.org/wiki/Wireworld

I imagine many of us are busy with back-to-school things at the moment. Though I'd still like to see the code from the project in >>2965, I decided to go hunting for other examples of CA-style neural networks. I ended up finding mxnet and tiny-cnn (now tiny-dnn), and a few papers that deal with neural networks on embedded systems, but mxnet isn't all that portable, and I didn't turn up a whole lot of example code, especially not using BLAS. tiny-dnn has some example programs, so I thought I'd dump it here. https://github.com/tiny-dnn/tiny-dnn Hopefully this week I'll be able to find some time to go over the CA wiki and some of these automata generation programs, and to look more at neural networks and how they can be used with CAs. It would be awesome if someone with a great deal of familiarity with NNs could help those of us who aren't as familiar with them narrow our search to NN architectures that use principles which can be applied to CAs. There are many different types of NNs and each one is suitable for different purposes.

I tried to do something experimental and go against CA's rules. Instead of forcing the neighbors to determine the state of a cell, I tried to see if I can get it working with the cell determining the states of its neighbors. Then I swapped the cell-neighbor mapping at the end of each iteration, so it would seemingly conform by CA rules. Here's the initial distribution (has to be sparse), and results after 2 and 10 iterations. The rules are: If a cell receives 1 state, its neighbors are at -1 (transient). If a cell gets assigned -1 from two other cells, it becomes 1. If a 1 is entirely surrounded by -1 at the end of 1 iteration, it becomes 0.

>>3167 Never heard of an inverted CA before. Seems like something that should be looked into. The pattern there looks like bismuth. Maybe you could use it to model crystal growth or other similar processes.

>>3172 My initial motivation was to create a system where a cell's interactions with its environment determined its fate. If a cell could interact with another cell, it would remain alive, because that's how I thought both cellular organisms and civilizations did. If interacted with nobody the cell would revert to null, or die. Pics related: the configuration. Now, my current work involves a relation with Golden Ratio and I think I have an insight, so by modifying this code I'll try to see if I can achieve fractal growth.

>>3167 also the 4th iteration I couldn't post before.

>>3175 >>3176 Can you post some example code from this? I'm wondering if it's possible to make a CA-based neural network using a similar system. I'm still hunting down code samples from that.

>>3178 Sure. I'm a soykaf coder, but I modified this from a working Game of Life sample, which runs with a complexity package from here: http://pycx.sourceforge.net/ Also I'm new at CA so you might want to check if there's something fundamentally wrong with my work. import matplotlib matplotlib.use('TkAgg') from pylab import * import numpy as np L = 100 p = .01 def init(): global c, nc c = zeros([L,L]) for x in xrange(L): for y in xrange(L): c[x,y] = 1 if random() < p else 0 nc = zeros([L,L]) def draw(): cla() imshow(c) def step(): count = [] global c, nc for x in xrange(L): for y in xrange(L): count = [] for w in range(-1, 2): for z in range(-1, 2): count.append(c[(x+w)%L, (y+z)%L]) #count = nc[z] for k in range(len(count)): if c[x,y] == 0: nc[x,y] == 0 else: if any(count[k] == 1): nc[(x+w)%L, (y+z)%L] == 1 #print(any(count[k] == 1)) #print any(nc == 1) #print count[k] #c[x,y] = 1 pass elif count[k] == 0: count[k] = -1 nc[(x+w)%L, (y+z)%L] = count[k] #print count[k] #nc = count[k] #print c[x,y] for x in xrange(L): for y in xrange(L): #n = number_of_living_neighbors(x,y) for w in range(-1, 2): for z in range(-1, 2): for k in range(len(count)): if c[x,y] == 0: pass else: if all(count[k] != 1): nc[x,y] = 0 #print any(nc == 1) #print count #print nc elif any(count[k] == -1): count[k] = 1 nc[(x+w)%L, (y+z)%L] = count[k] c, nc = nc, c #if you are dead: # if you have 3 living neighbors, 0 -> 1 # otherwise 0 -> 0 #else: # if you have 2 or 3 living neighbors, 1 -> 1 # otherwise 1 -> 0 import pycxsimulator pycxsimulator.GUI(title='My Simulator',interval=0, parameterSetters = []).start(func=[init,draw,step])

>>3179 ignore this part, I was trying to rush it to a presentation. this is a leftover from the original code I believe. #if you are dead: # if you have 3 living neighbors, 0 -> 1 # otherwise 0 -> 0 #else: # if you have 2 or 3 living neighbors, 1 -> 1 # otherwise 1 -> 0

>>3179 >nested loops 5 levels deep woah. Out of curiosity: how fast does it run?

>>3183 Kinda slow but my laptop is soykaf. I would expect it to return results at a reasonable time on a good setup.

For anyone new I would recommend Chapter 15 of The Computational Beauty of Nature covering: Basics, Wolfram's 1D CA, Langton's Lambda, Game of Life, Kauffman's boolean network for biological representation. The following chapter [16] looks at Autonomous Agents and Langton's ant and boids which is also interesting, maybe not for the same reaon

>>3179 At a glance it looks like when you update a node, its neighbors to the left and upper have already been updated and so it's taking their *new* state into account instead of their state at the start of the update

>>3187 That's the transient state. See >>3175 So if there are two overlapping -1s it becomes a 1. Is that what you were referring to?

>>3188 I don't think so but I'm not sure. Basically, you change the state of the pixel at (0, 0). Then when you go to update the state of the next pixel, and its looking at the state of its neighbors to determine what its state should be, it's looking at the just-now-updated state of the cell at (0, 0), not the state of (0, 0) at the end of the last frame

>>3190 You've got it correct. There are two subframes within one frame. First subframe assigns either 0 or -1. Depending on condition, second subframe assigns 0 or 1. Then nodes are swapped with environment and iterates to next step. If you think there's something logically wrong with the code representation (might very well be), can you recode it? Because I can't really say any more than this.

I had a thought. If you want to create a 1D cellular automaton, you could make it even easier than matrix multiplication and just use vector multiplication. It could potentially be the most portable, lightweight CA implementation yet. Given that rule 110 has Turing universality, you might be able to do a whole lot more with that than you'd think at first. I'm going to try to code this up myself, ideally in such a way that I can add things onto it later. Does anyone have any pointers on how I should do it? The tutorials I've looked at which don't use custom language-specific commands or libraries generally have CAs constructed as arrays, but other methods could exist.

>>2978 >>2987 >>3144 sorry, i lost track of this thread. the BLAS thing i mentioned was for approximating solutions to a particular integral equation.. so maybe not all that helpful if you just want to see a CA implementation. i can clean it up and post the relevant bits if you still want to see it anyway; the techniques would be the same. however, if you don't mind trading generality for speed i don't think you can do much better than the hashlife algorithm. i haven't read all the papers, but i'm pretty sure you could generalize it to neighborhoods of arbitrary size (at the cost of performance). >>3178 >CA-based neural network i'm not entirely sure what you mean by this. do you want to encode some kind of training algorithm into a CA, or do you just want an algorithm that can derive CA rules from a training set?

>>3227 >i can clean it up and post the relevant bits if you still want to see it anyway; the techniques would be the same. This would be a helpful reference when trying to do >>3195. >do you want to encode some kind of training algorithm into a CA That's the idea.

Tell me about non-deterministic automata and if it can be implemented to CA.

>>3195 Model ergodicity.

>>3251 What does this mean code-wise? I've never tried to do anything like that before.

>>3254 You might be pleasantly surprised to learn that although they are different concepts, both ergodic theory and cellular automata are the brainchildren of von Neumann. How I would begin would be to use Rule 18 CA as pic related. I have also attached two papers, one of them explaining Ergodic Theorem and the other explaining CA applications of ET. What your code would do, is initially declare a rule 18 setup as seen here: http://atlas.wolfram.com/01/01/18/01_01_1_18.html#01_01_161_18 Then, by using parts of the code here, >>3179, you will write a conditional that corrects the distribution if it goes to chaotic behavior. The Rule 18 begins as a Sierpinski triangle and then goes on unpredictable patterns. With your added conditional, you can block these unpredictable patterns, keep generating Sierpinski triangles, and log these changes to calculate how much entropy it costed. Good luck.

>>3268 Also probability vectors are a good idea.

>>3268 >>3271 My coding knowledge is based in C/C++, but I'm sure a basic if-else statement or a for/do-while loop should be enough to prevent chaotic behavior. I'd like to have more than one rule though. Never heard of probability vectors or a lot of this other stuff. I'm going to have to go over these papers. It does sound intriguing to model a CA's state changes ergodically though. What benefits can be gained this way?

>>3276 Ever heard of Maxwell's Demon? en.wikipedia.org/wiki/Ergodic_hypothesis Basically your demon'll be converting your PC's processor power into information to reduce entropy. The end conditions will have the same configuration as the initial ones so that will preserve ergodicity. Then you can compare the processing power spent in terms of how long does it take for one step to be calculated, and compare it with Rule 18 that doesn't run the conditional algorithm.

>>3276 when you're talking about dynamical systems (like CAs), the word "chaotic" has a pretty specific meaning. a chaotic CA configuration would basically be one that goes on forever without repeating itself. think fractals.

>>3279 This is true. In a chaotic system, a slight initial change can lead to large end deviations. >>3276 You should identify the initial deviations and correct them to maintain symmetry.

>>3013 I took a look at the CA wiki and it has many rules in it that I've never heard of before. It goes to show how versatile CAs are. I'll probably be referring to it more in the future. >>3278 >>3279 >>3287 I'm beginning to wonder if ergodic CAs should be considered their own category. It sounds like substantial changes to ordinary CA rules can be made this way. The idea was to exactly replicate existing CAs ergodically to save processing power, but the way you're talking about changing rule 18 makes it sound like something completely new.

>>3289 >exactly replicate existing CAs ergodically Really, I'm not even sure if this is possible or not, as I have no experience with ergodic theory.

>>3290 >>3289 I didn't know if CA was invertible. So I went and did this >>3167 Experimenting doesn't hurt.

>>3291 I think that's called a totalistic CA, actually, though the reversal at the end should warrant some distinction.

>>3289 >ergodic CAs What would it mean if this really was its own class and a member of it was proven to be computationally universal? I've asked myself this about many special classes of CAs. I'm probably getting ahead of the game here, though.

>>3293 >totalistic CA Never heard, I need to do some reading about this. >>3296 I think it's a step towards this: https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton)

>>3296 As >>2719 points out, not all CAs can have a Garden of Eden configuration. What would be particularly interesting is if a quantum, stochastic or other non-deterministic CA were proven to be computationally universal at the same time as the deterministic Game of Life and Rule 110. I suspect that ergodic CAs may hold the key to something earth-shattering that could potentially resolve such a paradox, but I lack the facility with them to find it out on my own. Right now I'm just trying to get a 1D CA program to work so I can do other programming and engineering projects with it. The only thing I can say about a potential ergodic CA class right now is that most of them would necessarily be of a non-deterministic type. Any interesting ergodic CA would have to have at least 3 possible states, and most likely a great multiplicity of possible states. In order for a 3-or-more state CA to be ergodic, you need more than one possible state transition at a time. The only deterministic CAs that could qualify as being ergodic are two-state CAs, or "blinkers" as they're called. Those would be trivially ergodic, as the ability to transition to any other state at any time isn't very interesting if there's only one other state that the CA could be in.

>>3317 >>3310

>>3317 >As >>2719 points out, not all CAs can have a Garden of Eden configuration. What would be particularly interesting is if a quantum, stochastic or other non-deterministic CA were proven to be computationally universal at the same time as the deterministic Game of Life and Rule 110. I suspect that ergodic CAs may hold the key to something earth-shattering that could potentially resolve such a paradox, but I lack the facility with them to find it out on my own. Now check this out: >In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. It can be the initial configuration of the automaton but cannot appear later in the evolution of the automaton. John Tukey named these configuration after the Garden of Eden in Abrahamic religions, which was created out of nowhere.[2] https://en.wikipedia.org/wiki/Ergodic_theory >For the special class of ergodic systems, this time average is the same for almost all initial points: statistically speaking, the system that evolves for a long time "forgets" its initial state. There is a possibility of Garden of Eden problem if we can create a teleportation from the ergodic state. It's actually done in the PageRank algorithm here >>3271 states that if a system is ergodic you should be able to teleport to any state you like when one path reaches a dead-end, and you reach the dead-end with ergodicity. >But, by Liouville's theorem, if all regions of phase space are equally populated at time, t=0, then they are equally probable for all time. It's a feedback loop, so to speak. >The only thing I can say about a potential ergodic CA class right now is that most of them would necessarily be of a non-deterministic type. Agreed. There's this (relatively) new paradigm that got forgotten called non-deterministic chaos. I think it holds the key and my current work is tied to that and to the ergodic theorem. I was reading this for my work when I suggested the anon for a CA >>3251

>>3326 >if a system is ergodic you should be able to teleport to any state you like when one path reaches a dead-end Wouldn't it be great if life was like that? Anyway, the more I thought about it the more I realize that an ergodic CA could be an excellent choice for embedded systems. It would certainly be more versatile than a standard CA, and possibly more efficient as well. If you want to modify the program, you could just modify your CA rule to add new states instead of adding a ton of new lines of code. If that neural network functionality could be integrated into it, it could even manage itself. Still not quite sure how to build a CNN with CAs, though.

>>3345 I found this https://pdfs.semanticscholar.org/f332/c1e17f87c6b068d97a73ccceab8bc3858eae.pdf

>>3346 >cellular neural network I didn't know this was already a thing. I was thinking of the convolutional neural networks described earlier in the thread. This paper even includes a small portion of sample code at the end, albeit in MATLAB which I don't use. Maybe some of the papers listed in the bibliography can offer more information. Going to have to look into this.

>>3347 Same, a lot of reading to do. I'll get back when I find time to work on some samples myself.

>>3246 I think a lot of people would like that. >>3326 >There's this (relatively) new paradigm that got forgotten called non-deterministic chaos. It would be interesting to hear more about this. My understanding of chaos is that it's deterministic but unpredictable due to sheer complexity, though I've heard of quantum chaos. The various interpretations of quantum mechanics differ in rendering it as a fully deterministic theory, a free will permitting theory or some form of compatibilism. There's even a cellular automaton interpretation of quantum mechanics conceived by Gerard t'Hooft. It's a deterministic theory which he outlines in a free book available here. https://www.springer.com/us/book/9783319412849?wt_mc=ThirdParty.SpringerLink.3.EPR653.About_eBook It's interesting, but it only uses classical CAs - at least so far. Discussion of this type may be too far outside of this thread's intended subject, though. Wasn't there a /sci/ board on the original incarnation of the site before it went kaput? Maybe we should ask for one.

>>3484 >It would be interesting to hear more about this. You wouldn't even find a single Wikipedia entry about it. In fact, there are 3 papers that have referred to it as: terminal dynamics , noise induced instability and non-deterministic chaos respectively. I've attached the last paper that references to the others. In chaos context, non-determinism is defined as behavior that generates a complexity onlook. >My understanding of chaos is that it's deterministic but unpredictable due to sheer complexity Chaos and complexity are two different things. Chaos is the significant deviations in the end result that is caused by minimal changes in initial conditions, or in other words, sensitivity in changes in initial conditions. It is deterministic, but not necessarily complex. For a system to be complex (could also be chaotic), it has to have a lot of interdependent acting variables. There are very simple chaotic systems in contrast, see Logistic Function or harmonic oscillator. That book will be handy, thank you. I don't know much about Quantum Chaos unfortunately.

I think I've wrapped my head around what would an ergodic CA aim towards: https://en.wikipedia.org/wiki/Loschmidt%27s_paradox#Dynamical_systems Current research in dynamical systems offers one possible mechanism for obtaining irreversibility from reversible systems. The central argument is based on the claim that the correct way to study the dynamics of macroscopic systems is to study the transfer operator corresponding to the microscopic equations of motion. It is then argued that the transfer operator is not unitary (i.e. is not reversible) but has eigenvalues whose magnitude is strictly less than one; these eigenvalues corresponding to decaying physical states. This approach is fraught with various difficulties; it works well for only a handful of exactly solvable models.[2] Abstract mathematical tools used in the study of dissipative systems include definitions of mixing, wandering sets, and ergodic theory in general.

>>3494 I don't know much about quantum chaos either. I don't know if anybody does. This is a lot of highly theoretical stuff. >harmonic oscillator In t'Hooft's book, he introduces a concept called the cogwheel model and uses it to construct what he calls a harmonic rotator, which is essentially a rotary analogue of the harmonic oscillator. I suspect a chaos theoretician could do a lot with that, but I'm interested in more practical applications. For that purpose, you couldn't do much better than the harmonic oscillator or a quantum harmonic oscillator. Still, I like reading about what the theorists produce. >>3495 I didn't realize anybody here would actually work on the ergodic CA concept. It's so far outside of my expertise that basically all I can do is sit here and watch as people with more experience figure it out. I'm sure everyone in this thread would love to hear any results you come up with, but I don't know how much help you'll get with it here.

>>3495 This ties into the discussion near the start of the thread about reversible CAs. An ergodic CA should necessarily have some form of reversibility - as it can go to any state at any time, it should be able to retrace the steps of whatever path it chose. It could also choose to behave irreversibly, though. As far as whether a non-deterministic CA can be computationally universal goes, I always thought that it was interesting how quantum and non-deterministic Turing machines could be universal at the same time as a classical Turing machine. Any route to proving computational universality of non-deterministic CAs and ergodic CAs in particular would likely be the same route used with many other systems, proving that it can emulate a system already known to be Turing universal. Maybe the relation between reversible and irreversible CAs mentioned in >>2718 could be useful here.

>>3517 I've given this a lot of thought today. This approach fits my model well, but I have no idea how to structure a CA around it. Here's the way I imagine it to work: I don't think you have to set up a CA with Turing machines in mind, since it's only a working model of an automaton and any super-Turing machine is only a theoretical concept. For solving such an ambitious problem though you have to abandon any route you know and construct your own. It has to satisfy: 1) time reversibility/irreversibility in a given setup random algorithms 2) non-deterministic finite automaton/dfa conversion power structure algorithms Reversibility is a requirement of Garden of Eden theorem and there can't be a Garden of Eden CA if a state function is surjective (has a predecessor) and injective where no two states are the same: https://en.wikipedia.org/wiki/Surjunctive_group Thus it becomes a decision problem that is built upon a backtracking search algorithm for the Garden of Eden, where we reach a previous state that generates the Garden of Eden. This state can be called the God state.

>>3532 And this suggests a solution to the Halting problem. >In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. So the search goes both ends: search for the Garden of Eden and possible latter stage configurations that can create the Garden. If the algorithm reaches the Garden -> run a probabilistic search, halt when you reach it.

>>3532 The Garden of Eden can't have a previous state or be part of a reversible CA though, unless you're talking about simulating an irreversible CA with a reversible one. An ergodic CA also shouldn't have an Eden state unless it's simulating an irreversible CA, and the only way for it to simulate anything else is if it was Turing universal. What type of model are you building and what are you going to use it for? >>3533 The halting problem is undecidable in some cases. I'm unsure what could be considered solving it in general or what you'd obtain with regards to CAs by doing so. Maybe an oracle machine could shed some light on the properties of an ergodic CA. That's just speculation, though, and it may be unfounded.

>>3534 >the only way for it to simulate anything else is if it was Turing universal. On second thought, this may not be true. I don't think all the d+1 dimensional reversible CAs simulating their d-dimensional irreversible counterparts are universal. An ergodic CA probably doesn't need to be universal to simulate just one CA...or does it? For all I know about them, there could be some property of ergodic CAs that requires them to be universal to simulate anything else at all because their rules are so batsoykaf compared to normal CAs. It'd be nice to have some defined criteria as to what's required to prove universality for an ergodic CA. Something along the lines of "if it can have this type of state, it's universal." It might not be that easy, though.

Loosely related since it's about GoL, pretty neat read though. https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life

>>3534 >The Garden of Eden can't have a previous state or be part of a reversible CA though, unless you're talking about simulating an irreversible CA with a reversible one Yes, think of it this way: Go back to Big Bang and get the Garden of Eden from there. Then, go to the end of known universe, max entropy equilibrium. If it collapses to Big Bang, halt at n-1 state. It's a loop, but technically it's not a predecessor, because it stops before the n state. >>3536 If you think of it, all of the halting problems and Entscheidungsproblems are proven in terms of Turing machines. Maybe it's about time to think beyond that limit. But you're right, needs a clear statement.

>>3539 >Then, go to the end of known universe, max entropy equilibrium This is the ergodicity ofc

>>3539 >Turing machines Turing machines AND lambda calculus. jammit

Well, seeing as we've been having so much fun theorizing what an ergodic CA could be like, why don't we try to formulate other potential classes of CAs? Even if ergodic CAs turn out not to have any special rules for when they can be Turing universal, there might be other CAs that do. It would most likely be too extreme to have a CA class that can either simulate no other CA or every other CA (could be wrong, though). It might be more reasonable to have a CA that's universal if it can simulate any member of a particular class of CA. These may or may not be ergodic. I think they're somewhat likely to be ergodic because of the constraints imposed on ergodic CAs. An ergodic CA is essentially a reversible CA that requires many potential states to be added to it, and this requirement may introduce new properties and possibilities. It can also be thought of as adding together numerous reversible CAs, if the notion of adding CAs together or more generally performing any kind of traditional mathematical operation on them even makes sense. If it does, it may end up being like linear algebra with its own special rules, or given that the grid-based nature of ordinary CAs closely mirrors the idea of a matrix, they may be exactly the rules of linear algebra. I'm not aware of any such thing currently, but it would be interesting to find out. Working on new classes of CAs ought to give us posting material for quite a while. Of course, I hope we can get some more immediately practical programming projects running as well, such as >>3022. This is a programming board, after all. The OP states that computer science applications are valid here, but even so, theorizing new CA classes at this stage is basically just throwing every dart you've got at the dartboard and hoping one of them hits the bullseye, so why not try working on one of the following: >CAs with odd computational universality conditions >Hybrid CAs >Higher-dimensional CAs that use even more abstract, topologically strange bases instead of a grid, triangles or even Voronoi shapes >Assuming regular CAs could be thought of as spacelike, timelike CAs >CAs that resemble Duck Hunt, complete with the laughing dog >CAs that by some arcane sorcery allow you to travel back in time and slap George Lucas at the exact nanosecond he thinks about making Jar Jar >CAs that resemble the Virgin Mary appearing in a tortilla

>>3542 >An ergodic CA is essentially a reversible CA that requires many potential states to be added to it, and this requirement may introduce new properties and possibilities. It can also be thought of as adding together numerous reversible CAs, if the notion of adding CAs together or more generally performing any kind of traditional mathematical operation on them even makes sense. If it does, it may end up being like linear algebra with its own special rules, or given that the grid-based nature of ordinary CAs closely mirrors the idea of a matrix, they may be exactly the rules of linear algebra. >>2965 >>3144 >>3227 This is pretty much what these posts are talking about with the BLAS library for C, and all the other posts about implementing a CA via matrix multiplication. A CA can also represent solutions of a differential equation, which can be operated on mathematically as they're functions (or can have closed form approximations operated on mathematically in cases where no closed form solution exists). I'd imagine you can do anything with CAs that you can do with matrices.

>>3542 >Higher-dimensional CAs that use even more abstract, topologically strange bases instead of a grid, triangles or even Voronoi shapes Recently a Game of Life was constructed on a torus.

>>3549 Got a link to this? Maybe we should be building a Game of Life on a Klein bottle or a Calabi-Yau shape.

>>3556 https://www.youtube.com/watch?v=lxIeaotWIks https://github.com/gollygang/ready https://gist.github.com/SeanBP/edfb9916713224971d35

>>3560 Good stuff. We need a lot more CAs with this kind of inventiveness. They may open up applications nobody could have foreseen.

>>3543 >I'd imagine you can do anything with CAs that you can do with matrices. I'd like to hear a lot more about this from our resident math gurus. You may be able to do even more with CAs. The use of new mathematical objects can open up new avenues of research, as happened when linear algebra offered a new approach to quantum mechanics when differential equations alone could no longer proceed.

>nerds have named an oscillation "french-kiss" https://en.wikipedia.org/wiki/Oscillator_(cellular_automaton)

https://pastebin.com/VQbgJSPh

>>3615 >Mars Attacks! Automata You magnificent soykaf.

>>3617 It can also be expanded with other atom words, but yeah, I also found funny what I was getting while deriving it

>>2719 >>3310 The Wiki article on the Garden of Eden mentions a novel called Permutation City in which the concept is used to prove that someone lives in a computer simulation. Is that actually a valid use of the Garden of Eden or of CAs in general?

Here's an article on how to generate Sierpinski Triangles from CA: https://www.johndcook.com/blog/2017/09/23/sierpinski-triangle-strikes-again/

https://pastebin.com/WyXH9b40

>>3719 explanation: testing the limits of arithmetics with only the +-()^ symbols

I have a schematics of a nacker and a unacker that I'll transcribe later

Ack W^X? -> Ack W^X. W*¬X. Ack W^X? -> Ack W^X. ¬W*X. Ack W+X? -> Ack W+X. W. Ack W+X? -> Ack W+X. X. Ack W*X? -> Nack W*X. ¬X. Ack W*X? -> Nack W*X. ¬W. Ack W=X? -> Nack W=X. W*¬X. Ack W=X? -> Nack W=X. ¬W*X. https://en.wikipedia.org/wiki/Propositional_calculus https://esolangs.org/wiki/Return-oriented_programming https://www.wolframscience.com/nks/

I spent a lot of time in high school messing around with CA's - they're a nice niche in CS that aren't really discussed a lot. Here's a neat thing I found while procrastinating a little while back: https://gfycat.com/gifs/detail/ScratchyIndelibleGrouper Sadly there's not much funding for research in these areas since everyone is going crazy about deep learning right now. There's a chance that the focus for machine learning may shift towards artificial life (which has some overlap with CA's) but as of now it's a dead field.

>I didn't realize anybody here would actually work on the ergodic CA concept. The prediction algorithm I am working on brought me back to automata. It will be a very neat Turing universal CA. See the attached pdf. Looks like Ergodic is back on the menu boys.

This >>4825 was for >>3515

>>4825 link for DL http://dev.whydomath.org/Reading_Room_Material/ian_stewart/CommutersandComputers.pdf

>>4825 That was a charming story. A thought that occurred to me is that the train is both undecidable and possibly intelligent. It leads to all sorts of questions about the computational nature of intelligence, or about whether undecidability implies non-determinism. Since it's made out of deterministic components it wouldn't seem so. It actually seems more like chaos, which can be unpredictable but completely deterministic. I'd love to hear more about how this relates to ergodic CAs. I want to be able to post "he actually did it, THE ABSOLUTE MADMAN" when a Turing universal ergodic CA is discovered. Instead, without having seen that yet I can only post "there ain't no gettin' offa this train we're on."

>>4854 I've read various things about other mechanical systems becoming intelligent, including rivers, billiard ball computers and Charles Babbage's Analytical Engine. If, as some have hypothesized, the entire universe is a computer, it may be intelligent as well, or capable of developing intelligence. It should be interesting to examine if those systems share the same undecidability properties with this train, and how much undecidability has to do with intelligence in general.

>>4854 I've started reading on Automata Theory to find that connection to the Ergodic Theory. Will post updates. >>4865 I imagine the undecidability to be chaotic in character.

>>4854 >>4865 For a definition of non-deterministic chaos, see the pdf in >>3494

Wow Lainons WOW Ergodic Theorem was directly referenced to in the groundbreaking 1938 paper of Norbert Weiner, "The Homogeneous Chaos", which gave the name to the Chaos Theory. W E W E W

Here is an interface for an artificial chemistry I designed. I guess it will be pretty obscure without context, I will give some later, but you guys can play with it. http://artlife.ml:51461/

>>5077 Looks really cool.

>>5085 I added tooltips to the buttons, it should be more usable now. I put a big molecule in the reactor, this molecule is an universal duplicator (except that it works in reverse order, because it was easier). It's grab pattern is DFDFFF which translates to something like D(D).* as a regexp (the F letter is used as a special character to generate a regexp from a string over the letters A-F). So the duplicator grabs any molecule starting with DD, and will duplicate it in reverse order. You can use the « simulation round » button to see the changes, and select the molecule of the duplicator to see the petri net and how it works

>>5077 >>5077 I know Petri Nets, what is the relationship of PNs with cellular automata?

>>5201 To be fair the relationship is rather thin. From Wikipedia about the Game of Life : « One interacts with the Game of Life by creating an initial configuration and observing how it evolves. » Evolve is the big word here, the Game of Life was an early attempt at designing a computer program that would emulate evolution. There have been some more attempts, namely Tierra (and Avida), and other simulation programs farther away from computers (more like toy chemical reactions in a 2D physical world, Hutton did some work in this area). This use of petri nets here is my attempt at designing a program that would emulate life. It's still at an early stage, but a universal replicator is already quite something I think, because reproduction is at the core of life features. And there are quite some extensions I have thought of that would give very nice results.

>>5203 >>5203 Since I already know PNs, I think I'll give cellular automatas a try. I have a simulator and space-state generator for colored petri nets that I made in Java, but I plan to recreate it on C++.

Looks like this is the place to ask, so here goes. I'm thinking about creating a CA on a hexagonal grid to be used to model and eventually regulate biological processes. I've done some research and the indications are that hexagonal CAs are particularly well suited to this, so I wanted to hear what people here thought. Why is a hexagonal CA better for this than a square or triangular grid? How difficult is it to create a hexagonal CA and what's the best method of doing it?

Physicist here. I work with quantum integrable (i.e. exactly solvable) models. In particular, I study spin chains, which models the evolution of a set of quantum spins on a 1d lattice. Typically, these have various quasiparticle excitations which can travel along the chain and interact in various ways, have bound states, exhibit phase transitions like from ferromagnetic to antiferromagnetic, etc etc. Practically all previously known exactly solvable models have had only 2-site interactions (like the heisenberg model: https://en.wikipedia.org/wiki/Heisenberg_model_(quantum) ) . I just found a solution to a wide class of models with nontrivial 3 and 4-site interactions, which allows the interactions to exhibit a wide range of behaviours that were not previously seen. For example, some solutions let me trap quasiparticles at specific locations, and throwing another quasiparticle at the trap will knock the old one out of the trap and replace it with a new one, kind of like the balls in a newton's pendulum or a billiard ball knocking another one. The previously trapped particle will continue out with the same momentum as the old one. By having different types of quasiparticles, I can use this to make memory cells. With scattering, I can build simple logic gates, including some quantum ones. At this point, I strongly suspect that I can get turing completeness from the interactions. In particular, it reminds me a lot of things I've seen in 1D cellular automata like the three spaceships that show up in the completeness proof for rule 110. I'm generally curious about constructions of turing machines in 1d cellular automata. The construction for rule 110 is really complicated, but that's partly because it only has two cell types. Does anyone have links to 1d CA's with simpler turing completeness proofs?

This thread had its activity die down somewhat in the last month or so, but I hope we can bring it back. People have doubtlessly been busy with school and work, but maybe over the holidays we can have some more productive things happening in here. I'd hate for >>5389 and >>5399 to have their questions go unanswered, and I want to hear from the guy doing ergodic CA research.

>>5508 > I want to hear from the guy doing ergodic CA research That guy here. Life hit me pretty hard, but I'll get back to it eventually.

Time to light a cozy holiday fire under this thread's ass. >>5582 Well that's unfortunate. Hopefully you can get back on your feet soon. I did some research for >>5389, and as it turns out, there are actually some cases where hexagonal CAs are easier to handle than square CAs. Hard to imagine at first, but it's true. This paper has more information: http://www.e-hilaris.com/MA/MA_8_2.pdf Essentially, reaction-diffusion processes, which are often involved in biological functions, proceed radially outward as diffusion tends to do, and because of this it's best modeled with a circular region. Anytime you need to model a circular region as a CA, hexagonal CAs are better than rectangular CAs because they have a neighborhood of 7 instead of the 9 on a rectangular grid, making them simpler to deal with for chemical reaction modeling. It's notable that the Game of Life has also been implemented hexagonally. I also hit upon a related idea when thinking about neural networks. Since I was trying to figure out how to implement a radial basis neural network as a CA, I thought maybe there should be radial/circular cellular automata defined not on a grid of polygons, but on a series of concentric circles. I searched for CAs of this type and almost nothing came up, so it may be a completely new type of CA. The only thing I could find was an almost-circular CA made by Stephen Wolfram that mimicked a circle pattern on a conventional square grid. I'm probably going to have to take this to the machine learning thread. I hardly dare to speculate about the potential applications of a radial CA. You could use concentric squares or triangles on those types of grids, but I'm unsure what you'd accomplish by doing so. It seems like concentric circles would do the same things, whatever they are, with less complexity. Anyone want to help out with this?

>>5718 To add to this, because of the Voronoi shapes being able to accommodate a CA, I'm betting that any combination of shapes whether curved, polygonal or half-and-half that fit together with no gaps between them can accommodate a CA, and that this extends to figures in any number of dimensions. A circular CA would be the simplest form of this because it would have a neighborhood of only 3. In some ways it'd be the same as a rectangular 1D CA. I wonder if there's really a meaningful difference between the two. Maybe that fact can be leveraged for the purpose of modeling things that hexagonal CAs are currently best suited for.

I just had something that only qualifies as a thought by using a very generous definition of the word: rendering the special zones from Sonic 3 & Knuckles into the form of cellular automata and coming up with rules to generate new stages in that mold. Am I going to turn into Chris-chan now? I'm scared.

https://arxiv.org/pdf/1609.05240.pdf

>>5751 I would play the fuarrrk out of Sonic The Nanite. Use the Sperg, Molly, use the Sperg.

>>5751 Definitely do it.

>>6035 >A particle, or gliders, is a key component of the collider. The glider is a finite-state machine implementation of a propagation localisation. A solitary wave, or an impulse, propagating in a polymer chain could be a phenomenologically suitable analog of the glider. A wide range of polymer chains, both inorganic and organic, support solitons. We believe actin filaments could make the most suitable substrate for implementation of a cyclic tag system via linked rings of CA colliders. Actin is an important motor protein. Actomyosin complexes are responsible for muscle movement. You could make artificial muscle or even programmable matter out of this. Or maybe one, then the other. You could probably get programmable matter to act in the same way as an artificial muscle while still retaining its ability to do other things. Would it be better to do that or to just try to create artificial muscle on its own? Maybe there should be a /diy/ thread about this because now I'm interested in the idea.

I suspect that at least some CAs would be good candidates for being programmed recursively. I wasn't able to find much about this when I did some searches, so maybe the notion has rarely been considered before. As much as it usually uses much more memory, there are some cases where programs relying on recursive functions can be made to run just as fast as conventional programs relying on iterative functions, or rarely, even faster. It seems to me that any program based on the notion of state machines should at least be considered in this light. In my programming classes, recursive programming was strongly discouraged because it's usually memory-intensive, but it produces undeniably more maintainable, compact programs which are easier to read and write. Actually I think I'm going to go start a thread about recursive programming. It's mentioned in a few other threads, but there isn't one specifically for it. I'll link back here in that thread so we can get something going pertaining to recursively programmed CAs. Recursion always gets a discussion going in any programming community, and the possibility of using recursion here might pull in some people who would otherwise be uninterested in CAs.

>>6147 To program something recursively, you need a recursive structure. As CA live in a 2D grid, there is no immediate recursive structure to use. You could view your 2D grid as a recursive tree : start with a square of a given size, then aggregate squares by group of 4 to obtain new squares. The general pattern is then to calculate the change of state in each of the squares, and then to the upper square by looking at what happens on the borders of internal squares, but I don't think this pattern would be so efficient with CA, since you always have to take borders into account.

>>6174 >To program something recursively, you need a recursive structure. So in order to understand recursion, you must understand recursion. >As CA live in a 2D grid, there is no immediate recursive structure to use. This thread is full of examples of CAs being made on all kinds of grids of any number of dimensions and shapes. That said, it probably isn't beneficial for this application to take most of those into account for reasons which will be outlined below. >You could view your 2D grid as a recursive tree : start with a square of a given size, then aggregate squares by group of 4 to obtain new squares. The general pattern is then to calculate the change of state in each of the squares, and then to the upper square by looking at what happens on the borders of internal squares, It makes sense to view each node of a grid as a recursive structure, since a CA is essentially an array of finite state machines, and unless you're using Voronoi shapes or doing other weird stuff, they're going to be identical. You may have to write a function that calls itself multiple times in order to get results with a recursive CA, since a CA works by having each node of the grid change based on the states of the nodes in its neighborhood. The computational overhead would scale up massively with the number of times you need to make a recursive function call, so in order to keep it feasible, your choices for recursively programmed CAs are probably limited to 1D CAs. >but I don't think this pattern would be so efficient with CA, since you always have to take borders into account. There are several different ways of handling the borders in an iteratively written CA, and there are probably several ways you could do it recursively. 1D CAs are often set up so that when you reach the last node in the line it loops back to the other end, and that could be done in iterative or recursive style.

>>6181 It's important to remember that when you're talking about recursive structures it's the sum of the parts that makes up the structure. Some examples of recursive structures people often cite are staircases, factorials and the above-mentioned Sierpinski triangle. If you add a stair to a staircase, you get another staircase. If you multiply a factorial by an integer one number higher than the previous factorial, you get another factorial. If you have an equilateral triangle and you add two more similar triangles, you get the True Force to rule the universe - I mean another triangle. Likewise, when you have a neighborhood in a CA and you add some more nodes to it, it becomes another neighborhood. You could also consider the CA as a whole a recursive structure. You have a rectangular grid, you add another iteration to it and you get another grid. A node in a CA is generally square and squares are rectangles, so adding more nodes to it creates another rectangle, but that's not the most important sense in which it's recursive. It becomes meaningfully recursive because you're evaluating several nodes' states together to get another state. In that way, everything could be said to be recursive in some sense, because the universe is built on math and every number can be made by adding other numbers together, and indeed it's been proven that it's possible to write any program recursively, so nobody needs to worry that it might not be possible to find a recursive structure to use to write a recursive program. It's just not always practical to use recursion. I can't imagine trying to base a 3D CA on it.

A few things caught my interest here. Some people were talking about CA-based programming early in the thread, but what this actually consists of was only briefly touched on. Embedded systems and training algorithms for neural networks were brought up, but not much was made of the larger question of automata-based programming as a paradigm, and there should definitely be more emphasis on that considering the board topic. To that end, it's worth asking what exactly you want a CA to do for your program. Are you looking for a CA that can serve as a program for some purpose, or to write some other code for you? Is there some pressing reason you'd need a program that can switch between several different CAs, or to have a genetic program or neural network that uses or generates them? If you can answer these questions, you should be able to create a CA for almost anything. >>4854 This post would be better with a non-deleted picture. Should've posted the Guard Scorpion instead, like so. People apparently love robots and videogames here, which is cool, because robots and videogames are awesome, and STEM communities tend to have a high concentration of people with those interests. Maybe what we should be doing with CAs is programming robots. In the recursion thread I made, I mentioned that I've read people saying they use recursion when coding pathfinding for the various moving objects and entities in a videogame. Pathfinding is also needed for making autonomous mobile robots. It's not impossible to theorize CA-based systems for either autonomous bots or remotely controlled ones, and if one was going to do something with recursively coded CAs, that may be a good candidate. Robotics-related CA discussion is something this thread should have and that I think many people here would like. AI discussion could also fit into that. Incidentally, I'd love it if there was an /m/ board here. Lainchan would be a great place to discuss all things /m/echa related, including robots, power armor and cyborgs. But until an /m/ board is created, we're limited to discussing how to actually program and build those things in real life. That's not really that bad of a limitation, is it? Maybe there should even be a whole imageboard dedicated to /m/, but I don't know if there's enough of an audience for it and this isn't really the place to request new boards anyway.

>>6174 the problem with alot of CA's is that they're iterative. Meaning that generally speaking, the origin [0,0] will generally take precedence in figuring out how the rest of the actions take place. Take the game of life. Generally speaking, I suspect that alot of the genuine effects of a cellular system IRL fails since all actions are computed in real time for each "segment" where as most computational CA's iterate. What would be interesting is a game of life version where one uses the life of a cell to determine precedence for eating, and eventually dying as it's "telomeres" generally kill it off (ageing). allowing for a more natural simulation.

>>6334 I can't believe I haven't seen a CA in that mold before. That seems like it might fall under the category of life-like CAs, but it doesn't strictly meet the definition of them given in the wiki article. Incorporating more features of living cells like eating and aging would be a great advancement over what's common with CAs right now. >Generally speaking, I suspect that alot of the genuine effects of a cellular system IRL fails since all actions are computed in real time for each "segment" where as most computational CA's iterate. Is this meant to suggest that recursion would be better to model biological or bioinspired IRL systems? I don't quite get what you're trying to say here. Some more elaboration would be both appreciated and potentially very interesting.

>>6335 Just think it out a bit. You have to loop (or recurse) but the computed next state start from [0,0] to [n,n] by advancing on each cell. Now, it would take some tweaking and careful consideration, but essentially using parallel processes. Computing each element at exactly the same time. Which is why you'd need some sort of fitness check to determing what cell eats whom in the game of life analogy. Which is why a genetic or darwinistic component would be needed to referee each cycle.

>>6336 And I suppose this fitness check would be whatever you want to call the type of CA rule this uses. >Which is why a genetic or darwinistic component would be needed to referee each cycle. Genetic CAs, then? That might also lead to a memetic CA, whatever that involves, or in any event to a much more general class of bioinspired CAs mimicking all sorts of biochemical systems. For the purposes of genetic CAs, cells don't necessarily have to eat each other, though. They could eat some magical third-party source of food and have the CA rule prioritize which gets the most of it, or you could have some other system I haven't thought of. If you start thinking this way, you could consider a CA that doesn't use these systems as a CA where everyone gets an equal amount of food. How would you handle aging, though? The possibilities are numerous. >>6337 >so eager to post in the thread he forgets to type anything Seems like CAs are getting pretty popular, lel.

>>6338 I decided to search for information on genetic CAs with the thought that someone might have already considered them, but the only thing that's coming up is stuff about using genetic programs/algorithms to find CA rules to model DNA mutation. There's nothing about having the CA rule itself incorporate a genetic algorithm. Based on this, I strongly doubt that any of these potential CA categories have ever previously been investigated. Of course, there's a good supply of information on genetic or evolutionary algorithms, and I'm sure much of it could be applied here. It'd be appropriate to make a distinction between genetic CAs and evolutionary CAs. The idea with the cells trying to eat each other definitely falls into the latter category, as genes don't eat each other when replicating. A genetic CA would be something like a 1D CA where each iteration represents a DNA strand. The black cells are coding segments and the white cells are non-coding segments. Since genes don't always replicate exactly, sometimes mutating, the rule needs to take that into account, and that's the number one thing that you need to know how to do to make a CA of this type. I'm going to have to think about this some more before I can say anything else about what a genetic CA would be like, let alone how to extend whatever lessons it can teach to biochemistry in general.

>>6339 A close form could be Avida (although not really a CA).

>>6334 >>6335 >>6336 >>6338 >>6339 https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor This sounds like the goal here with this talk of genetic CAs and evolutionary CAs. The implementations listed in the article are very complex, though, most of them featuring over two dozen possible states per cell, and all of them are in 2D. I don't know if it's doable in 1D even with significant departures from how the existing rulesets are constructed.

>>6344 https://en.wikipedia.org/wiki/Langton's_loops A related article for those who want CAs for use in applications that don't require computational universality, which should be most of the things mentioned in this thread except AI. Langton's loops sacrifice universality for simplicity while retaining the self-replication capability vital to modeling so many biochemical reactions. If you want something to build an entirely new class of genetic CAs on, this is undoubtedly a less troublesome candidate than a von Neumann constructor.

>>6345 Genetic CAs as described here would just be a subset of the more general class of stochastic CAs. Their capacity for self-replicating behavior would distinguish them from other stochastic CAs. Some stochastic CAs already feature self-organizing behavior, so adding self-replication seems like a logical step to take. You could also make evolutionary stochastic CAs, but I don't think they'd be a strict subset. Chemical reactions involving basic, well-known chemical species can easily be modeled by already-existing stochastic CAs without a self-replication component, or even with ordinary CAs, even if the substances in question can be fairly complex. It's only when biochemistry is invoked that self-replication becomes desirable. A stochastic CA at its core is just a CA that includes a probability distribution of some sort in its ruleset. The question is how to choose a ruleset that creates self-replicating behavior, and how to do it simply enough to make it useful for many applications.

Notably for the purposes of the above discussion of genetic CAs, Rule 90 features self-replicating behavior in a 1D CA, and it can be used to emulate the Sierpinski triangle, but it's not stochastic. Many other 1D rules can also generate the Sierpinski triangle and Rule 90 in general. Additionally, as CAs with self-replication can be seen as tree structures, and handling trees is one of the few situations where you don't lose anything from using recursion in your code, and can even make substantial gains as posited by >>6174 and numerous other sources, the answer to the question posed in the OP of the recursive programming thread that spawned from this one is probably as follows: The best CA-related use of recursive code is for CAs that feature self-replicating objects. All other CAs should be coded iteratively. That deserves to be posted in the recursion thread as well. As for the things being discussed in the posts here about recursion, biological systems would best be simulated by a CA that combines self-replication and self-organization. In biology, DNA transfers its code to RNA, which then creates the proteins that make up the cells and organs of life. This is the popular although incomplete form of the central dogma of molecular biology. DNA can also replicate itself, and some other interactions can take place, but in general it goes DNA -> RNA -> protein. Just because a structure self-organizes doesn't mean it'll be a recursive or self-replicating structure. Protein folding involves a healthy degree of self-organization, and yet proteins don't replicate themselves.

>>6351 >proteins don't replicate themselves. Actually, while this is true for the most part, there are certain phenomena related to proteins that do feature self-replication, like prion proteins forcing other proteins to replicate aspects of their structure, as well as self-replicating peptides. If you want something that combines self-organization and self-replication, there's also a class of readily foldable molecules called foldamers, some of which are self-replicating and some of which are protein-related because they mimic peptides. https://www.scientificamerican.com/article/life-rsquo-s-first-molecule-was-protein-not-rna-new-model-suggests/ According to the model this article talks about, foldamers formed an autocatalytic set of molecules that replicated themselves into the predecessors of biological life. Autocatalysis is described mathematically by the Lotka-Volterra equations, a system of nonlinear differential equations. Linearizing it to make it easier to handle yields a solution that mimics simple harmonic motion. If you want to code a CA that fits this model, it should be easy to do so recursively due to harmonic systems having a wave nature that fits the idea of recursion in much the same way that a staircase does. This CA may not have any uses outside of foldamers or prions, though, but those alone should be able to keep anyone interested in them busy. Prions are responsible for mad cow disease and Alzheimer's, so if you're into researching that, this is the CA for you. Foldamers on the other hand may have numerous areas of application in chemistry, medicine and more. Stochastic CAs in general have a long list of applications you can easily find by looking at the Wikipedia article on self-organization. One of these areas is neural networks, and considering the discussion of those earlier in the thread, I'm surprised it wasn't brought up more often. At any rate, if you want to know more about this, we need to get someone in here who's extensively studied Rule 90 or any other rules involving replicators to give us some details on how they might best be converted into stochastic rules, because my own knowledge in this area is lacking.

>>6353 Well, I have good news and bad news. I've been doing some followup on this and while trying to figure out how to create a stochastic CA out of Rule 90, I remembered reading that Stephen Wolfram used Rule 30 as a random number generator in Mathematica, so I thought "If you want randomness in your CA, why not just use another CA?" It's also worth noting that the Wikipedia article on Rule 90 states that it's random given random initial conditions, but in a turn of events typical for Wikipedia, this point isn't given a terribly clear or complete description (or elaborated on at all for that matter), and nothing else I've been able to find has shed much light on it, so any help from other posters here would be great, because as I understand it, Rule 30 generates randomness (or at least pseudorandomness) for all possible initial conditions, so I'm unclear as to why initial conditions would have any effect on whether Rule 90 is random or not. Some of the papers I've been reading about random CAs seem to draw a distinction between them and stochastic CAs at some times, while at other times treating them as though they're the same. Needless to say, this is extremely confusing for someone who's never done anything with stochastic CAs before, and the confusion is compounded by what I'm going to describe in the next section. >>3542 >Hybrid CAs Until now I was unaware that any work had been done on this, but I found some papers about developing hybrid CAs for the purpose of making RNGs for use in cryptography. All of them were from the last 2-3 years, meaning this is a very, very new area of CA research. Problem is, in order to construct anything that could properly be described as a genetic CA, you need repeating patterns, but in an RNG for cryptography you don't want repeating patterns because they could be used to predict the RNG and break the code. Also, I'm not a cryptography expert, but from what I've been able to find, both Rule 30 and ordinary CAs in general appear to be deprecated in this regard, judging both from stuff I've read from people in cryptography and the fact that Wolfram stopped using Rule 30 as an RNG in newer versions of Mathematica. This deprecation would explain why hybrid CAs are being developed for RNGs, but what's being talked about here is different. In order to properly emulate biochemical mechanisms, the correct balance of randomness and repetition has to be present. I'm interested to see what a hybrid CA that mixes Rule 30 and Rule 90 would be like, but I also want to understand how Rule 90 by itself can be random, because if I understood that, I could just use Rule 90 under a suitable set of initial conditions, and it'd basically amount to a genetic CA in 1D. It'd be worth it to compare the two approaches, and to combine the data gleaned that way with what's already known about deterministic life-like CAs to create genetic CAs in all shapes, sizes and numbers of dimensions. >>3689 This article came up when I was searching for this information. The very next post on the author's blog is about CAs with random initial conditions, but much like the Wikipedia article, he doesn't explain what it takes for the initial conditions in a CA to be considered random. This whole post is basically a call for help on a couple of crucial points, because the explanations I've been able to find up until now are missing vital information.

>>6351 >Notably for the purposes of the above discussion of genetic CAs, Rule 90 features self-replicating behavior in a 1D CA, and it can be used to emulate the Sierpinski triangle, but it's not stochastic. Well actually, I guess maybe it is, sort of. None of the elementary CA rules appear to be stochastic or random at first glance, but there was that bit with Rule 30, so apparently they can be, somehow. I really don't know what's going on with this. Help is urgently needed.

>>6375 >>all the last few posts This topic is going to take some doing to get through. Not only is the Wikipedia explanation of how randomness works in Rule 90 not terribly clear or complete, even the articles pertaining to Rule 90 on MathWorld and LifeWiki are missing some important points. Here's a paper from Stephen Wolfram about randomness, which includes a lot of material about CAs. It may not have everything everyone here wants, but it's better than Wikipedia. www.stephenwolfram.com/publications/cellular-automata-complexity/pdfs/origins-randomness-physical-systems.pdf And here's another paper from Wolfram describing how randomness is generated in CAs. http://www.stephenwolfram.com/publications/academic/random-sequence-generation-cellular-automata.pdf I think these "genetic CAs" as they're currently described here will simply wind up being computationally universal CAs instead of having a special class all to themselves. In Wolfram's classification system (which admittedly hasn't been rigorously proven to be valid, so your mileage may vary), Class 2 CAs exhibit oscillatory behavior and Class 3 CAs exhibit randomness. Class 4 CAs are frequently characterized as combinations of the behaviors shown in Class 2 and Class 3, and Wolfram has conjectured that all Class 4 CAs may be computationally universal. Since replicators can be emulated by oscillators, a CA that exhibits both self-replication and randomness will probably be Class 4 by default. This view is supported by the fact that using DNA as a computing substrate has been shown to be possible. https://en.wikipedia.org/wiki/Transcriptor This is the biomaterial analogue of a transistor. Other possible biological computing systems exist that use peptides or XNA in place of DNA. It's a burgeoning field all its own. Maybe there will be some hybrid CAs that represent algorithms optimized to run on biological computers, but we're probably a ways away from knowing that for sure. Also, I think the reason neural networks didn't get talked about here as much as one might think is because Wolfram says CAs aren't good at modeling them. I don't necessarily agree with that, but as he's contributed a great deal to the field, many people take his opinion seriously.

>>6379 These papers from Wolfram have a lot of good information about randomness, though I think they could be worded a bit better. This post will hopefully explain enough about what's going on in them so that anyone in the thread who's wondering how randomness works in CAs will be able to understand it. Here's another paper on randomness: https://www.tcm.phy.cam.ac.uk/~tmf20/PUBLICATIONS/epl_08b.pdf This basically says that randomness can either arise as an emergent property of the time evolution of a deterministic CA, or it can be embedded into the update rule as a stochastic CA. Either one is a valid form of randomness, so if you're looking for a CA to simulate some biological process or chemical reaction, you should first check if you can use one of the deterministic Class 3 CAs, because chances are it'll operate like a stochastic CA for many if not most purposes. So now that we understand a bit more about how the properties of stochastic CAs compare to those of random deterministic CAs, we need to take a look at the other half of the question and understand how randomness is generated by deterministic CAs. To do that, we need to read Wolfram's material. Now Wolfram's papers are a bit special. His paper on the origins of randomness uses the ideas of homoplectic and autoplectic systems, which for some reason seem to be in very few other publications. A homoplectic system will produce random output only when given random input, while an autoplectic system will produce random output no matter what kind of input it's given. Obviously, all stochastic CAs are autoplectic, but deterministic CAs can be in either group, or they can feature no randomness at all. >>6374 >as I understand it, Rule 30 generates randomness (or at least pseudorandomness) for all possible initial conditions, so I'm unclear as to why initial conditions would have any effect on whether Rule 90 is random or not. The concept of homoplectic versus autoplectic is the other half of the answer to this. Rule 30 is an autoplectic system. But this still doesn't answer what exactly random initial conditions are as opposed to simple initial conditions. Fortunately, once you think about it a bit and read Wolfram talking about periodic initial conditions, it becomes clear. Basically, the types of inputs you can have are analogous to the classes of CAs themselves. Class 1 CAs have simple rules that terminate in every cell being one color, Class 2 CAs are oscillators and Class 3 CAs are random. This analogy yields simple, periodic and random inputs. As an example, supposing you have a 7x7 grid of squares for a 1D CA with 2 possible colors represented here by 0 and 1, a simple input would be (0,0,0,1,0,0,0), a periodic input would be (0,1,0,1,0,1,0), and a random input would be (0,1,1,1,0,1,0). Simply put, randomness in the initial conditions is defined the same as randomness in the CA rule itself. Randomness in general is defined as the lack of a pattern, as the paper in this post specifies. CA outputs that have sufficient levels of randomness to make patterns in them nonexistent, or at least computationally intractable to find, are used for things like RNGs and encryption. You can use any type of input with any type of CA, and the results you get will be dependent on the rule's traits. As mentioned above, Rule 30 will generate randomness no matter which type of initial conditions it's given, while Rule 90 will generate randomness if given random input, but if given the particular simple input listed above with only one cell active, it'll generate the first 7 iterations of the Sierpinski triangle, which makes Rule 90 homoplectic. With this knowledge, you should be able to see how to handle randomness in CAs. I think this clears up the considerable amount of confusion here. To me, one of the major reasons CAs aren't more popular is that much of what's out there about them isn't written to be accessible. This is also the case for textbooks and scientific literature in general, but that's a problem far beyond anything that's going to be solved in this thread.

This thread has now lasted for 6 months. Do threads on anime internet goddess imageboards get anniversaries? At any rate, I think it's gone pretty well. There are many fun projects and ideas here, and I hope we see many more. We're over halfway to the bump limit, so when the thread starts nearing its end, we should be thinking about packaging all the resources here into a convenient format to put in the OP of the next CA thread.

>>6421 Happy anniversary Lain!

>>6422 Pour one out into the Wired for us. Another reason I think CAs aren't as popular as they should be is because many engineers and scientists don't see the point in using CAs in their programs over just working out the differential equations and coding things that way. I think there could be a resurgence in CA research and popularity if they were known to have a clear advantage in terms of portability, maintainability and efficiency, especially for difficult equations which are traditionally solved with numerical methods for lack of an analytical solution, as nonlinear PDEs so often are. There's also particularly thorny classes of equations like stochastic differential equations, which are a nightmare both to work out on paper and to implement into a program. That's why they tend to get linearized for many purposes. Most systems in nature are nonlinear, but people generally try to keep commercial technology to the linear realm. It'd be nice if we could get some mathematicians in here to help us put together a list of pros and cons for each approach.

>>6393 Turns out a third paper from Wolfram spells out exactly this definition of randomness. Why this isn't in practically every article about CAs is a mystery considering how important it is. CA literature needs a serious overhaul. http://www.stephenwolfram.com/publications/academic/cellular-automaton-continuum-systems.pdf

>>5582 I got back on track and did some research on ergodicity in CA. There are a number of papers describing ergodic behavior or calculating the entropy of a CA etc, but I haven't seen a simple, clean, applicable approach. Mostly theoretical work. The attached series of lectures from University of Manchester define ergodicity rather neatly. >Definition. Let (X, B, µ) be a probability space and let T: X → X be a measure-preserving transformation. We say that T is an ergodic transformation (or that µ is an ergodic measure) if whenever B ∈ B satisfies >T−1B = B then µ(B) = 0 or 1. The [0,1] probabilistic distribution for the ergodic definition fits CA very snugly, especially on the mapping. There are interesting papers on Probabilistic CA (PCA) if you'd like to read further. Instead, I am going to write down a protocol based on the Card Trick section in the Lecture 22 attached. SYNCHRONIZATION PROTOCOL FOR ERGODIC CA 1) For simplicity, the range of numbers used in the probability distribution will be limited from 1 to 4 (inclusive). 2) Assign a number for decks used, either 2-3. This will be a direct analogy of the card trick told in the lecture. 3) Assuming a 2 deck shuffle, the overall map size becomes 32 (4 cards each for 4 numbers, 2 decks, 4x4x2). Add up the values of each number in the shuffle ((4x1 + 4x2 + 4x3 + 4x4) x 2). This will be the deck size. 4) When the CA starts its first step, it generates a random number between 1-4. We call this the initial number. Decrement the chosen number's amount and deduct this number from the deck size. Note: This is a 1D CA, so the map is of size 1x32. However, if there are more than one initial numbers drawn (more than 1 players as described in the Card Trick), the map size will increase exponentially in 2D. 2^2 for 2 drawings, 2^4 for 4 and of course, a 32x32 for 2^5, 5 initial numbers drawn. 5) After the initial number, CA redoes the generation. This number becomes the new number. CA maps the initial number distribution. 6) Based on the initial number, CA allocates a number of generations in the next step (if initial number is 2, 2 generations). The last number of this generation becomes the new number. For the new number generated in 5), distribute. 7) Repeat 6). Decrement and deduct until the shuffle is emptied and the numbers are spent. The end result is called a synchronizing block. Again from Lecture 22: >Suppose the sequence of cards 4; 3; 2; 1; 1 occurs somewhere in the pack. Then, no matter what number a person has, they will eventually enter this finite block; once this finite block is entered, the person will always end up at the final 1, after which all audience members will always have the same number. Call such a block a `synchronising block'. There are lots of synchronising blocks (for example, 2; 1; 2; 1; 1 is another synchronising block). >The shift map on the one-sided full 4-shift SIGMA4 is ergodic. Hence almost every point in SIGMA4 visits a synchronising block innitely often. Hence it is highly likely (exactly how likely can be made precise) that a particular shuffle of cards (which corresponds to the initial few symbols in a typical point of SIGMA4) contains at least one synchronising block.

>>6533 I don't always get a chance to come here as often as I'd like, but I make it a point to pop in every now and again and see what people have come up with. I hope others are doing the same, because it's worth it. I was just reading about converting asynchronous CAs into block-synchronous CAs the other day and this explains the concept of synchronizing blocks better than what I was reading. Of course, formulating it as a card trick is pseudorandom instead of truly random, but for it to be truly random it'd have to be formulated with quantum mechanical systems. Is a synchronizing block absolutely necessary for an ergodic CA though?

>>6537 I'm flattered, thank you. I'm quite new to CA, but one thing I've noticed is that with CA, less is more is much much more pronounced, because that's how CA is designed in the first place. That's the beauty of Game of Life. So instead of digging through piles of papers, I just skim through them to find something like the card trick that I felt suitable enough. Game of Life is a complex system and I've employed the same approach in other complex systems, which also proved to be much more fruitful than conventional approaches. > but for it to be truly random it'd have to be formulated with quantum mechanical systems Absolutely. That's where I stop, because it grows too thick for me to tackle it right now. Unless I find a bootstrap of course. https://en.wikipedia.org/wiki/Subshift_of_finite_type Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. >Is a synchronizing block absolutely necessary for an ergodic CA though? Not necessary at all. This is based on Birkhoff's Ergodic Theorem, which is just one of many definitions of Ergodicity. The reason why Birkhoff's Theorem proves to be handy is that it equates space averages with time averages over almost everywhere. This is possible in finite mappings, and these properties are just tailor made for CA. ERRATA for >>6533 The bold section > However, if there are more than one initial numbers drawn (more than 1 players as described in the Card Trick) does not describe the Card Trick accurately. I've reread it, it appears the trickster plays each audience member separately and compares the results afterwards. I find the simultaneous play much more enticing and challenging.

>>6543 This is pretty good for someone who's new to CAs. What made you decide to get into them, particularly the concept of ergodic CAs? Are you going to try to get anything you find in this area published?

>>5718 The fundamental problem is that when you have what's supposed to be a radially symmetric continuous model, and you try to approximate it with a rectangular discretization, you end up with something that's no longer radially symmetric. Hex grids do a better job than squares, but they're hard to code. I'm studying solutions to 2d neuronal filter models, and i'm trying to overcome this exact problem. Pic related is my rendering of the evolution of a circular initial condition in a 2d neural lattice with cyclic boundary conditions. The kernel is radially symmetric, and nearby cells excite eachother while remote cells inhibit. in other words, if d(x,y) is the euclidean distance between two cells, then the connection weight between them is given by: w(x,y) = {1 : d(x,y) < r; -0.06 : d(x,y) >= r} for some radius r. Notice that the radially symmetric kernel and initial condition produce a solution pattern that is not radially symmetric. This is not supposed to happen. It is the result of the choice of rectangular discretization.

>>6552 It's been a while since >>5718 was posted. Glad at least somebody here is doing something with it. >Pic related is my rendering of the evolution of a circular initial condition in a 2d neural lattice with cyclic boundary conditions. You should go to /drg/ and show this to them. I'm sure they'd appreciate it. It looks like something you could watch for 4 hours while stoned out of your skull. I don't know much about neuronal filter models or neural lattices, but maybe you should use a triangular grid. It might be easier than a hex grid.

>>3268 This post from a while ago talks about Rule 18 and generating Sierpinski triangles that veer off into chaotic patterns, which is an odd occurrence. Rule 90 can generate either a Sierpinski triangle or randomness, but not both at once as far as I know. Still, it's worth asking if there's some method unknown to me of making Rule 90 act like Rule 18. This post was originally made in response to a request for assistance in building a neural network out of a CA, so if there is, then maybe it could be done with Rule 90 instead of Rule 18. But then it and >>3251 ended up spiraling into the discussion of ergodic CAs which became fascinating on its own merits. This may be grasping at straws, but if Rule 90 contains any link between the two discussions, it'd be very enlightening to find it. >>6351 >Many other 1D rules can also generate the Sierpinski triangle and Rule 90 in general. Is there a link between all of them, then? Maybe even one where Rule 90 is the chain binding them together. According to Wikipedia's Rule 90 article, Rules 18, 22, 26, 82, 146, 154, 210 and 218 are the other ones that generate the Sierpinski triangle. Rule 90 is said by Wolfram to be the simplest nontrivial CA. Any of its chaotic patterns is a superposition of Sierpinski triangles, so it seems at first glance that you could make Rule 90 behave kind of like Rule 18 by having simple input with a handful of active cells set very far apart, so that Sierpinski triangles are generated which then start interacting in a way that produces random patterns. Is that truly enough to duplicate Rule 18's behavior, though? >>3605 This deserves an answer for curious readers. Additive cellular automata are CAs that you can do math with, but you can't in general add, subtract or do other mathematical operations on CAs. Rule 90 is one of the additive CAs, incidentally.

>>6551 I was introduced to CA in a complexity course and I promptly went on and wrote this manipulation of GoL: >>3167 >>3175 >>3179 This work laid dormant for a while until I realized my model which I’ve been developing is essentially aiming to become a Maxwell’s Demon to reduce a system’s entropy. That’s when I decided to couple CA with the Ergodic Theorem, because I imagine autonomous agents will be needed in synchronization.

>>6571 Will I be able to publish any results? I don’t know. I’m trying to generate a synchronized block out of an autonomous network. Still thinking about the use case though.

>>6571 A CA is a closed system. Figuring out how to decrease its entropy would be an incalculably massive revolution in physics, because that would mean it'd be possible to decrease entropy without increasing the entropy of something else by a greater amount, thus proving the Second Law of Thermodynamics wrong, or at least incomplete. The Second Law of Thermodynamics was considered by Einstein to be the absolutely most inviolable law of physics that would never be superseded or disproven, even above his own theory of relativity.

>>6573 Actually Maxwell’s Demon suggests otherwise. The only thing that stands in the way of MD is a finite memory as proven by Charles Bennett from IBM, a century after the initial postulation. So now consider this: what if instead of one finite memory source we distribute the memory load between an ever growing amount of automata?

>>6576 >Actually Maxwell’s Demon suggests otherwise. You mean it suggests the Second Law, or that there are circumstances in which the Second Law can be overridden? I'm naturally highly skeptical of the latter.

>>6582 Actually, Maxwell was the contemporary of Clausius who made the statement that became the Second Law of Thermodynamics. Maxwell was a devout Christian so the fact that life was deterministic troubled him deeply. He wanted to reinstate the firm belief of choice being the driving factor in our lives. That is the reason why he devised the Demon that is known with his name. If you take a look at the mechanisms of this Demon, it is particularly simple. There is a finite Demon, which is all-seeing so it can distinguish between hot and cold molecules. It sits on top of a box of gas molecules, and with no effort allows hot molecules to pass into a container by lifting a lid, trapping cold molecules inside. This thought experiment was very powerful and it took more than 100 years, and the Information Entropy of Claude E. Shannon to match the rise in the entropy with the finiteness of Demon's memory: As the Demon keeps track of a hot molecule and a cold molecule, it stores this information in its memory. After a while, the finite memory of the Demon overflows, so it has to wipe some amount of memory. This is the reason of the entropy increase. What I'm suggesting is this: if these molecules are AI, or humans with embedded memory of their own, and are capable of sorting themselves in their respective chambers, what happens then?

>>6588 You can't get infinite memory though. Just a large amount of memory isn't enough. It has to be literally infinite to lower the entropy of a closed system.

>>6589 You don’t technically need an infinite memory. Just one that keeps growing faster than write and/or count speed.

>>6594 Okay, so let's suppose you use one of these memory cores to lower the entropy of a closed system. Is it just a one-time thing and the memory core can flush its memory and let the system proceed naturally from that point, or does the memory core have to keep a record of that being done? I've actually read some theories about spontaneous entropy reduction which can occur by sheer luck of the draw with regards to the movement of atoms and molecules, but never any way to induce it through a machine of some sort. Those theories rely on painting the 2nd Law as a probabilistic phenomenon, meaning entropy will increase on average, but unlike in classical physics, there is a possibility, however slight, of total entropy going down instead of up.

>>6596 >Is it just a one-time thing and the memory core can flush its memory and let the system proceed naturally from that point, or does the memory core have to keep a record of that being done? Both. The entire system is designed to bypass the limitations of computation by clever tricks. Assume a daily system of any kind. This system's only known setting to us is the 24 hour period, because it's "daily". If the system goes idle after a certain hour, like people going to sleep, the overall entropy of the closed system will be drawn out. The memory won't be flushed out in the common sense, but will leave with the carriers of that memoryspace as they exit the system. Memorylessness is a very important property of such a system and it opens up the pathways to time-reversibility, which is a subject explored within Markov chains framework. In order to optimize the system you could task memory flushes which would have an immediate entropy penalty but could reduce the entropy on the longer term. The hypothetical Maxwell's tunnel, which is a play upon the quantum tunneling, suggests a pump of molecules to decrease the overall entropy of the system, and this has been experimentally verified by Finnish researchers: http://physicsworld.com/cws/article/news/2016/jan/11/autonomous-maxwells-demon-displays-chilling-power This setup above is said to greatly reduce energy losses of microchips. Linear mechanical thinking, which the algorithms such as the Turing machine is built upon, are all tied to the Axiom of Causality. However if you consider a feedback loop, the cause may be the effect itself. Such a dynamical shift between the cause and the effect would lead to changes in mathematical foundations as we know it (in order to arithmetically count do we need the information of a number priorly?), which would lead to Super-Turing Computation. Beyond that, anything's possible.

>>6597 >However if you consider a feedback loop, the cause may be the effect itself. Such a dynamical shift between the cause and the effect would lead to changes in mathematical foundations as we know it This is all over my head. That's why I read it in Doc Brown's voice, because all I'm getting from it is that when this baby hits 88 iterations per second, we're gonna see some serious soykaf.

>>6561 >Is there a link between all of them, then? Idk, but the sierpinski triangle comes up all the time in mathematical chaos. I think it has to do with the cantor set, which contains all points on the unit interval with orbits that remain bounded under the quadratic map (most of which are chaotic orbits): >Q_c(x_(n+1)) = x_n + c It has a bunch of weird properties, like being completely discontinuous at every point, and having a "length" of zero. The attached Devaney book is a really good intro to this stuff. Easy to understand with lots of pictures and context. >>I'd imagine you can do anything with CAs that you can do with matrices. >This deserves an answer for curious readers. Sure, I'll do my best. Consider the (finite) 1D case. The initial state is a binary vector x_0 of length n, with elements corresponding to live, 1, or dead, 0, cells. Think of a cell's neighborhood like a bit mask. We'll call the neighborhood of cell i "w(i)". For example, let n=9. Here's an initial state: > x_0 = [0 0 0 1 1 0 0 1 0] and here's the neighborhood of cell 5: > w(5) = [0 0 0 1 1 1 0 0 0] If you want to retrieve the bits of x that are relevant to cell 5's next evolution step, you can simply do the following: > w(5) & x_0 = [0 0 0 1 1 0 0 0 0] Now check this out: > W = [w(1); w(2); ... ; w(9)] i.e. > W = [ >[1 1 0 0 0 0 0 0 1]; >[1 1 1 0 0 0 0 0 0]; >[0 1 1 1 0 0 0 0 0]; > . . . >[1 0 0 0 0 0 0 1 1]; >] We define a kind of matrix-vector product * using the & operator for multiplication, and a really weird "sum" function based on the evolution rule. Formulating this sum explicitly would be a pain in the ass, so I'm just going to tell you that sum(v) returns 1 if the configuration of v produces a living cell, and 0 if it produces a dead cell. Thus, we have: >W*x = [sum(w(1)&x); sum(w(2)&x); ... ; sum(w(9)&x)] Putting this all together, we have a model for the CA in question: >x_(t+1) = W*x_t ... for time t Why would you do this? The motivation isn't obvious if you aren't familiar with abstract algebra, but looking at properties of the multiplication and sum functions can tell you things about the whole model. You'd want to look for linearity, isomorphisms, etc.

>>6606 soykaf, i just realized that's supposed to be >Q_c(x_(n+1)) = x_n^2 + c

>>6605 I laughed IRL, thanks Lainon.

Next up: Implementing this >>6533 into this >>4825

I've been following this thread for months and don't have a clue about the technical side of what you're doing but does someone have an application working already for this crazy math?

>>6657 There are several applications in some of the earlier posts in this thread, such as Golly. You can also check out LifeWiki for more. http://www.conwaylife.com/wiki/Main_Page

>>6639 http://www.cr31.co.uk/stagecast/trains/index.html

>>6615 I'm soykaf at math so I might be wrong, but isn't that the logistic map, not the Cantor set?

>>6700 You're kind of right. It is the Cantor set, but the cantor set is closely related to the logistic map. That's the point I was getting at.