Guy wrote: << The recent question about a fallible agent taking on the 'Towers of Hanoi' leads me to look for a way of compactly indexing the 'States of Hanoi', i.e. the different states of the 1-person game. Godel-numbering the states is too 'spacious' but might be a element of the algorithm to achieve compact indexing. All ideas welcome: thank you - Guy
Any state of the game is a mapping from the set D of n disks (say D = Z/nZ) to the set P of 3 posts (say P = Z/3Z). (Given the set of disks on any one post, their order on that post is determined, so this mapping determines the full state of the game.) Questions: 1. Starting any two of these 3^n states -- say A and B -- can B be reached from A by a sequence of legal moves? (If not, for which A, B is this possible?) 2. When state B can be legally reached from state A, what is an algorithm for using the fewest moves to do this? --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele