makeMeStop

makeMeStop

Here is a simple algorithm.

Given a number x, do the following:

If x is 1, stop
If x is even, divide it by two.
If x is odd, mutliply x by three and then add one.

You can program this in squeak:
Take an ellipse (say), create a variable called "x".
Create a script called "makeMeStop" as follows

TEST  x = 1
     YES stop script makeMeStop
     NO  TEST   x isDivisbleBy 2
                    YES x multiply by 0.5
                     NO x multiply by 3.0
                          x increase by 1

If you want, drag out a detailed watcher for x

Now, set a value of x, and start the script ticking.
The value of x changes according to the rule. If it is even, it gets cut in half. If it is 1, the script stops. So, if x is a power of 2 (like 256), then it will halt quickly. Example: successive values after 256 are 128, 64, 32, 16, 8, 4, 2, 1 halt.

If x is not divisible by 2, it turns into 3x+1. Sometimes this makes it into a power of 2 and then the above paragraph applies. So 5 turns into 16, then 8,4,2,1. Some inputs of x cause x to cycle through a much longer sequence of numbers. Experiment: How many different numbers happen when you give a an input x? Which inputs x make it take longer? You can actually program this by creating a new variable "count" that you set to 0 when you set x before running the script. Then, add the line "count increaseby 1" OUTSIDE of the main test, just after it, or just before it. If x starts off as a power of 2 (like 256 which is 2 to the 8th power, or 2x2x2x2x2x2x2x2, then count will end up at 9 (I'd rather it be 8... and it would in most programming languages... but each script here must finish all the way through because of how etoys works). Computing the number of times you need to mulitply 2 by itself to get x is called the logarithm (base 2) of x.
So, "count" is computing a logarithm, but is off by 1.

Actually, count only computes a logarithm if x is a power of two.

THE BIG QUESTION: Is there an input which will make "count" go up forever? That is, we've seen that if x is a power of two, the algorithm makeMeStop will keep halving x until it hits one, and then stop. But if x is some other number, can the process of multiplying by three and adding one, or halving, etc., go on forever??

NOBODY KNOWS THE ANSWER!

Although people have tried, and/or peopel have proven through other means, that if x is not more than some very very large number (billions & billions) it is guaranteed to halt, nobody can prove that regardless of the input, it is guaranteed to halt, even though we expect that to be true.

You might wonder how we could prove something would work regardless of the input x. In math, it is common to prove things are true for all numbers. Such proofs don't require separately proving a property for each number separately, but doing it all at once in general (which is why math is powerful). But reasoning about simple algorithms does not yield even to powerful mathematics. In this case, there may ultimately be an answer. But some problems are known not to be solvable - that is, we've proved there is no way we'll ever know for sure. This may or not be one of those cases.

Finally, you might ask whether this particular problem is important. I think not - as it doesn't have any application or tie-in with other mathematics that I know of. But it is a lovely and simple example of our limitations, and of the difficult of understanding and predicting behavior that arises from simple rules.

Link to this Page

Pedagogy Place last edited on 30 March 2005 at 5:19:17 pm by csil-cbt6.cs.uiuc.edu