<p>You can take a look to the work of Lutz, Mayordomo, Hitchcock, Gu et al. on <a href="http://en.wikipedia.org/wiki/Effective_dimension" rel="nofollow">Effective dimension</a>:</p>

<p><em>... In mathematics, effective dimension is a modification of Hausdorff dimension and other fractal dimensions which places it in a computability theory setting ...</em></p>

<p>I found interesting (though I'm not an expert) E. Mayordomo's introductive video <a href="http://sms.cam.ac.uk/media/1254201" rel="nofollow">"Effective Fractal Dimension in Computational Complexity and Algorithmic Information Theory"</a> (or the related <a href="http://webdiis.unizar.es/~elvira/publicaciones/efdait.pdf" rel="nofollow">paper</a>).</p>

<p>See also: <a href="http://www.cs.uwyo.edu/~jhitchco/papers/fgcc.pdf" rel="nofollow">John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, "The Fractal Geometry of Complexity Classes"</a></p>

CC BY-SA 3.0
2013-03-22T11:54:45.813Z
2013-03-22T13:24:28.547Z
2013-03-22T13:24:28.547Z
Marzio De Biasi
<p>part of the challenge in this area is there seems not to be a strict formal/mathematical definition of the term <a href="http://en.wikipedia.org/wiki/Fractal" rel="nofollow">"fractal"</a>. originally as coined by <a href="http://en.wikipedia.org/wiki/Benoit_Mandelbrot" rel="nofollow">Mandelbrot</a> in 1975 it had an informal geometric interpretation but is now seen as more general, eg applying to misc important mathematical objects created/discovered before unifying principles/properties of fractals were recognized, such as <a href="http://en.wikipedia.org/wiki/Cantor_dust#Cantor_dust" rel="nofollow">Cantor dust</a> or the <a href="http://en.wikipedia.org/wiki/Sierpinski_triangle" rel="nofollow">Sierpinsky triangle</a> or even the <a href="http://en.wikipedia.org/wiki/Weierstrass_function" rel="nofollow">Weierstrauss function</a>. </p>

<p>of course as in these examples an algorithm to draw fractals has fractal complexity properties. however there seems to be a much deeper connection between fractals and algorithms (maybe fundamental?) as uncovered in the links between fractal computations and undecidability (maybe two faces of the same phenomena?).</p>

<p>one alternative is to consider the closely related <a href="http://en.wikipedia.org/wiki/Iterated_function_system" rel="nofollow">iterated function systems</a>. eg try </p>

<ul>
<li><a href="https://eudml.org/doc/92487" rel="nofollow">Fractal geometry, Turing machines, and divide-and-conquer recurrences</a> <a href="http://archive.numdam.org/ARCHIVE/ITA/ITA_1994__28_3-4/ITA_1994__28_3-4_405_0/ITA_1994__28_3-4_405_0.pdf" rel="nofollow">[pdf]</a>
S. Dube,
Informatique
théorique
et
Applications/Theoietical
Informaties
and
Applications
(vol.
28,
no
3-4,
1994,
p.
405-423)</li>
</ul>

<blockquote>
  <p>These
  results
  show
  that
  for
  every
  Turing
  machine
  there
  exists
  a
  fractal
  set
  which
  can
  be
  viewed,
  in
  a
  certain
  sense,
  as
  geometrically
  encoding
  the
  complement
  of
  the
  language
  accepted
  by
  the
  machine.
  One
  can
  build
  a
  fractal-based
  geometrical
  model
  of
  computation
  which
  is
  computationally
  universal.
  Secondly
  we
  survey
  the
  results
  which
  show
  how
  fractal
  geometry
  can
  be
  fruitfully
  used
  to
  solve
  divide-and-conquer
  recurrences.
  A
  recursive
  algorithm
  possesses
  temporal
  self-similarity
  and
  there
  is
  a
  natural
  connection
  with
  spatial
  self-similar
  objects
  (fractal
  images).
  This
  approach
  yields
  a
  new
  and
  gênerai
  way
  of
  solving
  such
  divide-and-conquer
  récurrences.</p>
</blockquote>

<ul>
<li><a href="http://www.complex-systems.com/pdf/07-6-2.pdf" rel="nofollow">Undecidable
Problems
in
Fractal
Geometry</a>
S. Dube, Complex
Systems
7
(1993)
423-444</li>
</ul>

<blockquote>
  <p>In this
  paper, a
  relationship
  between
  the
  classical
  theory
  of
  computation
  and
  fractal
  geometry
  is
  established.
  Iterated Function
  Systems are
  used
  as
  tools
  to
  define
  fractals.
  It
  is
  shown
  that
  two
  questions about
  Iterated
  Function
  Systems are
  undecidable:
  to test
  if the
  attractor
  of
  a
  given Iterated
  Function
  System
  and
  a given
  line
  segment intersect
  and to
  test
  if a given
  Iterated
  Function System
  is
  totally
  disconnected.</p>
</blockquote>

CC BY-SA 3.0
2013-03-27T15:33:12.440Z
2013-03-27T15:33:12.440Z
vzn
<p>An application of fractals in document analysis has been proposed in</p>

<p>Tang, Y.Y.; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., "A new approach to document analysis based on modified fractal signature," Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on , vol.2, no., pp.567,570 vol.2, 14-16 Aug 1995
doi: 10.1109/ICDAR.1995.601960</p>

<p>Here is the abstract:</p>

<p>The proposed approach is based on modified fractal signature. Instead of the time-consuming traditional approaches (top-down and bottom-up approaches) where iterative operations are necessary to break a document into blocks to extract its geometric (layout) structure, this new approach can divide a document into blocks in only one step. This approach can be used to process documents with high geometrical complexity. Experiments have been conducted to prove the proposed new approach for document processing</p>

<p>Two years later, they published an extended journal version:</p>

<p>Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, "Modified Fractal Signature (MFS): A New Approach to Document Analysis for Automatic Knowledge Acquisition," IEEE Transactions on Knowledge and Data Engineering, vol. 9, no. 5, pp. 747-762, September-October, 1997 </p>

<p><a href="http://www.sc.ehu.es/ccwgrrom/transparencias/articulos-alumnos-doct-2002/andoni/00634753.pdf" rel="nofollow">Here</a> is the latter paper.</p>

CC BY-SA 3.0
2013-03-24T08:41:21.803Z
2013-03-24T08:41:21.803Z
Massimo Cafaro
<p>Blum, Shub, and Smale proved that <a href="http://books.google.com/books?id=zxtrVqUP-AwC&amp;lpg=PA55&amp;pg=PA55#v=onepage&amp;q&amp;f=true" rel="nofollow noreferrer">membership in the Mandelbrot set is undecidable</a> in the <a href="http://en.wikipedia.org/wiki/Real_RAM" rel="nofollow noreferrer">Real RAM model</a> of computation (known in <a href="https://cstheory.stackexchange.com/a/2124/111">some upstart circles</a> as the <a href="http://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine" rel="nofollow noreferrer">BSS model</a>).  </p>

<p>The high-level argument is one sentence long: Any Real RAM computable set is the countable union of semi-algebraic sets, so its boundary has Hausdorff dimension 1, but the boundary of the Mandelbrot set has Hausdorff dimension 2.  By the same argument, <strong>almost every interesting fractal is uncomputable</strong> in the real-RAM model.</p>

CC BY-SA 3.0
2013-03-22T18:11:28.180Z
2013-03-24T05:56:07.960Z
2017-04-13T12:32:28.117Z
Jeffε
<p>Recursion utilizes some self similar nature of an object (some representation of the given problem) to produce some quantitative measure (output) on the object through some algorithm (utilizing the self similar nature). </p>

<p>Can one represent algorithms as fractals (such a representation is not possible is not obvious nor how the representation should be if one exists) of some measurable information of the object the algorithm works on? </p>

<p>Has the tools used in the study of fractals provided any illuminating examples for lower or upper bounds for recursive complexity of algorithms?</p>

<p>I am looking for examples and references along the lines of whether algorithms can be treated as fractals and tools about fractals can be used to prove results about algorithms.</p>

<p><strong>just added</strong> Would we be compelled to redefine some essential property of Sierpinski triangle if Walsh Transform or Sierpinski triangle transform is shown to be fully linear?
<a href="http://en.wikipedia.org/wiki/Walsh_matrix" rel="nofollow">http://en.wikipedia.org/wiki/Walsh_matrix</a></p>

CC BY-SA 3.0
2013-03-24T06:41:45.187Z
IIUC, you are asking: "has tools used in the study of fractals been used in proving lower/upper-bounds on the complexity of algorithms?". You may want to expand more on why you think that is likely and explain the first paragraph in more detail. Many fractals are recursively defined and have self-similar structure but I don't think one implies the other: recursive definition of an object doesn't mean it is a fractal and a fractal doesn't need to be recursively defined. I don't see how information comes into play here.
Kaveh
CC BY-SA 3.0
2013-03-24T06:42:49.097Z
By the way, I am not sure what you mean by "recursive complexity of algorithms". Do you mean something other than the usual notions of complexity of algorithms? ps: I edited the question a bit to make it easier to read, feel free to roll back my edit.
Kaveh
CC BY-SA 3.0
2013-03-25T08:19:48.760Z
JeffE's answer seems to be close to why such a framework may not be possible.
Turbo
CC BY-SA 3.0
2013-03-25T08:45:50.823Z
I am not sure how that follows from Jeff's answer. ps: More generally the real RAM model is one of the approaches to computable analysis. In the opinion of many experts in computable analysis it is not a very good model, particularly from the practical perspective, as it lacks the ability to deal with limits which is essential for analysis and the model doesn't correspond to how we deal with real numbers in practice.  There are papers by Ker-I Ko, Mark Braverman, ... on computability/complexity of fractals. Btw, ch.9 of Weirauch book has a comparision of different models if you are interested.
Kaveh
CC BY-SA 3.0
2013-03-25T12:36:11.723Z
'close' is a relative term here. I take the cue from 'almost every interesting fractal is uncomputable'. However including your feedback seems to say something about the question as well.
Turbo
CC BY-SA 3.0
2013-03-25T15:04:53.707Z
there is some research linking fractals to hardness of [SAT instances](http://cstheory.stackexchange.com/questions/4375/which-sat-problems-are-easy/16431)
vzn
<cc.complexity-theory><fractals>
Algorithms as fractals
Turbo
# Algorithms as fractals

(Asked by: username_0 on 2013-03-22)

Recursion utilizes some self similar nature of an object (some representation of the given problem) to produce some quantitative measure (output) on the object through some algorithm (utilizing the self similar nature).

Can one represent algorithms as fractals (such a representation is not possible is not obvious nor how the representation should be if one exists) of some measurable information of the object the algorithm works on?

Has the tools used in the study of fractals provided any illuminating examples for lower or upper bounds for recursive complexity of algorithms?

I am looking for examples and references along the lines of whether algorithms can be treated as fractals and tools about fractals can be used to prove results about algorithms.

**just added** Would we be compelled to redefine some essential property of Sierpinski triangle if Walsh Transform or Sierpinski triangle transform is shown to be fully linear?
<http://en.wikipedia.org/wiki/Walsh_matrix>

**Tags:** cc.complexity-theory, fractals

> **Comments:**
> **username_1**: IIUC, you are asking: "has tools used in the study of fractals been used in proving lower/upper-bounds on the complexity of algorithms?". You may want to expand more on why you think that is likely and explain the first paragraph in more detail. Many fractals are recursively defined and have self-similar structure but I don't think one implies the other: recursive definition of an object doesn't mean it is a fractal and a fractal doesn't need to be recursively defined. I don't see how information comes into play here.  
> **username_1**: By the way, I am not sure what you mean by "recursive complexity of algorithms". Do you mean something other than the usual notions of complexity of algorithms? ps: I edited the question a bit to make it easier to read, feel free to roll back my edit.  
> **username_0**: JeffE's answer seems to be close to why such a framework may not be possible.  
> **username_1**: I am not sure how that follows from Jeff's answer. ps: More generally the real RAM model is one of the approaches to computable analysis. In the opinion of many experts in computable analysis it is not a very good model, particularly from the practical perspective, as it lacks the ability to deal with limits which is essential for analysis and the model doesn't correspond to how we deal with real numbers in practice.  There are papers by Ker-I Ko, Mark Braverman, ... on computability/complexity of fractals. Btw, ch.9 of Weirauch book has a comparision of different models if you are interested.  
> **username_0**: 'close' is a relative term here. I take the cue from 'almost every interesting fractal is uncomputable'. However including your feedback seems to say something about the question as well.  
> **username_2**: there is some research linking fractals to hardness of [SAT instances](http://cstheory.stackexchange.com/questions/4375/which-sat-problems-are-easy/16431)  

---

## 4 answers

### Answer by username_5 on 2013-03-22. Score: 14 | Accepted answer

Blum, Shub, and Smale proved that [membership in the Mandelbrot set is undecidable](http://books.google.com/books?id=zxtrVqUP-AwC&lpg=PA55&pg=PA55#v=onepage&q&f=true) in the [Real RAM model](http://en.wikipedia.org/wiki/Real_RAM) of computation (known in [some upstart circles](https://cstheory.stackexchange.com/a/2124/111) as the [BSS model](http://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine)).

The high-level argument is one sentence long: Any Real RAM computable set is the countable union of semi-algebraic sets, so its boundary has Hausdorff dimension 1, but the boundary of the Mandelbrot set has Hausdorff dimension 2. By the same argument, **almost every interesting fractal is uncomputable** in the real-RAM model.


---

### Answer by username_3 on 2013-03-22. Score: 4

You can take a look to the work of Lutz, Mayordomo, Hitchcock, Gu et al. on [Effective dimension](http://en.wikipedia.org/wiki/Effective_dimension):

*... In mathematics, effective dimension is a modification of Hausdorff dimension and other fractal dimensions which places it in a computability theory setting ...*

I found interesting (though I'm not an expert) E. Mayordomo's introductive video ["Effective Fractal Dimension in Computational Complexity and Algorithmic Information Theory"](http://sms.cam.ac.uk/media/1254201) (or the related [paper](http://webdiis.unizar.es/~elvira/publicaciones/efdait.pdf)).

See also: [John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, "The Fractal Geometry of Complexity Classes"](http://www.cs.uwyo.edu/~jhitchco/papers/fgcc.pdf)


---

### Answer by username_2 on 2013-03-27. Score: 2

part of the challenge in this area is there seems not to be a strict formal/mathematical definition of the term ["fractal"](http://en.wikipedia.org/wiki/Fractal). originally as coined by [Mandelbrot](http://en.wikipedia.org/wiki/Benoit_Mandelbrot) in 1975 it had an informal geometric interpretation but is now seen as more general, eg applying to misc important mathematical objects created/discovered before unifying principles/properties of fractals were recognized, such as [Cantor dust](http://en.wikipedia.org/wiki/Cantor_dust#Cantor_dust) or the [Sierpinsky triangle](http://en.wikipedia.org/wiki/Sierpinski_triangle) or even the [Weierstrauss function](http://en.wikipedia.org/wiki/Weierstrass_function).

of course as in these examples an algorithm to draw fractals has fractal complexity properties. however there seems to be a much deeper connection between fractals and algorithms (maybe fundamental?) as uncovered in the links between fractal computations and undecidability (maybe two faces of the same phenomena?).

one alternative is to consider the closely related [iterated function systems](http://en.wikipedia.org/wiki/Iterated_function_system). eg try

* [Fractal geometry, Turing machines, and divide-and-conquer recurrences](https://eudml.org/doc/92487) [[pdf]](http://archive.numdam.org/ARCHIVE/ITA/ITA_1994__28_3-4/ITA_1994__28_3-4_405_0/ITA_1994__28_3-4_405_0.pdf)
  S. Dube,
  Informatique
  théorique
  et
  Applications/Theoietical
  Informaties
  and
  Applications
  (vol.
  28,
  no
  3-4,
  1994,
  p.
  405-423)

> These
> results
> show
> that
> for
> every
> Turing
> machine
> there
> exists
> a
> fractal
> set
> which
> can
> be
> viewed,
> in
> a
> certain
> sense,
> as
> geometrically
> encoding
> the
> complement
> of
> the
> language
> accepted
> by
> the
> machine.
> One
> can
> build
> a
> fractal-based
> geometrical
> model
> of
> computation
> which
> is
> computationally
> universal.
> Secondly
> we
> survey
> the
> results
> which
> show
> how
> fractal
> geometry
> can
> be
> fruitfully
> used
> to
> solve
> divide-and-conquer
> recurrences.
> A
> recursive
> algorithm
> possesses
> temporal
> self-similarity
> and
> there
> is
> a
> natural
> connection
> with
> spatial
> self-similar
> objects
> (fractal
> images).
> This
> approach
> yields
> a
> new
> and
> gênerai
> way
> of
> solving
> such
> divide-and-conquer
> récurrences.

* [Undecidable
  Problems
  in
  Fractal
  Geometry](http://www.complex-systems.com/pdf/07-6-2.pdf)
  S. Dube, Complex
  Systems
  7
  (1993)
  423-444

> In this
> paper, a
> relationship
> between
> the
> classical
> theory
> of
> computation
> and
> fractal
> geometry
> is
> established.
> Iterated Function
> Systems are
> used
> as
> tools
> to
> define
> fractals.
> It
> is
> shown
> that
> two
> questions about
> Iterated
> Function
> Systems are
> undecidable:
> to test
> if the
> attractor
> of
> a
> given Iterated
> Function
> System
> and
> a given
> line
> segment intersect
> and to
> test
> if a given
> Iterated
> Function System
> is
> totally
> disconnected.


---

### Answer by username_4 on 2013-03-24. Score: 2

An application of fractals in document analysis has been proposed in

Tang, Y.Y.; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., "A new approach to document analysis based on modified fractal signature," Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on , vol.2, no., pp.567,570 vol.2, 14-16 Aug 1995
doi: 10.1109/ICDAR.1995.601960

Here is the abstract:

The proposed approach is based on modified fractal signature. Instead of the time-consuming traditional approaches (top-down and bottom-up approaches) where iterative operations are necessary to break a document into blocks to extract its geometric (layout) structure, this new approach can divide a document into blocks in only one step. This approach can be used to process documents with high geometrical complexity. Experiments have been conducted to prove the proposed new approach for document processing

Two years later, they published an extended journal version:

Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, "Modified Fractal Signature (MFS): A New Approach to Document Analysis for Automatic Knowledge Acquisition," IEEE Transactions on Knowledge and Data Engineering, vol. 9, no. 5, pp. 747-762, September-October, 1997

[Here](http://www.sc.ehu.es/ccwgrrom/transparencias/articulos-alumnos-doct-2002/andoni/00634753.pdf) is the latter paper.


---

