<p>Space filling curves turn out to be useful when building quad trees for search. <a href="http://valis.cs.uiuc.edu/~sariel/book/">Sariel's book has more on this</a>. </p>

CC BY-SA 3.0
2012-03-10T17:55:02.857Z
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.
Peter Taylor
CC BY-SA 3.0
2012-03-11T08:22:44.403Z
and for [travelling salesman problem](http://www2.isye.gatech.edu/~jjb/mow/mow.html).
Pratik Deoghare
CC BY-SA 3.0
2012-03-10T03:21:19.727Z
2012-03-10T03:21:19.727Z
Suresh Venkat
<p>Mandelbrot set $M$ is defined using the complex equation $P_c (z)=z^2 +c$  where $c$ is a complex number.</p>

<p>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 }</p>

<p>The Mandelbrot set is <a href="http://www.complex-systems.com/pdf/07-6-2.pdf" rel="nofollow">undecidable</a> under computation models over $R$.</p>

CC BY-SA 3.0
2012-03-11T08:56:42.920Z
and of course there's this question: http://cstheory.stackexchange.com/questions/778/complexity-of-a-variant-of-the-mandelbrot-set-decision-problem
Suresh Venkat
CC BY-SA 3.0
2012-03-10T09:03:53.607Z
2012-03-10T09:22:56.950Z
2012-03-10T09:22:56.950Z
Mohammad Al-Turkistany
<p>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 &amp; dont see obvious alternative. (worthy of another question here maybe) or at least there seem to be multiple plausible definitions of fractals.</p>

<p>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]</p>

<p>[1] <a href="http://en.wikipedia.org/wiki/A_New_Kind_of_Science" rel="nofollow">New Kind of Science/wikipedia</a></p>

<p>[2] <a href="http://www.wolframscience.com/nksonline/toc.html" rel="nofollow">New Kind of Science/Wolfram online version</a></p>

CC BY-SA 3.0
2012-03-11T06:40:48.257Z
This might be better off as a comment
Suresh Venkat
CC BY-SA 3.0
2013-09-11T18:53:20.853Z
new ref showing deep link between computational complexity (time/space) and fractal characteristics of the TM computational tableau, [fractal dimension versus computational complexity](http://arxiv.org/abs/1309.1779) by wolfram-affiliated researcher(s)
vzn
CC BY-SA 3.0
2012-03-11T03:05:39.847Z
2012-03-11T03:05:39.847Z
vzn
<p>Mark Braverman has written quite a bit about Julia sets. See, e.g. <a href="http://www.springer.com/mathematics/computational+science+%26+engineering/book/978-3-540-68546-3" rel="nofollow">Computability of Julia Sets</a></p>

CC BY-SA 3.0
2012-03-10T05:38:37.700Z
Mark's thesis is also about the computability of these fractals.
Kaveh
CC BY-SA 3.0
2012-03-10T01:34:26.177Z
2012-03-11T08:48:47.150Z
2012-03-11T08:48:47.150Z
Aaron Roth
<p>Relating to the <a href="https://cstheory.stackexchange.com/a/10377/7884">discussion on whether fractals are part of TCS</a>, my question is:</p>

<blockquote>
  <p>What are some important work/results in fractals in TCS?</p>
</blockquote>

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

CC BY-SA 3.0
2012-03-10T08:59:02.027Z
I think that you have misunderstood JɛﬀE’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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-10T15:46:24.267Z
computability or drawing of fractals can be part of TCS, but [fractals](http://en.wikipedia.org/wiki/Fractals) for their own sake are generally considered part of the [dynamical systems](http://en.wikipedia.org/wiki/Dynamical_system) area in math (AFAIK).
Kaveh
<reference-request><fractals>
What is some important work in fractals?
vzn
# What is some important work in fractals?

(Asked by: username_0 on 2012-03-10)

Relating to the [discussion on whether fractals are part of TCS](https://cstheory.stackexchange.com/a/10377/7884), 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.

**Tags:** reference-request, fractals

> **Comments:**
> **username_1**: I think that you have misunderstood JɛﬀE’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.  
> **username_2**: computability or drawing of fractals can be part of TCS, but [fractals](http://en.wikipedia.org/wiki/Fractals) for their own sake are generally considered part of the [dynamical systems](http://en.wikipedia.org/wiki/Dynamical_system) area in math (AFAIK).  

---

## 4 answers

### Answer by username_7 on 2012-03-10. Score: 10 | Accepted answer

Mark Braverman has written quite a bit about Julia sets. See, e.g. [Computability of Julia Sets](http://www.springer.com/mathematics/computational+science+%26+engineering/book/978-3-540-68546-3)

> **Comments:**
> **username_2**: Mark's thesis is also about the computability of these fractals.  

---

### Answer by username_3 on 2012-03-10. Score: 8

Space filling curves turn out to be useful when building quad trees for search. [Sariel's book has more on this](http://valis.cs.uiuc.edu/~sariel/book/).

> **Comments:**
> **username_4**: 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.  
> **username_5**: and for [travelling salesman problem](http://www2.isye.gatech.edu/~jjb/mow/mow.html).  

---

### Answer by username_6 on 2012-03-10. Score: 4

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](http://www.complex-systems.com/pdf/07-6-2.pdf) under computation models over $R$.

> **Comments:**
> **username_3**: and of course there's this question: http://cstheory.stackexchange.com/questions/778/complexity-of-a-variant-of-the-mandelbrot-set-decision-problem  

---

### Answer by username_0 on 2012-03-11. Score: -9

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](http://en.wikipedia.org/wiki/A_New_Kind_of_Science)

[2] [New Kind of Science/Wolfram online version](http://www.wolframscience.com/nksonline/toc.html)

> **Comments:**
> **username_3**: This might be better off as a comment  
> **username_0**: new ref showing deep link between computational complexity (time/space) and fractal characteristics of the TM computational tableau, [fractal dimension versus computational complexity](http://arxiv.org/abs/1309.1779) by wolfram-affiliated researcher(s)  

---

