Computations in hyperbolic spacesMaurice MargensternUniversité Paul Verlaine − Metz, LITA, EA 3097 |
In this paper, we give a survey on results about computations in hyperbolic spaces, mainly in the hyperbolic plane.
First, we remind the setting and the very basic features of hyperbolic geometry. Next, we introduce coordinates for tilings in the hyperbolic plane. After reminding the notion of tilings and that there are infinitely many ones based on regular polygons in the hyperbolic plane, we introduce the splitting method. This methods defines a recursive procedure to split the successive regions in finitely many parts producing a certain number of tiles at each step. As a result, we obtain a bijection of the tiling onto a tree which can be algorithmically constructed. This allows to define coordinates. Besides results on general properties on various families of tilings, we give several applications of the coordinates to several problems: defining the shortest path between two tiles, changing the centre of coordinate systems, locating points in the pentagrid and in the heptagrid and other coonected results as coordinates for points of the hyperbolic plane and the construction of a Peano curve.
Then, we go back to the application of the method to the tiling problem of the hyperbolic plane. We present a general construction of a grid in a particular tiling of the hyperbolic plane, the heptagrid, but the same can be done in infinitely many tilings of this plane. Thanks to this, we introduce the ingredients of the proof that the tiling problem is undecidable in the hyperbolic plane.
The last, but not least section of the talk is devoted to the application of the splitting method to cellular automata in the hyperbolic plane. First, we establish a general characterization of cellular automata on the pentagrid or the heptagrid in terms of their global function. Then, taking advantage of the construction used for the tiling problem, we refine the construction in order to obtain that the injectivity of the golbal function of a cellular automaton on the heptagrid is an undecidable property. Next, we present several results on the construction of weakly universal cellular automata with a small number of states, all of them based on the implementation of a railway circuit. We conclude this section with a particular family of tilings of the hyperbolic plane which allows us to define a model of computation which has a super-Turing ability.
The first two references contain a lot of references, in particular those of [4], below.
This document was translated from LATEX by HEVEA.