Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: immortality problem

Sortuj według:

Ogranicz wyniki do:

Piecewise Affine Functions, Sturmian Sequences and Wang Tiles

Kari J.

Fundamenta Informaticae

2016

Vol. 145, nr 3

257--277

The tiling problem is the decision problem to determine if the infinite plane can be tiled by copies of finitely many given Wang tiles. The problem is known since the 1960's to be undecidable. The undecidability is closely related to the existence of aperiodic Wang tile sets. There is a known method to construct small aperiodic tile sets that simulate iterations of one-dimensional piecewise linear functions using encodings of real numbers as Sturmian sequences. In this paper we provide details of a similar simulation of two-dimensional piecewise affine functions byWang tiles. Mortality of such functions is undecidable, which directly yields another proof of the undecidability of the tiling problem. We apply the same technique on the hyperbolic plane to provide a strongly aperiodic hyperbolic Wang tile set and to prove that the hyperbolic tiling problem is undecidable. These results are known in the literature but using different methods.