Subsection 1.3.6 Claims about Programs and Their Performance
The logical tools that we are about to study are the basis for reasoning about both the correctness and the performance of the programs that we write. So it’s critical that we be able to represent correctness and performance claims as logical statements.
Activity 1.3.11.
Consider the following simple program expressed in pseudocode:
def threen(value):
while value is not equal to 1 do:
if value is even then set value to value/2
else set value to 3 * value + 1
The program threen takes a positive integer as its input. Call it value. The program loops until value becomes 1. When that happens, it halts (stops). At each step, if value is even, it is divided by 2. If it’s odd, we multiply it by 3 and add 1.
It’s interesting to watch this program at work, particularly on large numbers. You can do so by going to:
http://www.nitrxgen.net/collatz.php
Now consider this claim about threen:
Given any positive integer as input, threen eventually halts.
Note that this is equivalent to saying that value eventually becomes 1.
The claim Item 1 is called the 3n+1 conjecture or the Collatz Conjecture. It is a logical statement. It is either true or false.
The interesting question is which. It is widely believed that [1] is true. No counterexamples have been found (and many have been tried). But no one has yet proved that threen will always halt.
Notice that we have just seen another example of a logical statement whose actual truth value we don’t happen to know (yet).
Problems 1.3.12.
(a)
Suppose that we invoke threen with the value 78. You can try it by going to:
http://www.nitrxgen.net/collatz.php
Step 1 will transform 78 into 39. The process will continue from there until it generates 1 and halts. How many total steps will it execute before it halts? ___
(b)
Consider the following simple program expressed in pseudocode:
def greedy(value):
while value is greater than 0:
if value is even:
value = value/2
else:
value = value - 1
Now consider this claim about greedy:
Given any positive integer as input, greedy eventually halts.
Note that [1] is equivalent to saying that value eventually becomes 0 or less.
Which of the following is true of [1]:
It is a true statement.
It is a false statement.
It is a statement but it’s not readily apparent whether it’s true or false.
It is not a statement.