The technique of derived variables
comes up in analyzing state machines.
So let's just take a quick look at it together.
So a derived variable is simply a function
on the states of a state machine that assigns some value
to the states.
So it's just that kind of a function mapping.
If the values happen to be, say, the non-negative integers,
it's called non-negative integer value,
but it could be real value, complex value,
and even take on other kinds of odd kinds of values,
not necessarily numerical.
No pun there-- not odd numbers, but unusual values.
So let's look at the example of the robot on the grid.
The states were pairs of non-negative integers giving
the coordinates of where the robot was.
And one of the derived variables that we
found was real useful was the sum
value, sigma, of a state, which is defined to be x plus y.
And this would be a non-negative integer
valued derived variable.
So the word "derived" comes because we're making it up.
It's not part of the specification
of the state machine or part of the program that
defines the state machine.
So in the robot example, the actual states
were composed of the two coordinates x and y,
but the derived variable that we made up
was their sum of signal.
Another useful derived variable for that robot example
was the parity of sigma, whether or not
the number was even or odd.
So sigma is a 0, 1 valued variable,
which takes the value 0 if the sum is even
and 1 if the sum is odd.
So in the case of fast exponentiation,
we looked at the actual variable z,
which was part of the invariant and a crucial part
of the program.
And what we noticed about z was that z
was a strictly decreasing and natural number valued variable.
As a matter of fact, we noticed that it halved at each step.
But its values were non-negative integers,
and it's strictly decreasing at every step.
So that implies by the Well Ordering Principle
that it will take a minimum value.
And what we know about the minimum value of a strictly
decreasing variable is that the algorithm is stuck,
because once z has reached its minimum value,
if the machine took another step,
then it would get smaller.
So it means that the algorithm has to terminate.
So this gives you a general methodology
for proving termination-- find a non-negative integer valued
strictly decreasing variable guarantees the program stops.
As a matter of fact, we can say sometimes
how long it will take for the program to stop.
As we saw with fast exponentiation,
it took not z, which was the obvious bound,
but in fact, log of z, because z not only went down
at every step, it got halved at every step.
So in general, the concept of a strictly decreasing variable
is one-- as shown here-- that at every step of the state
machine, at each transition, it gets strictly smaller.
A related idea is a weakly decreasing variable.
These are not necessarily useful for proving termination,
but they are often useful, as you'll
see as we progress through the term-- examples
where it helps you analyze the behavior of the algorithm.
So a weakly decreasing variable is one which goes down
or stays constant.
It never gets larger.
So if we looked at the example of sigma,
the sum of the coordinates, that's
up and down all over the place.
It's neither increasing nor decreasing.
The other extreme is the parity variable
pi, which was the 0 or 1 according to whether
or not the sum of the coordinates was even or odd.
And pi is a constant, and that means
that it's both weakly increasing and weakly
decreasing in the degenerate sense
that weakly increasing is allowed to stay the same.
In fact, something is weakly increasing and weakly
decreasing if and only if it's a constant.
By the way, we used to call weakly decreasing variables
"non-increasing," which is the standard terminology
in the field.
In calculus, you talk about non-increasing functions.
And we just found that it caused a lot of confusion,
because you have to remember that non-increasing is not
the same as not increasing.
So there's an example of a function that
is not increasing, but it's certainly not non-increasing.
And if that didn't register, I'll let you think about it.
By the way, this method of proving termination
by finding a strictly decreasing natural number
valued variable generalizes straightforwardly
to a variable which takes on values from a well-ordered set
of real numbers.
Remember, a well-ordered set of real numbers,
one of the definitions of it is that it's
a set of numbers where it's impossible to find
an infinite decreasing sequence of values--
w0 less than w1 less than w2 less than w1 going on forever.
If that can't happen, then the set is called well ordered.
Of course, the non-negative integers
are the most obvious basic case, but there
are a bunch of others described in the notes.
And in general, the termination principle
is that if you can find a strictly decreasing
variable of derived variable whose values always come
from a well-ordered set, that also
is a way to prove termination.
That's going to guarantee termination for the same reason
that the variable will have to take a minimum value.
That's the other definition of well ordered.
And when it does, the machine can't move anymore.