6
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ fractals are quite readily produced with CAs although there is not a simple/ mathematical definition of "fractal". "infinite selfsimilarity" is maybe the closest that can be constructed. $\endgroup$ – vzn Sep 11 '15 at 21:39
  • 1
    $\begingroup$ see also formal definition of "fractal" or standardized categories? $\endgroup$ – vzn Sep 18 '15 at 4:24
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.