Restricted Towers of Hanoi and Morphisms

摘要

The classical towers of Hanoi have been generalized in several ways. In particular the second named author has studied the 3-peg Hanoi towers with all possible restrictions on the permitted moves between pegs. We prove that all these Hanoi puzzles give rise to infinite morphic sequences of moves, whose appropriate truncations describe the transfer of any given number of disks. Furthermore two of these infinite sequences are actually automatic sequences.