Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 Mar 24 '13 at 6:41
    
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 Mar 24 '13 at 6:42
    
JeffE's answer seems to be close to why such a framework may not be possible. –  Turbo Mar 25 '13 at 8:19
    
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 Mar 25 '13 at 8:45
    
'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 Mar 25 '13 at 12:36

4 Answers 4

up vote 14 down vote accepted

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.

share|improve this answer

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"

share|improve this answer
2  
+1 Very nice video lecture. –  Mohammad Al-Turkistany Mar 28 '13 at 12:14

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.

share|improve this answer

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

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.

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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