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.

>>17 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...

>>19 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.

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

>>21 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)

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

>>18 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 >>21 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.

>>19 >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.

>>25 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.

>>26 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.

>>28 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.

>>30 First tell us about CA (plz)

>>30 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.

>>31 >>32 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

>>34 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?

>>36 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.

>>36 Took me about a week of hacking to get it to where it is right now. >>37 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.

>>38 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?

>>39 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).

>>40 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.

>>41 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?

>>42 >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.

>>43 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.

>>44 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?

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

>>44 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.

>>29 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.

>>48 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.

>>49 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.

>>51 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'} >>30 i'm down. lets come up with something cool for the lainzine.

>>49 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. >>50 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.

>>48 I like the way you think. I'll probably keep this current project purely grid-based, additionally, >>50 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!

>>50 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

>>57 >>58 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. >>55 Also this.

>>58 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!

>>60 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 >>50, 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.

>>64 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.

>>65 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.

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

>>66 >>67 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.

>>68 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])

>>69 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

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

>>71 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

>>69 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

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

>>75 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

>>76 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.

>>53 >>55 >>63 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). >>68 >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?

>>79 >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 >>78. >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.

>>78 Model ergodicity.

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

>>83 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, >>69, 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.

>>84 Also probability vectors are a good idea.

>>84 >>85 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?

>>86 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.

>>86 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.

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

>>58 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. >>87 >>88 >>89 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.

>>90 >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.

>>91 >>90 I didn't know if CA was invertible. So I went and did this >>64 Experimenting doesn't hurt.

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

>>90 >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.

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

>>94 As >>22 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.

>>96 >>95

>>96 >As >>22 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 >>85 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 >>82

>>98 >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.

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

>>100 >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.

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

>>81 I think a lot of people would like that. >>98 >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.

>>103 >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.

>>104 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. >>105 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.

>>105 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 >>21 could be useful here.

>>107 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.

>>108 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.

>>108 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? >>109 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.

>>110 >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

>>110 >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. >>111 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.

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

>>113 >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 >>61. 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

>>116 >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. >>50 >>63 >>79 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.

>>116 >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.

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

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

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

>>117 >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

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

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

>>22 >>95 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

>>129 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 >>134 was for >>106

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

>>134 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."

>>137 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.

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

>>137 >>138 For a definition of non-deterministic chaos, see the pdf in >>104

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/

>>142 Looks really cool.

>>143 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

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

>>145 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.

>>146 >>146 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 >>148 and >>149 to have their questions go unanswered, and I want to hear from the guy doing ergodic CA research.

>>150 > 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. >>151 Well that's unfortunate. Hopefully you can get back on your feet soon. I did some research for >>148, 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?

>>152 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

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

>>154 Definitely do it.

>>155 >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.

>>159 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.

>>160 >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.

>>161 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. >>137 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.

>>160 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.

>>164 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.

>>165 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.

>>166 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.

>>167 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.

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

>>164 >>165 >>166 >>167 >>168 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.

>>170 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.

>>171 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 >>160 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.

>>173 >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.

>>174 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. >>116 >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. >>128 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.

>>173 >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.

>>176 >>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.

>>177 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. >>175 >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.

>>179 Happy anniversary Lain!

>>180 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.

>>178 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

>>151 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.

>>183 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?

>>184 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 >>183 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.

>>185 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?

>>152 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.

>>187 It's been a while since >>152 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.

>>84 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 >>82 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. >>173 >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? >>122 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.

>>186 I was introduced to CA in a complexity course and I promptly went on and wrote this manipulation of GoL: >>64 >>3175 >>69 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.

>>190 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.

>>190 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.

>>192 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?

>>193 >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.

>>194 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?

>>195 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.

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

>>197 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.

>>198 >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.

>>199 >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.

>>189 >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.

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

>>200 I laughed IRL, thanks Lainon.

Next up: Implementing this >>183 into this >>134

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?

>>205 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

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

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

>>208 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.

>>206 Your link made me discover this: https://www.youtube.com/watch?v=8unMqSp0bFY Absolutely amazing.

>>201 Check these out

>>64 >>67 gonna work these with Rule 184 tonight

>>212 Should be interesting to see some more of that type of CA work. What made you pick Rule 184?

>>212 Find a rule that creates chaotic behavior, preferably a "if amount between a and b it survives" like conway's game of life

>>214 Try it with Rule 30 and Rule 90 if you want chaotic behavior in 1D, but for stuff like this, we also need some go-to 2D and 3D rules that do the same thing. Anyone know anything about that?

>>213 Rule 184 is a model for traffic flow, which solves the majority problem. I want it to solve the synchronization between cells. >>214 >>215 I’ll do the exact opposite. If cell is 1 then what are the status of its neighbors? That’s the code behind the example I provided.

I tried to recreate the card game described in >>183 Does this work as a protocol?

>>217 >mp3 soykaf, had a brain freeze. Here you go

Life has been difficult lately, but I'm still trying to work on the recursive CA when and where I can. Since I currently have minimal time to actually sit down and try to code something, I decided to attempt to get a better concept of how a recursively done Rule 90 works theoretically, since the semi-iterative way I was going about it is too convoluted for my taste instead of being the much, much simpler approach I was hoping for. There are many iterative versions of Rule 90 with similar levels of complexity, so if I wanted to deal with that, I'd just go with one of them. Asking in here rather than in the recursion thread would be better for this because this is about how a recursive CA works on a fundamental level rather than how to code one. My current idea is to make use of Rule 90's properties of additivity and generating nothing but superpositions of Sierpinski triangles, and create a base "tile" to add together as a recursive structure to generate the CA, but the problem with that is fitting it within the concept of an array, since you need to modify and write the values one at a time, and one iteration is one line long, whereas a tile could be multiple lines long. The end result I'm going for is something like a 3-step process: 1) Scan input data for 1s. 2) Upon encountering a 1, generate a Sierpinski triangle. 3) Add together the results generated this way to get the complete CA. I feel like there's some crucial concept I'm missing, though, one which may upend this idea entirely and replace it with something else. Maybe I could just have the program generate a 2D Sierpinski triangle array every time it encounters a 1 in the input data and add all the arrays together, but that could involve a lot of arrays. I'd rather keep the number of arrays as low as possible and their size as small as possible. I actually have a (possibly groundless) hunch that the missing concept which would allow a truly recursive CA may be bitwise operation. All current CAs I'm aware of, no matter what category they fall into, use mathematical functions to create their next iteration. Using logic gates in place of mathematical operators is often done to save computing resources on platforms strapped for processing power because it's more computationally efficient than actually doing math, but it's not often technically needed to make the program work. This may be different, though. Try as I might, bang my head against the wall as much as I want, I can't come up with a way to use any sort of mathematical operation to escape the iterative paradigm of CAs. But what if I didn't have to? What if I could have a logic gate decide a given value or set of values for me? And if I used logic gates in place of mathematical operations, it would be easy to just call that same routine over and over again as a recursive function. Depending on what logic gates you choose, you may be able to recreate many other CAs besides Rule 90 this way. Have I just gone off the deep end here or is there something to this? Someone who uses bitwise operation a lot, please respond to this.

>>219 To add to this, both Wikipedia and MathWorld mention that Rule 90 can be constructed with the XOR logic gate. However, that by itself doesn't do much to suggest a method of implementing this into a recursive program...at least not to me, because my bitwise-fu is scrub-tier.

>>219 >Depending on what logic gates you choose, you may be able to recreate many other CAs besides Rule 90 this way. I've thought about this some more, and I had the idea that you may be able to use this CA formulation to prove computational universality. If logic gates can construct any CA recursively, all you'd have to do is prove that a certain CA can be made of a NAND gate arrangement equivalent to a CPU and you'd have proven universality. That could be much easier than, say, Matthew Cook's cyclic tag proof of the universality of Rule 110. I'm probably jumping the gun here, though. I need to finish the recursive Rule 90 program before trying that, but I can't help wondering how many results you could prove this way.

