| |
ISSN 1320-0682 | |||
| Volume 02 | April 1995 | |||
Simant Dube
Department of Mathematics, Statistics and Computing Science
University of New England
Armidale, NSW 2351, Australia
Email: sdube@iterated.com
The emerging science of complex (chaotic) systems has brought remarkable insights into the nature of universe and life. It breaks across disciplinary boundaries as complex systems abound in physical, biological, mathematical, ecological, economic, meteorological and many other fields [6]. Geometrically, one can display the working of such complex systems as fantastic fractal images. A fractal image can be often viewed as a chaotic set of a dynamical system. This link between fractal geometry and complex systems is truly remarkable.
In this paper, the intuitive fact that fractals are complex objects is made precise from a computational point of view by proving that there do not exist algorithms to answer simple questions about fractals.
The notion of undecidability is important in the theory of computation. The Turing machine is a simple computing device but can have complicated behaviour. Rice's Theorem states that any nontrivial property of the recursively enumerable languages which are the languages defined (generated) by Turing machines is undecidable. Similarly, fractals can be defined (generated) by rather simple iterative methods. However, as we will show, these iterative methods can simulate the working of the Turing machine and hence produce complicated sets. Here the Turing machine provides the role of a dynamical system and the fractal image associated with it encodes its "chaotic" set (the words which are not accepted by the Turing machine and may lead to an infinite behaviour in which the machine never halts).
This paper is motivated by a conjecture by Penrose in his book [10] that the Mandelbrot set is undecidable under a reasonable model of computation which allows you to work with real numbers. He speculates that fractals might be a graphical way of looking at nonrecursive mathematics. Under a recently developed model of computation over reals (there does not exist any natural and invariant model), fractal sets have been shown to be undecidable [2]. But what about answering these questions under the classical model of computation over integers (rationals)?
The advantage of working under the Turing machine model is that it is the model in which you can prove that some problem is computationally unsolvable. This model is a natural, rigorous and invariant one, unlike any theory of computation over reals.
We show that even under the classical theory of computation over rational numbers, in which the Turing machine is the model of computation, one can prove some problems about fractals to be undecidable.
Fractal geometry was pioneered by Mandelbrot who showed that many natural objects and phenomena have fractal characteristics [9]. We use iterated function systems as our basic mechanisms to define fractals. IFSs were introduced by Hutchinson [8] and have been further developed and applied for image generation and compression by Barnsley [1]. An IFS is a collection of N contractive affine transformations. Of course we restrict the coefficients of these affine transformations to be rational numbers. An IFS defines a unique set which is the fixed point of a mapping obtained by applying these N affine transformations and then taking the union. Using an iterative method, one can obtain this fixed point in the limit and therefore the fixed point is also called the attractor of the IFS. It is the fractal defined by the IFS. In 2-dimensional real space it would be an image. The iterative method is called the deterministic algorithm for IFS. Generalisations of IFS are studied in [3,4].
In this paper, a number of simple problems about IFS are shown to
be undecidable. For example, given an IFS defined on
the unit square 
, there
is no algorithm to test if its fractal intersects the diagonal line segment
between the 2-D points (0,0) and (1,1).
This also proves the problem of testing the
emptiness of the intersection of fractals defined by two given IFSs
is undecidable. Another undecidable problem
is testing whether a given IFS is totally disconnected.
The proofs are quite straightforward. The basic idea is to interpret strings as numbers and to implement a concatenation operation as a composition of affine transformations. The proofs are obtained by reducing the post correspondence problem (PCP) and its variants. These results allow one to build a simple "geometrical" model of computation based on IFS which is computationally universal [5].
The results in this paper show how the fractal geometry and the computability theory are inter-related. Since the fractal geometry has strong links with the theory of complex systems, one is pleased to see these three scientifically rich disciplines conveying the same basic message, that finitely describable and seemingly simple systems have complex and provably unpredictable behaviour and such systems occur everywhere.
For omitted proofs of the results in this paper, see [5].
We assume that the reader is familiar with the basic theory of computation [7].
We briefly describe the notations for 
-strings and
-languages.
An 
-language is a set of infinite strings (
-strings).
The symbol 
informally means infinite repetition. Thus,
the 
-string
. The
-language
is the set of all
-strings which have finitely
many 0's followed by infinitely many 1's (this language is also
an 
-regular language). Similarly, one can work with
-relations.
The sets of all finite words and 
-strings over
an alphabet 
are
and
respectively
and 
denotes
.
A well-known undecidable problem is the post-correspondence problem:
Given lists A and B of k strings each from
, say
does there exist any sequence of integers
with
such that
The sequence 
is called a solution of
this instance of PCP.
It is also undecidable to test if a given instance of PCP has an
infinite solution. This infinite version of PCP is referred to
as I-PCP in this paper.
An IFS is given by N contractive transformations
on a complete metric space 
. Its notation is:
Typically, X is the k-dimensional Euclidean real space and the
transformations are affine.
We will restrict X to be 
.
A 2-dimensional affine transformation
is defined by
where 
's and
's are rational numbers (since we will be
working under the classical theory of computation, we don't allow
the coefficients to be reals).
Similarly, a 1-dimensional affine transformation
is
defined by 
.
An IFS defines a unique set A which is the fixed point of the
mapping 
where
is the set of non-empty compact subsets of the complete metric space
and W as defined as:
for all 
.
For the proof of existence and uniqueness of A, see [1].
This invariant set A is called the attractor of the IFS and
is the fractal set defined by it.
Figure 1: Illustration of the IFS deterministic algorithm starting
with the unfilled unit square.
(a), (b) and (c) show the parallelograms (squares in this
example) after the first,
second and third iterations, respectively, and a B denotes
a blank region which is not going to be a part of the attractor.
Note how each parallelogram "splits" into three smaller parallelograms
during each iteration.
(d) shows the attractor which is the classic Sierpinski Triangle.
By judiciously choosing transformations, one can generate
images of ferns, trees, mountains, clouds, flowers, etc.
By allowing transformations more general than affine transformations,
IFS can also generate Julia sets.
The undecidability proofs for IFS are quite straightforward.
The basic idea is to interpret strings as numbers in the
unit interval 
.
A string 
(note that 0 is not in
)
is interpreted as a rational number by putting the radix point to the
left and interpreting the string in base-d notation. Thus, if
the string 2112 is interpreted as the ternary
number 0.2112. Similarly, we can interpret
-strings as real
numbers. We define 
where
is the null
string. Formally, we define an interpretation function I:
where 
denotes the set of finite and
-strings
over 
.
The following lemma shows how concatenation of strings can be carried out as a composition of affine transformations.
Proof:
A number in 
has at least one and at most two
-representations
under base-d notation for any d.
If it has two 
-representations then they are of the forms:
where 
are digits and
.
Clearly, I is non-surjective since
and therefore
any number which has a 0 in its representation(s)
would not have a pre-image. It is injective when restricted to
since every number in the
range of I, which has two representations,
will have only the string corresponding to
the first of the two representations given above as its pre-image.
.
Then 
.
Let 
. Let
the representation of a be 
(which would be finite
if x is finite).
Then the representation of 
would be
and therefore 
is
which is 
.
for all
.
Repeatedly apply the fact that 
after
letting 
and
.
,
,
have representations
with matching digits and which become longer and longer.
To see why in the infinite case the above limit does not depend
on the real number with which you start, note that function
for any j is contractive - its contractivity factor
is 
. The maximum of the contractivity factors
of these functions is determined by the smallest of the lengths
of 
. Let it be s, then for any two real numbers
,
which tends to zero as i tends to infinity. In the above,
is the Euclidean distance between two real numbers (in 1-D case it
is |a-b|).
where 
and
and x is any real number;
that is,
Thus, 
and therefore
is surjective.
Since I is injective on 
,
therefore 
is bijective.
We can generalise the above lemma to higher dimensions.
In the 2-D case, we have ordered pairs of strings which are interpreted
as a point in the unit square; that is,
is defined as
Now we can notice why certain problems on IFS would be undecidable. Lemma 1 and its generalisation to 2-D case show that there is exact correspondence between the strings and the concatenation operation, and the application of the corresponding affine transformations. Thus, one can reduce questions on strings obtained by concatenation to questions on numbers obtained by application of affine transformations.
Proof: Consider an instance of I-PCP. Let the two lists be:
Consider the IFS:
Let 
be a 2-D affine transformation
defined as:
Then our claim is that there exists an infinite solution of the I-PCP if and only if the attractor of the IFS intersects the diagonal line segment.
Let 
.
Let A be the attractor of the IFS.
There exists an infinite solution of the I-PCP if and only if there exists
such that
.
Also, A intersects the diagonal line segment if and only if there exists
such that
.
Since, from generalisation of Lemma 1 to 2-D case,
is a bijection, therefore
Thus, there exists an infinite solution of I-PCP
if and only if A intersects the diagonal line.
This completes the proof.
By considering the way the halting problem of Turing machines is
reduced to I-PCP, one can prove the following [5].
Theorem 1 implies that it is undecidable to test if the intersection of the attractors of two given IFSs is empty. This is because for every line segment there exists a simple IFS with teo transformations which defines the line segment as its attractor.
Now we state another interesting undecidability result about IFS. Let
be an IFS with attractor A.
The IFS is called totally disconnected if and only if for all
,
Using a variant of I-PCP, one can show the following [5].
This paper showed a link between computability and fractal geometry motivated by some interesting speculative conjectures of Penrose. The paper suggests a number of challenging but seemingly difficult mathematical problems. Are there algorithms for membership, inclusion and equivalence problems for IFS? Can we test if fractal dimension of the attractor of a given IFS is less than a given rational number? Can we test if the Hausdorff distance between the attractors of two given IFSs is less than a given rational number? Our conjecture is that all nontrivial properties of fractals should be undecidable.
In conclusion, the three important disciplines - computability, fractal geometry and complex systems are closely related. This paper presents one more piece of evidence in the support of this belief.
Undecidable Problems in Fractal Geometry
This document was generated using the LaTeX2HTML translator Version 95.1 (Fri Jan 20 1995) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
l2h -dir dube undecide.tex.
The translation was initiated by Pam Milliken on Mon Oct 14 14:15:33 EST 1996
