(now long) Re: Tetrits and "stickiness"
OK folks,
Let me respond to Nate with an argument for what we need
in terms of state rather than bits. Then let's see how
many bits that takes up.
I'm making this up as I go along, folks. :-)
My original suggestion was to lock down the meaning of a
decoration by making explicit formulae for it.
Let's call the decoration name 'property'. Like 'inDomain'
or 'defined' or 'continuous' or 'bounded', 'property' is
something that we normally expect a function to possess
when we evaluate it. That is, most of the time we call f()
for most of the operands we would use with it, 'property'
is true.
More to the point, possessing 'property' is unremarkable.
There is no reason to remember the fact that f() evaluated
at x possessed 'property'. We expect it to happen normally.
The thing we want to know, the thing we want to remember,
the thing that we consider exceptional is when we find that
f(x) does NOT possess 'property'. Its something unusual,
something to worry about, perhaps something to prevent.
So, with this nomenclature, my original suggestion was to
compute the following two things:
'property' = {There exists x in xx such that f(x)
possesses 'property'} &
'notProperty' = {There exists x in xx such that f(x)
does NOT possess 'property'}.
Since all possible arrangements are possible, let's call
these 4 states FF, FT, TF, & TT, in that order ('property'
followed by 'notProperty'). Since my original note, the
meaning of these states has been written about several
times now, the most recent being Nate's description.
That was the original idea.
But we also need to make sticky the fact that bad things
happened in the run up to this computation. That is, we
want to remember any 'notProperty's that happened in the
past as well as any 'notProperty' that crops up during
this operation.
So let me make a new proposal.
Let me propose that we compute both 'property' & 'notProperty'
as before but that we REMEMBER 'property' & a new thing
called 'isOrWasNotProperty'. (OK, its a bad name. I know
that. We'll have a contest for a better name later. :-)
So now we compute:
'property' = {There exists x in xx such that f(x)
possesses 'property'} &
'notProperty' = {There exists x in xx such that f(x)
does NOT possess 'property'} &
'isOrWasNotProperty' = 'notProperty' or
'isOrWasNotProperty'(operand1) or
'isOrWasNotProperty'(operand2) (if needed).
And we remember only 'property' & 'isOrWasNotProperty'.
As before we have 4 possible states: FF, FT, TF, TT.
What could these 4 states mean for us now?
Well,
FF : There is no operand point that possesses 'property',
no operand point that does not possess 'property', & at no
time in the past has there been a function that contained
points which did not possess 'property' for those functions
either.
It seems to me that this still only happens with [empty]
but it may not be the only way [empty] can happen.
This is also the decoration that should accompany [empty]
intervals when they are created.
If we were on some sort of branch & bound search & we wanted
to eliminate [empty] intervals, this is the state we would
use to make that split.
FT: There is no operand point that possesses 'property' &
either there is an operand point that does not possess it
or there was one in the past for some previous function.
This means that the unusual or exceptional thing DID happen
WRT 'property' either here or in the past. Further this
state is sticky in that it can transform only into itself
or TT on future operations so we will always know that there
was a 'property' violation along this computation path.
This is the state that should accompany any entirely
'notProperty' possessing intervals when they are created.
In this state the computation is entirely outside the
region of 'property' possessing points so if we wanted to
branch & bound them away, this would be the way to do it.
TF: There is an operand point that possesses 'property',
none that do not possess it, & none in the past either.
This is the kind of normal state. This is the one we expect
all the time when nothing is going wrong. It is not at all
sticky but it IS expected to be the most common state.
This is the state that normal 'property' possessing intervals
should be initialized with when they are created.
If we want to branch & bound for good old wholesome 'property'
possessing places in this world, these are the ones to keep.
TT: There is an operand point that possesses 'property' &
either there is also a point that does not possess 'property'
or there was one in the past for some other function.
So the exceptional state happened here as well. This is also
a sticky state in that we will either remain in this state or
go to the FT state at some later date. So here again, the
fact that there was a 'property' violation along this path
is remembered all along the path.
This is the state that should be assigned to any intervals
with both 'property' possessing points & 'notProperty'
possessing points when they are created. (For example, for
the properties 'finite' or 'bounded' on semi-infinite
intervals.)
This is the branch & bound state that contains both 'property'
possessing points & 'notProperty' points. So this is something
to be split up to see if we can narrow things down a bit better.
How about that?
I think I just came up with a 4-state state machine that keeps
all things sticky we want to keep & still tells us all we need
to know about the world of 'property' in our calculation.
I WAS hoping I could get one of you guys to do this work but
there ya go.
So Nate wins in that we can do it in 2 bits. And I think the
rest of us win in that the definition is locked down as well
as the propagation rules.
Do I hear a motion to this effect? :-)
Yours in extremely pedantic expositions...
Dan
P.S. - We should still make that exception for selection
functions that says we only propagate the decorations of
the selected operand to the result.