zbMATH — the first resource for mathematics

Undecidable problems in fractal geometry. (English) Zbl 0816.58024
Summary: 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. The proofs are very simple and are obtained by reducing the Post Correspondence Problem and by interpreting strings as numbers and concatenation operations as compositions of affine transformations. 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.

37B99 Topological dynamics
28A80 Fractals
68Q25 Analysis of algorithms and problem complexity
37D45 Strange attractors, chaotic dynamics of systems with hyperbolic behavior