Computations in hyperbolic spaces

Slides

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.

References

[1]

M. Margenstern,Cellular Automata in Hyperbolic Spaces, vol. 1: Theory, Old City Publishing, Philadelphia, 2007, 422p.

[2]

M. Margenstern, Cellular Automata in Hyperbolic Spaces, vol. 2: Implementation and computations, Advances in Unconventional Computing and Cellular Automata Series, Old City Publishing, Philadelphia, 2008, 360p.

[3]

M. Margenstern, New Tools for Cellular Automata of the Hyperbolic Plane, Journal of Universal Computer Science, vol. 6(12), (2000), 1226–1252.

[4]

M. Margenstern, Cellular Automata and Combinatoric Tilings in Hyperbolic Spaces, a survey, Lecture Notes in Computer Sciences, vol. 2731, (2003), 48-72.

[5]

M. Margenstern, The domino problem of the hyperbolic plane is undecidable, Theoretical Computer Science, vol. 407, (2008), 29-84.

[6]

M. Margenstern, The injectivity of the global function of a cellular automaton in the hyperbolic plane is undecidable, arXiv:cs/0806.1602: (2008), 29p.

[7]

M. Margenstern, Y. Song, A new universal cellular automaton on the pentagrid, AUTOMATA’2008, Bristol, UK, June, 12-14, 2008.

[8]

M. Margenstern, Y. Song, A universal cellular automaton on the ternary heptagrid, Electronic Notes in Theoretical Computer Science, vol. 223, (2008), 167-185.

This document was translated from L^AT_EX by H^EV^EA.