Undecidable problems in fractal geometry. (English) Zbl 0816.58024

Dube, Simant

Complex Syst. 7, No. 6, 423-444 (1993).

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.

MSC:

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

Keywords:

undecidability; iterated function systems; computation; fractal geometry; attractor