Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cellular Automata (1983) [pdf]

content.wolfram.com

Post reply on HN
Print view View original

11–20 of 21 posts

Re: Cellular Automata (1983) [pdf]

#11

Post by Gehinnn »

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.

Re: Cellular Automata (1983) [pdf]

#12

Post by nelsonmandela »

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

Re: Cellular Automata (1983) [pdf]

#13

Post by anonu »

danbmil99 wrote: post #9
meroes wrote: post #2

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.

Re: Cellular Automata (1983) [pdf]

#14

Post by moonchild »

peheje wrote: post #4

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

Re: Cellular Automata (1983) [pdf]

#15

Post by dang »

MengerSponge wrote: post #5

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

Re: Cellular Automata (1983) [pdf]

#16

Post by jnakayama »

Gehinnn wrote: post #11

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…

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/

Re: Cellular Automata (1983) [pdf]

#17

Post by ganafagol »

mrkramer wrote: post #8

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.

Re: Cellular Automata (1983) [pdf]

#18

Post by erwinh »

nelsonmandela wrote: post #12

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

Re: Cellular Automata (1983) [pdf]

#19

Post by monk_e_boy »

nelsonmandela wrote: post #12

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

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

Re: Cellular Automata (1983) [pdf]

#20

Post by mrkramer »

ganafagol wrote: post #17
mrkramer wrote: post #8

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.

Post reply on HN