Relating to the discussion on whether fractals are part of TCS, my question is:

What are some important work/results in fractals in TCS?

The work/results may be focusing on fractals or it may use fractal concepts as a secondary analysis of some primary topic.

  • 4
    $\begingroup$ I think that you have misunderstood JɛffE’s comments on the linked post. For example, systems of linear equations are not a concept in TCS although they have a lot to do with TCS. In the same sense, fractals are not a concept in TCS. $\endgroup$ – Tsuyoshi Ito Mar 10 '12 at 8:59
  • 3
    $\begingroup$ computability or drawing of fractals can be part of TCS, but fractals for their own sake are generally considered part of the dynamical systems area in math (AFAIK). $\endgroup$ – Kaveh Mar 10 '12 at 15:46

Mark Braverman has written quite a bit about Julia sets. See, e.g. Computability of Julia Sets

  • $\begingroup$ Mark's thesis is also about the computability of these fractals. $\endgroup$ – Kaveh Mar 10 '12 at 5:38

Space filling curves turn out to be useful when building quad trees for search. Sariel's book has more on this.

  • $\begingroup$ I understand they're also being used in graphics cards for rendering textured polygons faster by having better cache locality. Whether that counts as TCS is another question. $\endgroup$ – Peter Taylor Mar 10 '12 at 17:55
  • 1
    $\begingroup$ and for travelling salesman problem. $\endgroup$ – Pratik Deoghare Mar 11 '12 at 8:22

Mandelbrot set $M$ is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number.

Let Set $M=${$c |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is bounded such that every $P^n_c (0)$ has a complex magnitude less than 2 }

The Mandelbrot set is undecidable under computation models over $R$.


yrs ago when I asked about this elsewhere, there was an assertion that "fractals are not technically defined". think there is some validity to that. since then Ive been thinking that maybe fractals are best defined as a computational sequence or "computation tableau" eg via a turing machine. this would be a very broad definition but seems to fit & dont see obvious alternative. (worthy of another question here maybe) or at least there seem to be multiple plausible definitions of fractals.

also in line with this def of fractals in terms of computational tableaus, one major contribution to study of fractals is via cellular automata patterns, heavily studied by Wolfram in New Kind of Science.[1][2]

[1] New Kind of Science/wikipedia

[2] New Kind of Science/Wolfram online version

  • 6
    $\begingroup$ This might be better off as a comment $\endgroup$ – Suresh Venkat Mar 11 '12 at 6:40
  • $\begingroup$ new ref showing deep link between computational complexity (time/space) and fractal characteristics of the TM computational tableau, fractal dimension versus computational complexity by wolfram-affiliated researcher(s) $\endgroup$ – vzn Sep 11 '13 at 18:53

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.