>>221 There's some stuff in A New Kind of Science about Boolean logic, including Wolfram's axiom, and about recursion as well. Unfortunately, it doesn't have too much tying these disparate concepts together with CAs, which is odd because NKS is probably the most well-known book about CAs.

possible important ergodic CA stuff here >>116 >An ergodic CA is essentially a reversible CA that requires many potential states to be added to it Following off of the idea of using logic gates to build CAs, you may be able to use this multidirectional reversibility property of ergodic CAs to build them with reversible logic gates, as well as quantum logic gates which are inherently reversible, and use this to prove results about them, and about reversibility in CAs overall. Quantum mechanics and ergodicity are closely related because in theory, the possibility of an object quantum tunnelling to any location exists. I decided to search for anything having to do with logic gates and CAs in an effort to get recursive CAs to work, and quite a few interesting results came up, but most of them were about using quantum dot CAs to simulate logic gates, not the other way around. Still, if you can do it one way, you can generally do it the other way. I found this video about using the Game of Life to simulate AND, OR and NOT gates: https://www.youtube.com/watch?v=vGWGeund3eA And here's a paper about QDCAs simulating MAJORITY, OR, NOT, and INVERTER gates. https://nanohub.org/resources/1005 There's a considerable catalog of material on this subject, and I don't have time to go through all of it in the detail it deserves right now. I'm posting a bit of it because it may be relevant to what others here are doing, and maybe if we all team up, we can tackle it.

>>223 >>116 Good stuff.

>>223 First read this >>134 And then visit this >>207

>>225 The train switches are basically a series of logic gates. What I want to know is if it's generally an easier, more intuitive approach to generate CAs directly from logic gates instead of starting with a formula and translating it into logic gates. I think the study of logic gates will make up most of the rest of this thread, possibly the next one and maybe eventually most of the field of CA research. To me, it seems like they're the answer to half the questions in this thread and many more. There are a couple of things I'd like to see here. The first is specific to CAs. Whereas there are only 7 logic gates in classical computing, quantum computing has an uncountable number of logic gates. This property could be used to generate literally innumerable varieties of CAs, but that's not certain. The elementary CAs have only a limited number of rules, and many of those are equivalent to each other. Proving some things about quantum logic gates could allow us to essentially put limits on what types of CAs are available. We could also try logic gates from other forms of computing like biocomputers, but I doubt you'll get anything from it that you wouldn't get from quantum logic gates. The second is regarding >>4825's claim that the ergodic CA will be Turing universal. This might be employed in conjunction with existing quantum mechanical theories to prove that the universe is mathematically equivalent to a computer. As far as I know, no quantum CA has ever been proven to have Turing universality. I hypothesize that even if the ergodic CA isn't a "proper" quantum CA, it could be reformulated as a quantum CA by using quantum logic gates and then used to prove the above conjecture. Needless to say, that would break open all sorts of things.

>>45 I just went to the genetic algorithms thread out of idle curiosity and found this post, which contains a paper about using CAs to model protein folding. I'm surprised no one's talked about it considering how long ago it was posted.

>>226 How about this for quantum computing? http://www.het.brown.edu/people/andre/qlambda/index.html

>>228 This link doesn't contain any references to CAs. How would you go about making a CA out of these gates?

>>229 I plan on inserting them into the Firing Squad Automata.

I saw this essay somewhere here (maybe in another thread), but the quality was terrible since it was a quick scan by somebody, lots of skewing and scanner artifacts. I fixed the skewing and cleaned it up some

>>231 That's quite neat, thanks.

>>69 I have upgraded this code. The code works to create pre-synchronization blocks. It works like this: 1) Search in upper and lower Moore neighborhoods 2) If there is only one in either up or down, align it to the middle This has revealed interesting results for different probability distributions. You can see them in the attached gif. You need PyCx to run the simulator. import matplotlib matplotlib.use('TkAgg') from pylab import * import numpy as np L = 100 p = .3 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 number_of_upper_neighbors(x,y): upper_count = 0 for dx in range(-1, 2): upper_count += c[(x+dx)%L, (y+1)%L] print upper_count return upper_count def number_of_lower_neighbors(x,y): lower_count = 0 for dx in range(-1, 2): lower_count += c[(x+dx)%L, (y-1)%L] print lower_count return lower_count def step(): global c, nc for x in xrange(L): for y in xrange(L): for w in range(-1, 2): if c[x,y] == 0: nc[x,y] = 0 elif c[x,y] == 1: m = number_of_upper_neighbors(x,y) if m == 1: nc[x,y] = 1 nc[x,(y+1)%L] = 1 n = number_of_lower_neighbors(x,y) if n == 1: nc[x,y] = 1 nc[x,(y-1)%L] = 1 c, nc = nc, c import pycxsimulator pycxsimulator.GUI(title='My Simulator',interval=0, parameterSetters = []).start(func=[init,draw,step])

>>233 Can you tell us more about what the results mean? It seems that the cells gradually die off for low values of P but continue to evolve for higher values.

>>234 To make matters more understandable, I have taken 5 steps of each probability distribution, p = 0.1, 0.3 and 0.5. The cells actually do not die off, but it appears that way in the lower probabilty distributions, because the alive points are so sparse, when they get into a block so much empty space becomes visible. The code runs this way: for any alive cell, it scans the upper and lower neighborhoods, and if it sees one neighborhood with only 1 alive cell, this cell moves to the middle of that neighborhood. With this one code, there is instant compression. For higher probability distributions though, and this is more apparent for p = 0.5, the steps start to oscillate, going back and forth. This is because, one cell calls its neighbor to its middle, while another calls the same cell to its middle neighborhood. Also for some reason, after each screenshot export, the borders get shrunken down, might be related to the periodic boundary conditions.

>>234 >>235 There are some evolutions because the connectivity increases, which allow for a higher neighborhood search, but there are oscillations as well.

>>64 >cell determining the states of its neighbors This seems like the opposite of: >for any alive cell, it scans the upper and lower neighborhoods, and if it sees one neighborhood with only 1 alive cell, this cell moves to the middle of that neighborhood How do you reconcile these two things? >>235 >>236 >compression So what, this is a new compression algorithm that compresses CAs? >There are some evolutions because the connectivity increases, which allow for a higher neighborhood search, but there are oscillations as well. Sounds a lot like the Game of Life, and that's what you said you modified it from, but you've managed to get it to do some new things.

>>237 >How do you reconcile these two things? Initially what I had in mind was to have a cell determine the states of its neighbors, which is the opposite of how the CA usually work. To do that I have introduced a ‘-1’ state which swaps the dead cells and the live cells, tricking the system that it is running like a normal CA. This code is similar in a sense that it requires a reference live cell, c[x,y], to determine the position of its neighbors if they meet certain criteria. Other than that I took away the ‘-1’ and limited the Moore neighborhood to its upper and lower boundaries only. >So what, this is a new compression algorithm that compresses CAs? For the lack of a better word. Pulling cells together is the first step towards creating synchronization blocks. >Sounds a lot like the Game of Life, and that's what you said you modified it from, but you've managed to get it to do some new things. The GoL is unique that it could lead to completely unpredictable behavior from a very simple initial setting, and this uniqueness is the product of the complexity generated from GoL’s interdependencies. What I’m trying to do is to manage these interdependencies from a reference point, the live cell, or the General in the Firing Squad Synchronization problem.

