Automatic maps on the Gaussian integers
Thijmen J. P. Krebs · Research Repository (Delft University of Technology) · 2013
How can you define automatic maps on the Gaussian integers? The two key components of an automatic map are an automaton, and a numeration system that represents every Gaussian integer at least once. We start by giving a brief introduction to automata and language theory, and go on to establish the existence of a numeration system for the Gaussian integers in every base. The literature is quite scarce on this latter subject, however, so we have to reproduce a referenced result that proved too hard to find. With the basic components covered, we define the concept of automatic maps, and show that it does not rely on the particular choice of numeration system in a given base. We then continue to prove that a map is automatic with respect to every multiplicatively dependent base, and show that there exist automatic maps that are not automatic in any multiplicatively independent base. Consequently, it reveals partly how an analogue of Cobham's deep theorem for the Gaussian integers will look like, and answers an open question in the literature negatively.