Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I know that a fractal is a non ending pattern, like Pascal's triangle or Sierpinski's triangle, which are the same as Rule 90 from Elementary Cellular Automata.
But, what about the other rules from Elementary CA? Are they also considered to be fractals?
Is there a definition relating Elementary Cellular Automata and fractals?
Cellular automata can generate fractal patterns (as in the case of Rule 90), but they don't always (e.g., Rule 0).
Willson was perhaps the first to demonstrate that CA can produce fractal patterns in the early 80's.
Shortly thereafter Wolfram characterized the fractal properties of a variety of 2-D CAs.
A few years later Culik and Dube went a bit further and proved that certain types of CA :
...will always produce a highly regular [fractal] behavior on an arbitrary finite configuration as the initial seed.
The take-home message is that some very simple CA rule sets generate complex behavior, but others don't do anything interesting at all.
There is not a precise/formal mathematical definition of "fractal" but there are rough informal specifications such as "infinitely self-similar objects".
A CA can output fractal-like configurations depending on the initial configuration. whether it does so is dependent on the initial configuration and CA rules. Some fractals are very regular and others are very irregular/"noisy". An example of a noisy fractal generated by a CA are patterns that contain many triangle-like regions with lots of surrounding noise. Even very simple CA rules can produce fractals. the same CA could produce either fractals or noise depending on the initial input. The interrelationship between CAs and fractals is a continuing area of study/research.
A bigger concept to note here is that CAs in general are "Turing complete" and can create any computation a Turing machine can, so yes, any "computable fractal" can also be generated by some CA. Also some individual CA rule sets are Turing complete.
This is a broad area with lots of refs. Two other refs on the subject:
Inherent Generation of Fractals by Cellular Automata / Martin
See p16 of this slide show Randomness in Computation: More Fractals and Cellular Automata / Cortina for example of simple CA rules that exactly generate the Sierpinski triangle (as you mention) and other related analysis.
