Decidability in Geometry
Humberto Jose Bortolossi
I've heard it was proved that the Euclidian Geometry is decidable (in
the Godel sense).
I'm looking for geometry problems that are undecidable. It seems Penrose
has stated
a tiling problem that is unsolved.
Please, could someone point me for references or examples of undecidable
geometric problems?
Thank you very much, Humberto.
hjbo...@mat.puc-rio.br
George Russell
>
> Greetings!
>
> I've heard it was proved that the Euclidian Geometry is decidable (in
> the Godel sense).
>
> I'm looking for geometry problems that are undecidable. It seems Penrose
> has stated
> a tiling problem that is unsolved.
is known to be undecidable. See for example
Tilings and Patterns
Branko Gr"unbaum
GC Shephard
WH Freeman and Company, New York (1987)
Chris Hillman
On Thu, 26 Apr 2001, George Russell wrote:
> Working out whether the plane can be tiled with a given set of tiles
> is known to be undecidable.
Typically, you have some finite set of "prototiles" (often, unit squares)
with edges marked in some fashion, and the problem is whether you can tile
-all- of R^2 by placing copies of these prototiles edge to edge so that the
markings match. The proof that this problem is undecidable works by
reducing it to Turing's Halting problem (think of the tiling, if it
exists, as a "history" of the infinite tape of the Turing machine).
By the way, you can often turn a "space" of tilings of R^d into a
dynamical system with the translation action by the (additive abelian)
group R^d (or Z^d, in the case of hypercubical tilings) and perhaps also
an inflation action by the monoid N (c.f. "inflation" acting on the space
of Penrose tilings), or even more general groups. Then you can apply the
machinery of ergodic theory (including spectral theory), topological and
symbolic dynamics, etc., to figure out things like the frequency of
occurrence of the tiles (this has to be defined with some care, of
course!), "recurrence properties", etc. In this context, the
undecidability of the above tiling problem for d >= 2 is one of the major
differences between symbolic dynamics in d = 1 and in higher dimensions.
For the one dimensional theory, see
Symbolic dynamics : one-sided, two-sided, and countable state Markov
shifts,
Bruce P. Kitchens,
Springer-Verlag, 1998.
For some background on higher dimensional shift spaces (Z^d actions on
sequences x:Z^d --> A), see
Ergodic theory on compact spaces,
Manfred Denker, Christian Grillenberger and Karl Sigmund,
Lecture Notes in Mathematics, vol. 527,
Springer-Verlag, 1976.
For a thorough study of an unusually tractable class of higher dimensional
shift spaces, see
Dynamical Systems of Algebraic Origin,
Klaus Schmidt,
Birkhauser-Verlag, 1995.
There are interesting connections with number theory, for some hints
regarding the connections with one-dimensional dynamics see
"Number Theory and Dynamical Systems",
J. Lagarias, in
The Unreasonable Effectiveness of Number Theory,
ed. Stefan A. Burr,
Proceedings in Applied Mathematics, vol. 46,
American Mathematical Society, 1992.
and (shameless plug) the first two talks listed on
http://www.math.washington.edu/~hillman/talks.html
Regarding the notion of "empires", see "What is a Concept?" on
http://www.math.washington.edu/~hillman/papers.html
(this concept can be generalized to higher dimensions; indeed J. H. Conway
introduced it in the context of Penrose tilings). This notion suggests
thinking of symbolic dynamical systems as non-Hausdorff sheaves, which
then leads one to topos theory and nonstandard intuitionistic logics!
Some time back I posted something to sci.physics.research regarding
various rationales for taking this approach to dynamical systems, which is
due to Grothendieck. One of the rationales I mentioned there is precisely
the fact that just as in algebraic geometry it turns out to be helpful to
study properties of an equation regardless of whether any solutions exist,
so it is useful to study symbolic dynamical systems (non-Hausdorff
sheaves with a etale groupoid action) regardless of whether any elements
(global sections) exist. Interestingly enough, topos theory has also
arisen in the search for a quantum theory of gravity, although it is not
yet clear whether topos theory will wind up playing any role here. See
however
http://xxx.lanl.gov/abs/gr-qc/9910005
Note that the classifying object for the N-action which the authors'
discuss in this paper arises very naturally in the topological dynamics of
a non-invertible continuous self-map T on a topological space X; this
should help clarify why nonstandard logics arise naturally in the study of
dynamical systems. For background on topological dynamics and ergodic
theory, see
Introduction to Ergodic Theory,
Peter Walters,
Springer-Verlag, 1981
For a particularly interesting higher dimensional aperiodic tiling and its
connection with an interesting subgroup of a familiar Lie group :-/ see
"Quaquaversal tilings and rotations",
Charles Radin and J. H. Conway,
http://www.ma.utexas.edu/users/radin/tiling.html
and several other papers on that page. Note the similarity between the
tiling problem above and the word problem in combinatorial group theory,
which is also known to be undecidable.
> See for example
>
> Tilings and Patterns
> Branko Gr"unbaum
> GC Shephard
> WH Freeman and Company, New York (1987)
The book was completed by 1977 but not published until 1987 because the
original publisher could not reproduce the figures adequately. Therefore,
it only covers the first few years of research on almost periodic tilings
such as the Penrose tiling. For a readable and more up to date source,
see
Marjorie Senechal,
Quasicrystals and Geometry,
Cambridge University Press, 1995.
(If you can, get the slightly later paperback edition; the hardcover
edition somehow appeared before the publisher obtained the author's final
corrections to the manuscript.)
Sorry if I seem to be rambling-- I was just trying to place the original
question in a broader context.
Chris Hillman
Home Page: http://www.math.washington.edu/~hillman/
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
NOTE: Since I post under my real name, as an anti-spam measure, I have
installed a mail filter which deletes incoming messages not from the
"*.edu" or "*.gov" domains or overseas academic domains.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Fred Galvin
> On Thu, 26 Apr 2001, George Russell wrote:
>
> > Working out whether the plane can be tiled with a given set of tiles
> > is known to be undecidable.
>
> Typically, you have some finite set of "prototiles" (often, unit squares)
> with edges marked in some fashion, and the problem is whether you can tile
> -all- of R^2 by placing copies of these prototiles edge to edge so that the
> markings match. The proof that this problem is undecidable works by
> reducing it to Turing's Halting problem (think of the tiling, if it
> exists, as a "history" of the infinite tape of the Turing machine).
Is the class of all finite sets of prototiles that don't tile the
plane known to be recursively inseparable from the class of those that
tile the plane periodically?