>>238 This is some pretty heavy stuff. I'm struggling to grasp a lot of it. >Initially what I had in mind was to have a cell determine the states of its neighbors, which is the opposite of how the CA usually work. To do that I have introduced a ‘-1’ state which swaps the dead cells and the live cells, tricking the system that it is running like a normal CA. This code is similar in a sense that it requires a reference live cell, c[x,y], to determine the position of its neighbors if they meet certain criteria. Other than that I took away the ‘-1’ and limited the Moore neighborhood to its upper and lower boundaries only. So it's two different things, then. What does changing it to how it is now accomplish? >For the lack of a better word. Pulling cells together is the first step towards creating synchronization blocks. Is it possible to do this with other CAs? It'd be incredible if you could use this "compression" technique to simplify the implementation of CAs. >What I’m trying to do is to manage these interdependencies from a reference point, the live cell, or the General in the Firing Squad Synchronization problem. I don't know this problem. What will you be able to do if you get this to work?

>>233 This is pretty clever.. I feel like you have to be very careful about not making your automata dependent on the order you execute the cells in. Seems like you did that but I have to think about it more.

>>239 >So it's two different things, then. What does changing it to how it is now accomplish? The first one, although not functioning as intended, builds live cells from the interactions of two live cells. The second one organizes live cells to form blocks with one another. >Is it possible to do this with other CAs? It'd be incredible if you could use this "compression" technique to simplify the implementation of CAs. I have no idea if there is any precedent to this. Although I did mention my methods are very personal and untried. >I don't know this problem. What will you be able to do if you get this to work? You can take a look at the Slashdot article on the problem: https://ask.slashdot.org/story/02/12/12/2025230/solving-feynmans-unsolved-puzzle >Problem 3.4: Before turning to Turing machines, I will introduce you to a nice FSM problem that you might like to think about. It is called the 'Firing Squad' problem. We have an arbitrarily long line of identical finite state machines that I call 'soldiers'. Let us say there are N of them. At one end of the line is a 'general', another FSM. Here is what happens. The general shouts 'Fire'. The puzzle is to get all of the soldiers to fire simultaneously, in the shortest possible time, subject to the following constraints: firstly, time goes in units; secondly, the state of each FSM at time T+1 can only depend on the state of its next-door neighbors at time T; thirdly, the method you come up with must be independent of N, the number of soldiers. At the beginning, each FSM is quiescent. Then the general spits out a pulse, 'fire', and this acts as an input for the soldier immediately next to him. This soldier reacts as in some way, enters a new state, and this in turn affects the soldier next to him and so on down the line. All the soldiers interact in some way, yack yack yack, and at some point they become synchronized and spit out a pulse representing their 'firing'. (The general, incidentally, does nothing on his own initiative after starting things off.) >There are different ways of doing this, and the time between the general issuing his order and the soldiers firing is usually found to be between 3N and 8N. It is possible to prove that the soldiers cannot fire earlier than T=2N-2 since there would not be enough time for all the required information to move around. Somebody has actually found a solution with this minimum time. That is very difficult though, and you should not be so ambitious. It is a nice problem, however, and I often spend time on airplanes trying to figure it out. I haven't cracked it yet." Basically I'm assigning each live cell a General status to synchronize their neighborhood. >>240 >I feel like you have to be very careful about not making your automata dependent on the order you execute the cells in. In this case, the order turns in my favor. Due to the nature of the problem I'm trying to solve, I'd like my cells to be mobile in the right-to-left alignment. I haven't added in the mobility yet, but the neighborhoods I'm manipulating into blocks are the alignments orthogonal to my movement axis. Interesting note: if you check the gifs of the initial random distribution and the following blocks, I don't really move the neighbor bits into center, I add a live cell at there. This might seem like I have added extra cells, but visually it looks alright. I have modified the code to fist wipe the neighborhood to 0 and then add 1 to middle, which led to a lot of cells getting killed. This is interesting because I might need to check the math behind this.

>>241 I took a trip to Wikipedia to see if they had anything about this, since I know next to nothing about what you've done here. Some of the features of this CA sound similar to this: https://en.wikipedia.org/wiki/Mobile_automaton With your rule, the cell will be able to move around instead of just flip into a different state. But this isn't all it can do. >Pulling cells together is the first step towards creating synchronization blocks. This idea of creating blocks has been done, but I'm not sure if it's been done in this way before. The use of the word "block" may not be the same as it is in ergodic theory, but it may still have some relevance: https://en.wikipedia.org/wiki/Block_cellular_automaton In some ways, a block CA is similar to a movable CA: https://en.wikipedia.org/wiki/Movable_cellular_automaton This is an array of CAs that uses data from more than one CA to decide their evolution. This is somewhat similar to second-order CAs: https://en.wikipedia.org/wiki/Second-order_cellular_automaton Obviously, since it was based on Life, it has similarities to that as well: https://en.wikipedia.org/wiki/Life-like_cellular_automaton It seems like you've created a hybrid CA that combines features of several previously-known types of CAs. Notably, some of them (block CA and second-order CA) are listed as being automatically reversible: https://en.wikipedia.org/wiki/Reversible_cellular_automaton There's also an article on the firing squad: https://en.wikipedia.org/wiki/Firing_squad_synchronization_problem This article says that you can't solve the firing squad problem with a CA where the cells have 4 states or less, but I guess you're just taking a concept from it instead of trying to solve the problem. I'm intrigued by the potential for reversibility in this CA, since it's known that you can simulate any d-dimensional irreversible CA with a reversible CA of d+1 dimensions. I wonder what you could simulate by using this. If you aren't familiar with these types of CAs, you should take a look at them and see what they're like compared to yours.

>>242 Thanks for all those links. I had skimmed over them before, and now I've read them a bit more carefully. There are bits I can take to use but the problem is, most of the CA classes are built with an academic thought. The structure is emphasized, not the function. I am leaning on the latter. Think of my blocks like an amoeba. It is more or less formless, yet it has some structure to it and the cilia around it allows it to move towards directions. It is the topology that generates the movement, and the boundary interactions that maintain a direction. That's how it should work in my design. >This article says that you can't solve the firing squad problem with a CA where the cells have 4 states or less, but I guess you're just taking a concept from it instead of trying to solve the problem. I'm intrigued by the potential for reversibility in this CA, since it's known that you can simulate any d-dimensional irreversible CA with a reversible CA of d+1 dimensions. I wonder what you could simulate by using this. If you aren't familiar with these types of CAs, you should take a look at them and see what they're like compared to yours. Similar with what I've said above, the problem to the Firing Squad Synchronization is bound to topology. Now, this might be stretching the problem definition, but for the sake of argument, what if you could have a 2 dimensional firing squad instead of a straight line? As I tried to do in my code, now I can plant a general in the middle of a neighborhood I call a block, and facilitate an even faster communication through this General.

>>243 >Now, this might be stretching the problem definition, but for the sake of argument, what if you could have a 2 dimensional firing squad instead of a straight line? As I tried to do in my code, now I can plant a general in the middle of a neighborhood I call a block, and facilitate an even faster communication through this General. Seems like the block CA concept has some definite advantages. It's possible that using a block-based approach may be more efficient for any CA that can be turned into a block CA, but the article has this to say about it: >Any reversible cellular automaton may be simulated by a reversible block cellular automaton with a larger number of states; however, because of the undecidability of reversibility for non-block cellular automata, there is no computable bound on the radius of the regions in the non-block automaton that correspond to blocks in the simulation, and the translation from a non-block rule to a block rule is also not computable. I'm unclear on what this means. It also says this: >As Toffoli and Margolus write,[2] the block cellular automaton model does not introduce any additional power compared to a conventional cellular automaton that uses the same neighborhood structure at each time step: any block cellular automaton may be simulated on a conventional cellular automaton by using more states and a larger neighborhood. Even if the block formulation doesn't introduce any additional capabilities, it may still simplify the process of generating a CA, and that's worth exploring if it can be done.

