Algorithms as fractals

Question

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

Answer 1

Blum, Shub, and Smale proved that membership in the Mandelbrot set is undecidable in the Real RAM model of computation (known in some upstart circles as the BSS model).

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 2

You can take a look to the work of Lutz, Mayordomo, Hitchcock, Gu et al. on 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" (or the related paper).

See also: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, "The Fractal Geometry of Complexity Classes"

Answer 3

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 is the latter paper.

Answer 4

part of the challenge in this area is there seems not to be a strict formal/mathematical definition of the term "fractal". originally as coined by 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 or the Sierpinsky triangle or even the Weierstrauss 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. eg try

• Fractal geometry, Turing machines, and divide-and-conquer recurrences [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 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.