5
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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
    Commented Mar 10, 2012 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
    Commented Mar 10, 2012 at 15:46

4 Answers 4

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Mark's thesis is also about the computability of these fractals. $\endgroup$
    – Kaveh
    Commented Mar 10, 2012 at 5:38
8
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Mar 10, 2012 at 17:55
  • 1
    $\begingroup$ and for travelling salesman problem. $\endgroup$
    – Pratik Deoghare
    Commented Mar 11, 2012 at 8:22
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
-9
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ This might be better off as a comment $\endgroup$
    – Suresh Venkat
    Commented Mar 11, 2012 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
    Commented Sep 11, 2013 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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