Newsgroups: comp.theory
Path: utzoo!utgpu!watserv1!graceland.waterloo.edu!shallit
From: shallit@graceland.waterloo.edu (Jeffrey Shallit)
Subject: Re: Non recursive "Towers of Hanoi"
Message-ID: <1990Dec7.143527.3661@watserv1.waterloo.edu>
Sender: daemon@watserv1.waterloo.edu
Organization: University of Waterloo
References: <1197@disuns2.epfl.ch> <2594@charon.cwi.nl>
Date: Fri, 7 Dec 90 14:35:27 GMT
Lines: 13

In the recent discussion about the Tower of Hanoi problem, I was
surprised to see no one mention the recent article

J.-P. Allouche and F. Dress, Tours de Hanoi et automates,
RAIRO Informatique Theorique et Applications 24 (1990), 1-15.

This article shows that the sequence of moves in the problem can
be computed by a finite automaton (!), and the automaton is
exhibited.  The input is the move number, represented in base 2,
and the output is the move.

Jeff Shallit
University of Waterloo