Problems that do not compute

Today, my task was to convince my students that there are problems which computers cannot solve in a practical time, say a year or a few years! It was meant to be an informal introduction to the concept of the limits of computation and we did it by exploring two specific problems: The towers of Hanoi and the Travelling Salesman.

From wikipedia, Made by User:Evanherk

The Towers of Hanoi

Legend has it that three tall towers stand vertically outside of a temple. The priests of that temple are tasked with transferring the 64 golden disks from one tower to another one. The conditions are:

1. Only one disk can be moved at any one time
2. No disk can rest on top of one that is smaller than itself

When all 64 disks have been moved, the world would end!

At first, we played the game with 1, 2, 3, 4 and then 5 disks, each time recording the minimum number of moves required. The video below shows our attempt with 3 disks:

We now had to deduce a general formula for the number of moves required to transfer any number of disks. To do this, consider the table below, to which I have added a third column to help the reader (a luxury which the students didn't have!):

Number of moves m = 2 to the nth power - 1. For 64 disks, we need roughly 16 x 1 billion x 1 billion moves! If the priests could make a move every 10 seconds, “it would take them well over five trillion years to get the job done.” (Harel, Algorithmics: The Spirit of Computing, 3rd Ed, p. 182, emphasis mine)

Assuming that a computer can make a move each microsecond, it would take around 1,000 years to work this problem out!

That was our first taste of an "intractable" problem, one that cannot be solved in a realistic time frame. We went on to explore another problem. If you found this post interesting and would like to know how we approached the Travelling Salesman Problem, let me know and I will try to report on that too.