Construct a Turing Machine, which implements the Towers of Hanoi.


The non-recursive algorithm by Buneman and Levy can be used, as described by David Harel in his book "Computers Ltd.: what they really can't do":
  1. Execute the following until step 1.2 is not possible anymore:
    1. move the smallest disk clockwise to the next tower;
    2. execute the only possible move with one of the other two disks besides the smallest one;
  2. stop.

Start position

In order to implement the Towers of Hanoi with a program of reasonable size, the towers and disks are displayed in an abstract manner. A tower is a column bounded at the lower end by a #-symbol. A disk is a simple 0, with the meaning that the lowest 0 is the biggest disk and the topmost 0 is the smallest disk.

Final condition

The tower has to be moved according to the rules of the Towers of Hanoi.