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
Algorithms as fractals
cc.complexity theory;fractals
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.