Limits of Computing

It began in the 1930s when a group of talented mathematicians came together to lay the foundations of theoretical computer science.  There work paved the way for the computer revolution, which in turn led to significant breakthroughs in scientific investigation, and in many other areas of discourse.  Computers provided us with the capability of solving problems requiring serious number crunching, and extensive resources.   However, as powerful as computers are, they do have inherent limitations.   In fact, provided with any sufficiently powerful machine, it has been proved that there are well defined problems that cannot be computed in this framework.   One such problem is the Halting Problem.  First proved in 1937, the Halting Problem basically asks whether it  is possible to write a program Halt(function, input), which returns True if function(input) eventually halts and returns False otherwise.  This is impossible to do.  The proof was discussed in lecture, and an alternative version can be found at http://wally.cs.iupui.edu/csci230/files/t16Haltingproblem.htm.

Problem Solving Episode: Penny Piles

What is the Problem ?: Suppose there are two drawers, where the left one contains 64 pennies and the right contains none. We are asked to determine whether it is possible to rearrange things so that one drawer has exactly 48 pennies using only two given operations.

L:  If the left drawer has an even number of pennies, transfer half of them to the right drawer (operation is disallowed if left drawer has odd number of pennies).

R: If the right drawer has an even number of pennies, transfer half of them to the left drawer (operation is disallowed if right drawer has odd number of pennies).

Understanding the Problem: In the problem, we are given: 1. The left drawer contains 64 pennies,  2. The right drawer contains no pennies, 3. Allowed to perform only two basic operations  L and R.  In the problem we are required to determine: If by using only L and R we can arrange things so one drawer has 48 pennies.  

Devising a Plan: We can create a table containing two columns representing the number of pennies in each drawer respectively.  As a starting point, we will have the left drawer containing 64 pennies and the right 0 pennies (by 1 & 2).

Since the left drawer initially contains an even number of pennies we can continually apply L, until the right drawer contains 48 pennies (by 3).

Carrying Out the Plan: 

Left Drawer                       Right Drawer
64                                        0
32                                        32     #applying L
16                                        48     #applying L

Review: From above, it is clear that the implemented plan gave us the correct solution.  After applying the L operation twice, the right drawer ended up with 48 pennies, as we desired.  In addition, there doesn't appear to be a simpler way to solve this problem.