Cellular Automata (1983) [pdf] | Hacker News Reader

Cellular Automata (1983) [pdf]

content.wolfram.com

95 pointsjnakayama20 comments

Dave Ackley is using cellular automata for new computational architectures.

Its really cool stuff and you'll no doubt love it if you're keen on that stuff. He's also got a youtube channel under his name that is really worth checking out.

https://direct.mit.edu/isal/proceedings/isal2020/32/13/98482

Very interesting! Added to my list for algorithms to use in generative art seeds. Was already looking for computer architecture geometries to visualise and play around with.

Feel like a bit of an amateur with my previous landscape architecture art driven by a cellular automaton: https://hyperobjects.design/artwork/rule-30-city

https://www.youtube.com/user/DaveAckley

Only a few pages in. Had to try: https://gist.github.com/peheje/8076f619f6fbc1202954bc70720ef...

And here it is in apl :)

  (width iterations) ← 127 64 ⍝ perfect size for a nice sierpinski
  
  advance ← {2|-⌿¯1 1⊖⍤0 1⊢⍵} ⍝ on a torus
  x←width⍴0 ⋄ x[⌊width÷2] ← 1
  {⎕←' ⌹'[⍵]⋄advance ⍵}⍣iterations⊢x

And the random variant (not as pretty, but still has some nice triangles):

  {⎕←' ⌹'[⍵]⋄advance ⍵}⍣iterations ?width⍴2

First time seeing .nim code in the wild! Seems like a fun/ fast language to use.

2D cellular automata can also be used to recognize formal languages: Every character of a word forms an (initial) state. Finitely many additional non-character states are allowed. A word w is accepted iff the first cell indicates "yes" after |w|-1 iterations.

It is an open problem if there is a language that can be recognized after 2|w|-1 iterations, but not after |w|-1 iterations. Afaik, it is even unknown if there is any language in NP that cannot be recognized after |w|-1 steps (obviously P!=NP would imply this). I'm surprised how far math has come, but how little we know about computational complexity.

Completely agree! I had the same thought when looking into elementary cellular automata, they seem so inoccuous, but there are still so many open questions. There is even a prize for solving three particular ones: https://www.rule30prize.org/

I'm quite happy that I have absolutely no idea what kind of argument could possibly be employed to solve any of those problems. No danger of wasting an endless amount of time here.

Hey, this article got me interested in 1-d cellular automata at the time. Before that it was Von Neumann’s self replicating cellular automata and then Conway’s Life in the 70’s

Does Conway's name only appear twice in this article?

It does and with acknowledgement that Conway's life was then the best known example of 2D cellular automata. However, Conway's life CA was not the focus of the article hence limited references to it. There was an increasing of interest at the time of the article on self similarity, emergence, self organization and mapping of CAs with dynamical systems theory and different classes of CAs (focus of article) beyond the game of life. A number of researchers at the time were interested in using CAs as a means of simulating certain dynamical systems e.g. fluids and weather. However generally the early work of CA pioneers including Stanislaw Ulam, Kondrad Zuse, Art Burks et all was not as widely known as it is now and certainly John Conway's life along with the works of Edward Frenkin, Norman Magulis et al and articles such as these by Stephen Wolfram helped generated renewed interest in the field. Without articles like this one I am not sure we would have seen sufficient interest to publish discoveries such as Christopher Langton's wonderful Loops and Ant only a few years later. If you are interested in CAs its a good article and worth reading.

Funny enough I started researching biology and computation 1 month ago and so far it has been a wild ride into topics such as biocomputation, emergent computation, evolutionary biology, evolutionary computation and artificial life.

Look up "New Kind Of Science" and the Wolfram Physics project and you are in for a ride.

As a warning, that stuff is a little controversial, to say the least.

I saw that book it is pretty hardcore with over 1000 pages I'm just trying to grasp the basics of Cellular Automata. I'm thinking about reading this book:

https://www.amazon.com/Cellular-Automata-F-Codd/dp/148321174...

by Edgar F. Codd the inventor of relational databases.

Some nice demonstrations of 2d cellular automata https://oeis.org/A139250/a139250.anim.html

Possibly of interest, some work I did with Ed Fredkin several years ago: http://busyboxes.org/?hash=PeciXwDuTA0

Where is Ed these days? He told me once he could replicate dial tones by humming and whistling 2 different frequencies at the same time.

"I wonder which will become self-aware first -- Wolfram Alpha, or Stephen Wolfram."

https://news.ycombinator.com/item?id=9798333

Speaking of self-awareness, we need some as the community—specifically, enough self-awareness to avoid endless reflexive repetition in response to the same provocative stimulus over how many—has it been 20 now?—years. The internet obsession with Wolfram is just a mirror image of the Wolfram-obsession it's complaining about.

https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

We detached this comment from https://news.ycombinator.com/item?id=26895428.

Reply on news.ycombinator.com