>>244 I need to remind that my definition of a block has nothing to do with the block automata, which are 2x2.. cells in n dimention. The correct definition would be a cluster, but I want to expand this into synchronization blocks, so I don't want to stray away from the word 'block'. In any case, the blocks my code generate is not pre-defined and come in all sizes, regardless of neighborhood. >Even if the block formulation doesn't introduce any additional capabilities, it may still simplify the process of generating a CA, and that's worth exploring if it can be done. The 2x2 block automata is not different from 3x3 Moore neighborhood in essence. In contrast, consider a 'cluster', to avoid confusion. It is made up of 3 rows and 5 columns of cells, 2-1-2-1-1. The 1s in the 2nd and the 4th columns are sitting in the middle, acting as information carriers to their Moore neighborhoods.

>>245 What this sounds like to me is that the cells are still determining the states of their neighbors, just with a few changes to how that determination is made. >The 2x2 block automata is not different from 3x3 Moore neighborhood in essence. You mean the 2x2 block CA is still using the neighborhood to determine the states of individual cells and not the other way around. Maybe either the block CA should be renamed a cluster CA or the synchronization block should be renamed synchronization cluster. That'd prevent a lot of confusion.

>>246 The block CA article says they're also called partition CAs. The use of generals isn't the same thing as using blocks, as the same transition rules you'd see in a normal CA still apply, except that they're done with whole blocks instead of on an individual basis. So you'll have rules that say a 2x2 block will have all its cells in certain states if the 2x2 blocks surrounding it have their cells in a certain combination of states. However, there's nothing stopping you from using the two concepts together. You could have a block of generals giving orders to other blocks.

Interesting turn of events. When I introduced rightwards expansion and leftwards contraction into the code, (actually the automata cells are counted from right to left so it's the opposite) the compression breaks down in the lowest probability density p = 0.1, yet there is a high cohesion and linearity in the highest probability density p = 0.5. Surely there must be a middle ground where we can achieve ample compression and cluster cohesion. >>233 The following code includes the left-right alignment: import matplotlib matplotlib.use('TkAgg') from pylab import * import numpy as np L = 100 p = .1 numberOfStates = 2 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 number_of_upper_neighbors(x,y): upper_count = 0 for dx in range(-1, 2): upper_count += c[(x+dx)%L, (y+1)%L] #print upper_count return upper_count def number_of_lower_neighbors(x,y): lower_count = 0 for dx in range(-1, 2): lower_count += c[(x+dx)%L, (y-1)%L] #print lower_count return lower_count def number_of_right_neighbors(x,y): right_count = 0 for dy in range(-1, 2): right_count += c[(x+1)%L, (y+dy)%L] #print right_count return right_count def number_of_left_neighbors(x,y): left_count = 0 for dy in range(-1, 2): left_count += c[(x-1)%L, (y+dy)%L] #print left_count return left_count def step(): global c, nc for x in xrange(L): for y in xrange(L): for z in range(-1, 2): if c[x,y] == 0: nc[x,y] = 0 elif c[x,y] == 1: nc[x,y] = 1 m = number_of_upper_neighbors(x,y) if m == 1: nc[x,(y+1)%L] = 1 n = number_of_lower_neighbors(x,y) if n == 1: nc[x,(y-1)%L] = 1 k = number_of_right_neighbors(x,y) if k == 0 and (m == 1 or n == 1): nc[(x+1)%L,(y+z)%L] = 1 l = number_of_left_neighbors(x,y) if l == 1 and (m > 1 or n > 1): nc[(x-1)%L,(y+z)%L] = 0 c, nc = nc, c import pycxsimulator pycxsimulator.GUI(title='My Simulator',interval=0, parameterSetters = []).start(func=[init,draw,step])

>>248 >Surely there must be a middle ground where we can achieve ample compression and cluster cohesion. That p = 0.5 gif is remarkable. What is it lacking that some other value of p would have? It starts as a jumble of random cells and then clusters up into a much more orderly assembly. Isn't that exactly what you're looking for? And what do you think of the possibility of using a block of generals?

>>249 It’s not exactly what I’m looking for. The structure is driven from the density of probability distributions and not the interdependencies between cells. In other words, there are so many alive cells that they have to fall in order, because there is nowhere else to go. To accept this result is an easy cope out and defeats the purpose of creating an automata that both compresses random distributions and guides them into an interaction-driven order.

>>250 This makes sense. So what are you going to do that gives the result you got with p = 0.5 for all cases?

>>251 First things first: let's get rid of all the unwanted cells outside of the blocks. For that I've introduced a von Neumann neighborhood as a rule, which filters out cells within no block structure. After this, I'll start developing the interaction mechanism between blocks. import matplotlib matplotlib.use('TkAgg') from pylab import * import numpy as np L = 100 p = .5 numberOfStates = 2 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 number_of_upper_neighbors(x,y): upper_count = 0 for dx in range(-1, 2): upper_count += c[(x+dx)%L, (y+1)%L] #print upper_count return upper_count def number_of_lower_neighbors(x,y): lower_count = 0 for dx in range(-1, 2): lower_count += c[(x+dx)%L, (y-1)%L] #print lower_count return lower_count def number_of_right_neighbors(x,y): right_count = 0 for dy in range(-1, 2): right_count += c[(x+1)%L, (y+dy)%L] #print right_count return right_count def number_of_left_neighbors(x,y): left_count = 0 for dy in range(-1, 2): left_count += c[(x-1)%L, (y+dy)%L] #print left_count return left_count def number_of_Neumann_neighbors(x,y): Vertical_count = 0 Horizontal_count = 0 for dy in range(-1, 2): Vertical_count += c[x,(y+dy)%L] #print Vertical_count for dx in range(-1, 2): Horizontal_count += c[(x+dx)%L,y] #print Horizontal_count return Vertical_count + Horizontal_count - c[x,y] def step(): global c, nc for x in xrange(L): for y in xrange(L): for z in range(-1, 2): if c[x,y] == 0: nc[x,y] = 0 elif c[x,y] == 1: #nc[x,y] = 1 m = number_of_upper_neighbors(x,y) if m == 1: nc[x,(y+1)%L] = 1 n = number_of_lower_neighbors(x,y) if n == 1: nc[x,(y-1)%L] = 1 k = number_of_right_neighbors(x,y) if k == 0 and (m == 1 or n == 1): nc[(x+1)%L,(y+z)%L] = 1 l = number_of_left_neighbors(x,y) if l == 1 and (m > 1 or n > 1): nc[(x-1)%L,(y+z)%L] = 0 #yo dawg #i heard you liked neighborhoods #so i put a von Neumann neighborhood in your Moore neighborhood #so you can run rules while you run rules h = number_of_Neumann_neighbors(x,y) if h >= 2: nc[x,y] = 1 c, nc = nc, c import pycxsimulator pycxsimulator.GUI(title='My Simulator',interval=0, parameterSetters = []).start(func=[init,draw,step])

>>252 It may be easier to develop the interaction rule while working within the framework of the von Neumann neighborhood, but to be truly complete, it should eventually operate the same way with any configuration of cells. For instance, if someone were to try to use this to model a physical process, they may not be able to just exclude certain cells and still have the model obey the laws of physics.

>>253 But I digress. If you'd take a look at how the rules I've implemented so far are situated in a neighborhood, you'll see that I have not stepped a foot outside of the Moore neighborhood configuration. In the end, von Neumann neighborhood is a subset of the Moore neighborhood in terms of its covered cells.

>>254 I guess so. I don't have any experience with this type of CA. I don't even know if this fits into what you were doing with an ergodic CA, or if it's a different new type of CA which happens to have characteristics you want to use for that. If you think you can make it work the same with a von Neumann neighborhood as it would with other neighborhoods, you're welcome to it, since you'd know better how to do this than I would.

>>255 I’ve figured (at least I hope I did) how to implement the Ergodic CA but for that I need to work out the interactions and get some motion going. But even though I may sound so sure of myself, my theory is mostly go with whatever works.

>>256 There are cases where different types of CAs overlap. Maybe this is both an ergodic CA and something else, with the possibility of having independent versions of both. At any rate, this is exciting stuff. The thread needs this kind of material. I'm anxious to see how far these ideas can be taken.

>>257 Spoiler alert

>>258 >This suggests that stochastic coupling could also be able to synchronize large populations of CA. A detailed account of these results will be given in a forthcoming work. So what happens then? This paper was published in 1998, so the followup should be available.

>>259 Didn't find anything tangible.

>>260 Not much of a spoiler, then. Still, the idea of coupled CAs hasn't been explored yet in this thread. Maybe someone here can finish what they started.

We've got just over 50 posts left in here before the limit. It's time to start thinking about packaging all the resources in here into an easily manageable format to start off the next thread.

>>261 >Not much of a spoiler, then You sure?

>>263 So now it's clustering up for p = 0.3 as well. What'd you change? It looks less like clusters and more like lines though.

>>264 I’ve added the coupling evolution equation from >>258

>>265 The paper says there's a critical probability of about 0.2 above which both CAs are fully synchronized, so that makes sense. What I don't understand is how you came up with the connection between stochastically coupled CAs and cluster CAs.

>>266 I fetched the stochastic probability from one neighborhood and tied it up to the self-correlation equation (1-p)*p, which is actually the standard logistic function. import matplotlib matplotlib.use('TkAgg') from pylab import * import numpy as np L = 100 # size of space: LxL p = .5 # probability of initial alive cells # initializing randomly assigned states with probability p 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]) # visualizing the content of an array def draw(): cla() imshow(c) # count of upper neighbors of a live cell's Moore neighborhood def number_of_upper_neighbors(x, y): upper_count = 0 for dx in range(-1, 2): upper_count += c[(x + dx) % L, (y + 1) % L] # print upper_count return upper_count # count of lower neighbors of a live cell's Moore neighborhood def number_of_lower_neighbors(x, y): lower_count = 0 for dx in range(-1, 2): lower_count += c[(x + dx) % L, (y - 1) % L] # print lower_count return lower_count # count of right neighbors of a live cell's Moore neighborhood def number_of_right_neighbors(x, y): right_count = 0 for dy in range(-1, 2): right_count += c[(x + 1) % L, (y + dy) % L] # print right_count return right_count # count of left neighbors of a live cell's Moore neighborhood def number_of_left_neighbors(x, y): left_count = 0 for dy in range(-1, 2): left_count += c[(x - 1) % L, (y + dy) % L] # print left_count return left_count # count of von Neumann neighbors of a live cell def number_of_Neumann_neighbors(x, y): Vertical_count = 0 Horizontal_count = 0 for dy in range(-1, 2): Vertical_count += c[x, (y + dy) % L] # print Vertical_count for dx in range(-1, 2): Horizontal_count += c[(x + dx) % L, y] # print Horizontal_count return Vertical_count + Horizontal_count - c[x, y] # count of Moore neighbors of an alive cell def number_of_Moore_neighbors(x, y): Moore_count = 0 for dx in range(-1, 2): for dy in range(-1, 2): Moore_count += c[(x + dx) % L, (y + dy) % L] # print Moore_count return Moore_count - c[x, y] def step(): global c, nc for x in xrange(L): for y in xrange(L): for z in range(-1, 2): if c[x, y] == 0: nc[x, y] = 0 elif c[x, y] == 1: #nc[x,y] = 1 # block generation from randomly distributed points m = number_of_upper_neighbors(x, y) if m == 1: nc[x, (y + 1) % L] = 1 n = number_of_lower_neighbors(x, y) if n == 1: nc[x, (y - 1) % L] = 1 k = number_of_right_neighbors(x, y) if k == 0 and (m <= 1 or n <= 1): nc[(x + 1) % L, (y + z) % L] = 1 l = number_of_left_neighbors(x, y) if l == 1 and (m > 1 or n > 1): nc[(x - 1) % L, (y + z) % L] = 0 h = number_of_Neumann_neighbors(x, y) g = number_of_live_neighbors(x, y) if h >= 1: nc[x, y] = 1 if g <= 6 else 0 if g / 8 >= (1 - p) * p: # stochastically coupled CA = cluster CA nc[(x + 1) % L, y] = 1 else: nc[(x - 1) % L, y] = 1 c, nc = nc, c import pycxsimulator pycxsimulator.GUI(title='My Simulator', interval=0, parameterSetters=[]).start(func=[init, draw, step])

>>267 ERRATA This g = number_of_live_neighbors(x, y) should be g = number_of_Moore_neighbors(x, y)

>>267 >which is actually the standard logistic function. This is an extremely powerful result. Is there any way you can get it to act more cluster-like though?

>>269 I could but I am pleased with these results for now. I’ll look at it and see if I can work something.

>>270 I'm interested to see what would happen if more than two CAs were stochastically coupled. Also, one of the many uses for the logistic function is in neural networks, so to see it used this way presents new possibilities for that. I've never seen any other CA paper that used the logistic function for anything.

>>271 >I'm interested to see what would happen if more than two CAs were stochastically coupled Technically this should be possible. I'll try to see if I can get to coupled CAs to run inside one master CA. > one of the many uses for the logistic function is in neural networks You could say it's similar since the logistic function here also introduces nonlinearity in the CA. That's why the blocks are acting like lines now.

>>272 >nonlinearity making something act like a line We've officially hit peak irony. Beyond that, this is odd because the logistic function is a solution to perfectly ordinary, linear differential equations.

>>273 >linear Never mind this, I'm mistaken. It does solve some weirdly simple nonlinear differential equations though. I'm familiar with it in passing, but not to any great extent, so whatever I think I know about it is probably wrong.

There's probably a whole family of equations which will produce clustering behavior in a CA. My thought would be to try a soliton function, since it also provides exact solutions to nonlinear differential equations, as the logistic function does. Any function like that might work. You could try several variations of that and compare results. It's also worth asking if stochastic CAs and deterministic CAs can both generate clusters.

>>275 >My thought would be to try a soliton function, Ah, this makes a lot of sense. Will try and post results

Ok, I've added a majority condition so it's now pulsating within the lines. This is encouraging. import matplotlib matplotlib.use('TkAgg') from pylab import * import numpy as np L = 100 # size of space: LxL p = .1 # probability of initial alive cells # initializing randomly assigned states with probability p 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]) # visualizing the content of an array def draw(): cla() imshow(c) # count of upper neighbors of a live cell's Moore neighborhood def number_of_upper_neighbors(x, y): upper_count = 0 for dx in range(-1, 2): upper_count += c[(x + dx) % L, (y + 1) % L] # print upper_count return upper_count # count of lower neighbors of a live cell's Moore neighborhood def number_of_lower_neighbors(x, y): lower_count = 0 for dx in range(-1, 2): lower_count += c[(x + dx) % L, (y - 1) % L] # print lower_count return lower_count # count of right neighbors of a live cell's Moore neighborhood def number_of_right_neighbors(x, y): right_count = 0 for dy in range(-1, 2): right_count += c[(x + 1) % L, (y + dy) % L] # print right_count return right_count # count of left neighbors of a live cell's Moore neighborhood def number_of_left_neighbors(x, y): left_count = 0 for dy in range(-1, 2): left_count += c[(x - 1) % L, (y + dy) % L] # print left_count return left_count # count of von Neumann neighbors of a live cell def number_of_Neumann_neighbors(x, y): Vertical_count = 0 Horizontal_count = 0 for dy in range(-1, 2): Vertical_count += c[x, (y + dy) % L] # print Vertical_count for dx in range(-1, 2): Horizontal_count += c[(x + dx) % L, y] # print Horizontal_count return Vertical_count + Horizontal_count - c[x, y] # count of Moore neighbors of an alive cell def number_of_Moore_neighbors(x, y): Moore_count = 0 for dx in range(-1, 2): for dy in range(-1, 2): Moore_count += c[(x + dx) % L, (y + dy) % L] # print Moore_count return Moore_count - c[x, y] def step(): global c, nc for x in xrange(L): for y in xrange(L): for z in range(-1, 2): g = number_of_Moore_neighbors(x, y) if c[x, y] == 0: nc[x, y] = 0 if g < 6 else 1 elif c[x, y] == 1: nc[x,y] = 1 if g < 6 else 0 # block generation from randomly distributed points m = number_of_upper_neighbors(x, y) if m == 1: nc[x, (y + 1) % L] = 1 n = number_of_lower_neighbors(x, y) if n == 1: nc[x, (y - 1) % L] = 1 k = number_of_right_neighbors(x, y) if k == 0 and (m <= 1 or n <= 1): nc[(x + 1) % L, (y + z) % L] = 1 l = number_of_left_neighbors(x, y) if l == 1 and (m > 1 or n > 1): nc[(x - 1) % L, (y + z) % L] = 0 h = number_of_Neumann_neighbors(x, y) if h >= 1: nc[x, y] = 1 if g <= 6 else 0 if g / 8 >= (1 - p) * p: # stochastically coupled CA = cluster CA nc[(x + 1) % L, y] = 1 else: nc[(x - 1) % L, y] = 1 c, nc = nc, c import pycxsimulator pycxsimulator.GUI(title='My Simulator', interval=0, parameterSetters=[]).start(func=[init, draw, step])

>>277 This is a marked improvement. I wish I could say what it was missing. Before you added the logistic function it seemed to cluster just fine, but only for p = 0.5. You either need yet another condition, or you need to remove something. You mentioned rightward expansion, leftward contraction and von Neumann neighborhoods. What would happen if you removed one or more of those while leaving the logistic function and/or the majority condition in? Try all your ingredients in isolation and then all possible combinations of them.

>>179 >>262 These posts are like a synchronizing block of text, if there was such a thing. I wish we could get some more machine learning people in here to look at the process in >>277 and its associated posts. I'd like to hear their thoughts about Wolfram's claim described in >>177 that CAs aren't a good fit for neural networks. Also, the cluster CA's new pulsation feature captures attention because of this bit in >>177: >Since replicators can be emulated by oscillators, a CA that exhibits both self-replication and randomness will probably be Class 4 by default. I don't know if this thread has enough room left to go into all the details about how this cluster CA applies to machine learning, especially since the author has said it isn't finished yet. Maybe that'll have to happen in the second thread. It seems like this CA answers, or has the potential to answer, many questions posed in this thread so far, but it raises new questions of its own, and those questions are going to require various kinds of expertise to tackle.

>>278 >>279 Added some extra piece of code that takes the ratio of live cells to dead cells and visualized the latest pulsating CAs.

>>280 Actually I may be a bit off-base with the self-replication stuff, but I'm not sure. I conjecture that the cluster formation could be done in such a way that it meets the definition of self-replication. That would mean it has both replicators and oscillators at the same time.

>>281 Seeing as you can emulate one with the other, this would make it reducible to only one or the other, but attempting something with this may give new insights into how to make it act like you want in other cases. I don't know about that either, but I think we're all taking shots in the dark on this one.

I think this cluster CA could be relevant to my attempt at the recursive Rule 90. Things have calmed down somewhat, so I'm devoting a bit more time to it again, but I'm still at a loss for how to proceed. What I do know is that constructing it as a conventional CA isn't going to work. A CA will be recursive if each iteration of the CA depends on all previous iterations, meaning it would be an nth-order CA. This could get computationally troublesome very quickly if done conventionally, so I was looking for an alternative way of formulating it. I was considering having the cell decides the states of the next iteration's neighborhood, similar to the cluster. That would allow it to work as I thought about earlier, where the computer generates a Sierpinski triangle every time it encounters a 1 in the input. Is it feasible to do this in a 1D CA?

Now that we're coming close to the end of the thread and we need to prepare for the next one, we should examine the existing CA knowledge base. To start off the next thread, >>7706 has a great OP that other threads could learn from. It'd be more convenient for everyone if threads specific to a certain programming language or area of software development commonly had OPs structured like that. It has resources broken down into subject areas. Any of the things discussed in this thread, like automata-based code, machine learning algorithms or ergodicity, could have a subset of resources for it. This kind of organization is important because the CA stuff I've been able to find lying around on the internet seems directionless. Most of the existing CA literature not only isn't written as clearly or accessibly as it should be, it doesn't convey just how big the topic really is, and this is part of the reason CAs are a niche instead of a major area of scientific work. What do we have to do to solve this? Do we need more blog posts, or better-written Wiki articles? Stephen Wolfram has his blog, and I'm hard pressed to think of anything we could do to stir up interest in CAs that someone in his position couldn't, but there may be something. The amount of noobish questions in this thread may be annoying to people who have a high level of CA expertise, but it indicates that some interest has been generated, which is good. Remarkably, the noob questions don't appear to have gotten in the way of high-level discussion at all. The question to everyone here is what direction would you like to see CA research go? The next thread, and any future outreach regarding CAs, should be built around that.

>>284 Also, if anyone who hasn't been following this thread sees this, we should hear from them about what we could do to catch their interest. Here's a picture to grab attention. I thought about posting a waifu in a bikini, but that would regrettably be taken down for not being on topic. I think bikini-clad waifus are always on topic. However, there's a surprising amount of art and music being done with CAs, so we should showcase some of that as well. I found this picture by running a search for cellular automata art. The source is here: https://trustpete.deviantart.com/art/cellular-automata-pattern-31709413

>>285 I just had a mental image of thousands of 8-bit anime girls square dancing or performing some mass choreographed dance together on an isometric grid.

>>286 I think this is the logical conclusion of the episode of Evangelion where they danced the Angel to death. inb4 the next Rebuild of Eva movie is a 2-hour monologue about how depressed and dysfunctional the characters are set to anime girls dancing in psychedelic CA patterns. Here's some more art because the miniaturized picture of the last one doesn't look quite right when miniaturized. It looks better at full size. We need to post a lot of CA art in the next thread. The source for this piece is here: http://mariuswatz.com/mwatztumblrcom/cellular-automata-as-pattern-generator.html Also, here's an article about CAs that came up during my search. It was posted during the lifetime of this thread, and it's largely about how they didn't really cause the revolution in computer science that Wolfram was hoping for. https://hackaday.com/2017/11/01/beyond-conway-cellular-automata-from-all-walks-of-life/ This article also contains an example of a CA that's considered an implementation of a neural network. https://en.wikipedia.org/wiki/CoDi >>277 should take a look at this and see what it has in common with the cluster CA. Is it the same thing? This Wiki article even contains a link to the firing squad problem. I'd hate to think that it's just old territory being retreaded. It seems like a lot of effort was put into the cluster CA, so I hope it contains a new advancement that sets it apart from CoDi.

>>287 >the miniaturized picture of the last one doesn't look quite right when miniaturized. I must have repeatedly taken my repetition pills today. Anyway, here's a piece from Rudy Rucker that he calls his pride and joy, and here's the source: http://www.rudyrucker.com/oldhomepage/celdoc/rules.html That's all the art I have to post for now, but those are some of the best examples I've found. Hopefully an artist will read this thread and make more.

Red text for extra attention because anyone invested in the cluster CA needs to read this. I'm reading the CoDi article I posted in >>287 a bit more closely now, and it also says that CoDi can be implemented as a partitioned CA, and that it uses a von Neumann neighborhood. Since much of this thread has been spent discussing the possibility of an ergodic CA, and subsequently seeing a poster here create a neural network-like CA intended to be the first step in building up to one, this is what I hope happens. Based on the small amount of Wiki articles about it and the other stuff I've scoured the internet for, it looks like CoDi is, if not the only CA rule that qualifies as a neural network, then one of a very few such rules which are presently known, and the only one listed on Wikipedia. This may turn out to be a new class of CA, a subset of which may exhibit ergodic behavior. Cellular neural networks were discussed a while back in here, and this may overlap with them or not. Regardless, if it does turn out to be a full CA category, that would mean it's not necessarily a rehash of CoDi. It would just mean that CoDi was the first of its kind, or at least the first one to become notable, like the Game of Life. It would mean that there's a titanic undiscovered frontier out there for this type of CA, and that would be ideal. That's the direction I think will be the most fruitful for CA research, and it's the direction I think the next thread should go in. That may not be what everyone wants to focus on, but there's enough room here for many different paths.

>>277 The pulsation of this CA is similar to a spiking neural network, which CoDi models, but CoDi doesn't seem to be stochastic according to what I can find about it. That's a major difference from what you have here. If this legitimately is its own thing, you should give it a proper rule name to distinguish it from CoDi. I don't think we've seen enough stochasticity in CAs with a number of dimensions other than 2, so that's something to think about. But the really exciting thing is that people can take this cluster process and start applying it to all sorts of CA architectures of all dimensions, grid shapes and topologies, and that's without even fully building it into an ergodic CA. If that isn't enough to drum up interest in CAs, I don't know what would. CoDi has been around since 1998, but I haven't heard of anyone else doing anything like it. Is that because it's not useful, or because it's such a niche approach to both CAs and neural networks that few people have even heard of it? I guess we'll find out.

>>285 Fun trick - images of lain are always on topic

There's been some discussion here of how to encode a genetic program into a CA. Nothing substantial has come out of this yet due to the large amount of focus this thread has placed on ergodicity, but there's a new thread at >>8211 for evolutionary algorithms. That might be something good to develop more on in the next thread. The main difference in a genetic program versus CAs with replicating objects is that a conventional CA has cells die off, but it doesn't have them compete to see which one is more fit, as the poster who wanted to have cells eat each other talked about. Also, certain cell structures in a CA may replicate themselves, but they don't do it in exactly the same way that genes do. A genetic algorithm features candidate solutions pairing off and creating "offspring" which will then go on to repeat the cycle. To the best of my knowledge, no CA yet developed has had this feature. Some here have alluded to it, but nothing concrete has been seen so far.

Rambling about the philosophy of computing inbound. We're running out of posts for this kind of thing, especially since our ergodic CA developer hasn't yet addressed CoDi, but I'm trying to contribute something to how future threads about CAs will evolve. Thinking about technological development from a historical perspective, there always seems to be one or two key advancements that overwhelm everything else in the field and transform a certain technology from a curiosity to a major area of scientific research. For electronics, these advancements were the transistor and the integrated circuit. CA research has yet to produce something with that level of impact. CoDi-like CAs may meet these requirements, but it's too soon to tell. After all, it took decades to go from the invention of the integrated circuit to home computers, video game consoles and smartphones. If CAs can be thought of as arrangements of logic gates mimicking biological life, and a cluster CA is the same as a CA that couples other CAs together, then a cluster CA would be analogous to a modern CPU, which is a form of integrated circuit consisting of a collection of logic gates built out of numerous transistors all on a single silicon wafer. By comparison, Rule 110 and the Game of Life would be like punch card computers and vacuum tube computers. They're technically capable of running anything a modern computer can run, but punch card systems and vacuum tubes are impractical for modern computing tasks. Other CAs may be more like chemical computers, as with those simulating oscillating chemical reactions like the Belusov-Zhabotinsky reaction. They may also be like biological computers, or any other kind of computer.

The objects that each CA generates determine what tasks it's best for. I'd like to see a comparison of the different CAs which have been shown to be Turing universal to find the best practical application for them. This would allow a clearer view of how CAs work in terms of coding philosophy and computer science overall. We could do something similar with CAs in general. Wolfram used Rule 30 as an RNG, so that's one way in which you can incorporate a CA into otherwise conventionally written programs. That's thinking of CAs as functions. You can also think of CAs as complete programs, including programs as complex as an operating system, or even as computer hardware themselves. There are different categories of CA which correspond to each. This could be thought of as an extension to the paradigm of automata-based programming. Automata-based programming is generally done with a single finite state machine being used as a function. CA-based programming could be its own separate but related paradigm, since a CA is an array of finite state machines. We need a more detailed treatment of this. You could have a program consisting of a master CA being constantly fed input data from less powerful CAs. There's the question of how to set up a CA to deal with having to take new input, since CAs generally only accept input when they start running. Maybe the answer to this is using stochastic methods, since there's a probabilistic component at each time step, not just the data from the CA's initial configuration. You could easily set up a stochastic CA with that probabilistic component governed by user input. This seems like the only way to set up certain systems with a CA, such as remote-controlled robots. A deterministic CA, or a concatenation of them like the CA program described above, would be just fine for autonomous robots or any other system that doesn't require a human controller. But as soon as you want to change what the system is doing while it's in the middle of doing it, you need stochasticity. At least that's how I see it right now.

Here's a paper on ergodicity in CAs that I found while looking for stuff on 1D stochastic CAs, which says that the problem of ergodicity in a stochastic CA is undecidable: http://math.ut.ee/emsdk/intensiivkursused/TOOM-TARTU-3.pdf And here's one that says that no stochastic CA can ever be computationally universal, but also says that they have a nondeterministic CA which is universal: https://arxiv.org/abs/1304.7185 If these papers are true, it may be impossible to create a universal ergodic CA. However, the second paper also asks in its section on problems left open at the end if universal CA are the same for two different groups. I thought the whole point of universal CA is that they're the same for anything.

>>295 This means it's only universal for certain groups of CAs. Still, the claim that no stochastic CA can ever be computationally universal is very odd considering that other stochastic machines have been shown to be just that. I suppose you could ask the question of whether ergodicity adds anything over and above a standard stochastic CA that would allow it to be computationally universal, but according to these papers, it seems doubtful.

I don't know when our ergodic CA developer is going to show us some more results and read the papers and other stuff that I've (mostly accidentally) found pertaining to his project, but there's something that's been bothering me for a while that has to do with how stochasticity and entropy relate to this, so I might as well post about it. Anyone else who hasn't necessarily been following this thread but has some expertise in this matter is welcome to try to answer this. If we run up to the 300 limit, I'll go ahead and make the next thread. Here's another CA with artistic qualities for the perusal of any such newcomers, though this wasn't made for artistic purposes. This is a picture of a 2D cyclic cellular automaton which comes from here: http://kaytdek.trevorshp.com/projects/computer/neuralNetworks/gameOfLife2.htm >>296 First off, upon reading a bit further into this, stochastic computing systems haven't exactly been shown to be Turing universal. In fact it's impossible for them to give error-free Turing universal computation. The only way they can be Turing universal is if you're willing to accept a nonzero error rate in their computations. This error rate can be made arbitrarily small, but it can never be zero. Both the input and output of a stochastic computer system are technically uncomputable, as specified in this article: https://en.wikipedia.org/wiki/Hypercomputation This would suggest to many that stochasticity doesn't strictly exist. That brings up a whole host of questions, many of them having a more philosophical bent than this thread or this board were meant for. >>195 >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. My biggest issue here is that I share this sentiment. A universe without free will is one that I find intolerable. >>199 >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 This is an intriguing piece of experimental evidence. As you said, it may lead to super-Turing computation, but many researchers don't believe this exists. I'd also love to know how the undecidability of the question of ergodicity in a stochastic CA relates to the fact that the above-mentioned problem of whether we can get off of this completely deterministic train we're on is undecidable as well. As I said earlier, a stochastic system is needed if you want to actually choose what a system does at any point while that system is running, and a super-Turing computer could solve the halting problem in general, meaning it would have a great deal to tell us about ergodicity and stochasticity. I don't know nearly enough about how to apply this idea, though. The limitations of my own knowledge are painfully apparent to me here. I'm just not terribly enthused about a world where nobody has a choice in anything.

Here's some more CA art just because. It's one of the many 1D CA rules which can generate the Sierpinski sieve mapped onto a circle to create a pattern which looks much like a flower. Here's the source: https://curvatureofthemind.com/2012/10/15/circular-cellular-automata/

https://arxiv.org/pdf/1803.08600.pdf This is one of the things that came up when I ran a search for lower error rate bounds of stochastic computation, because I was curious if anyone had proven that its error rate was not in fact arbitrarily small. My thought was that the laws of quantum mechanics provide a lower bound for so many other things, so they may be at work here as well. Here's one of the things it has to say in its abstract: >Much less attention has been paid to proving lower error bounds for the SGD method. I haven't found any papers dedicated to proving this type of result about stochastic computation in general, only papers like this that do it only for specific stochastic algorithms. Note that this is a very recent paper, being only a couple months old. This is more of a general computer science and physics thing than a CA-specific thing, but I thought it might be worth a look. Pic related, it's a completely 100% on-topic image, do not delete.

>>19 There are good journals on automata. https://arxiv.org/list/cs.FL/recent (general automata) http://www.oldcitypublishing.com/journals/jca-home/ I'm not a domain expert, but I've heard that Wolfram is a bit of blowhard, and I don't see him coming up in recent literature a whole bunch. >and 'priciple of coputational equality' or how Wolfram called seems like more of philosophical question... Yeah, Wolfram likes to hear himself talk. > Beware however as this book is really only mediocre if that And there is zero justification for the size of the damn thing. It's a massive book and it really didn't have to be. > i'd recommend representing the connectivity of cells in the network as an adjacency matrix +1 matrix is the way to go

>>283 I've been thinking about this whenever I can and going over some of the earlier posts in the thread. Bitwise operation, neural networks implemented as vector multiplication, and cluster methods may all be essential to be able to use recursion to implement a CA rule that acts like Rule 90 despite using a dramatically different route. Unlike the ergodic CA, this one will be deterministic, but I'm intrigued by the possibility of adding a probabilistic component at a later point. I think if the recursive CA concept can be fully fleshed out, you'll then be able to take some of the work that's already been done on recursion in other contexts and use it to prove some long-elusive results about CAs. Going over the thread's earlier posts has also led me to believe that you may be able to use the idea to implement this: https://en.wikipedia.org/wiki/Recursive_neural_network Any machine learning experts care to comment?

>>301 https://arxiv.org/pdf/1703.02806 https://www.researchgate.net/post/what_is_the_realitionship_between_deep_learning_methods_and_reservoir_computing_if_any You would be correct. It appears someone has implemented such a system already. I am not an expert on such things but I have worked with spiking neural networks and a few projects like Open Worm and NeuroKernel. >>301 On the topic of matrix representation of neural networks... Finding and efficient matrix representation can be very time consuming. Moreover, matrix math is slow for large networks and is not easily optimizable. I cannot in earnest suggest a superior alternative, but perhaps one of the more technowizardly types around here could help in this matter. Maybe a language suggestion that allows a more expressive and flexible representation, or a new application for a common data structure...

>>302 This is a recurrent neural network. That's not the same as a recursive neural network. What the guy with the ergodic CA alpha version is doing above is similar to a spiking neural network. What do you think of that? >On the topic of matrix representation of neural networks... Finding and efficient matrix representation can be very time consuming. Moreover, matrix math is slow for large networks and is not easily optimizable. This would be a very compact network if it were to be implemented because it's based on a 1D CA.

>>303 After looking for some papers about this I found that others are already using the term "recursive CA" to mean a CA where each cell splits into several more with each iteration. This might make it hard to find information about implementing a recursive neural network as a CA, if there even is any.

>>303 >What the guy with the ergodic CA alpha version is doing above is similar to a spiking neural network. What do you think of that? It's not. He's solving the Dym equation of solitons.

Has computer science figured out how to encode arbitrary programs into CA's yet? I was curious about that a while back, but I could never find anybody working on it.

>>305 What about all the similarities it has to CoDi? I'd never heard of the Dym equation, so I went and looked it up. I have to say it's very interesting. The Wikipedia article says it obeys an infinite number of conservation laws. I didn't know that was possible. I suggested to the guy trying to make the ergodic CA that he should use a soliton in it. Guess we're going to have to talk about solitons in the next thread.

>>307 >What about all the similarities it has to CoDi? Mostly cosmetic, essential function is different.

I found a few examples of Rule 90 being done recursively on this Reddit thread. I normally hate Reddit but it sometimes ends up being useful. I've done numerous searches for recursive Rule 90 and other similar terms before, so I don't know why it didn't turn up sooner. https://www.reddit.com/r/dailyprogrammer/comments/3jz8tt/20150907_challenge_213_easy_cellular_automata/ Some of them are pretty close to what I came up with, meaning I can probably just tweak a few things in my existing code, but the code found in that thread still seems like a process that's truly iterative but that's just being written in recursive form. Maybe that's just my personal bias as to how a recursive function should look. This isn't supposed to be a major project or anything, so I should have had this done a long time ago, but this isn't my primary focus. It's a "whenever I have time" thing. Someone on the thread said that they tried recursion at first and couldn't figure it out either. Obviously my recursion skills need a lot of work, but for practical purposes I can probably stop bothering with this pretty soon and move on to something that can help this thread more.

>>309 This isn't 4chan, you don't have to justify the fact that you visit any of the unapproved websites.

>>310 Neither he has to omit if he felt like sharing his opinion.

We're down to the last few posts, so who wants to make the new thread?

I've decided to try to put together the OP of the next thread. I've been doing some more research and found some types of CAs I was previously unaware of, but I'd like some feedback on what the OP should focus on. The next thread will probably have a lot of stuff about AI, but there are also some things regarding Turing machines that I'd like to see discussed. I hope the guy making the ergodic CA didn't die. It's going to be the 1-year anniversary of the thread soon, so maybe that's a good time for the next one, assuming there's still interest in this.

>>313 The ergodic CA is on hold for now, because the CA has evolved into a Mercator projection of hyperbolic geometry, which is the activation function of deep learning. We are about to travel into the mind of an AI. Welcome to the 21st century of navigation, where the charts are your hyperbolic tangents and the north star is the Euclid's 5th postulate. Appreciate in advance if you could dump whatever resource you have on hyperbolic space and deep learning.

>>314 What in Lain's name is going on in your compiler, man... I guess I shouldn't be overly surprised at this because some of the CAs I've been looking at are built on abstract data structures and arcane topological spaces that give them considerable overlap with various forms of machine learning, nearly to the point of eliminating any distinction between the two subjects. Do you have any idea when you'll be able to give us more of an update? Can you explain how this evolution occurred? I've been gathering some stuff on deep learning and neural networks in general for the next thread, but hyperbolic space is beyond my expertise.

>>315 >expertise Now this is one hell of a loose way of describing what I can do with CAs.

>>315 The code is pretty much the same. The math behind it though, is expanding gloriously.