Re: Amendment to property tracking
> Date: Thu, 02 Jun 2011 12:53:38 +0200
> From: =?ISO-8859-15?Q?J=FCrgen_Wolff_von_Gudenberg?= <wolff@xxxxxxxxxxxxxxxxxxxxxxxxxxx>
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: Amendment to property tracking
>
> Nate, Dan, all of you
>
> I think the decoration stuff needs further discussion
> Concerning the recent discussion by Nate & Dan
> I agree with Nate that the partial orderof the decorations has to match
> the linear order that leads the tracking process.
> Otherwise there is no FTDIA.
> Hopefully John and Arnold will find a consistent solution or proof the
> opposite.
>
> I also disagree with Dan that the definion of the predicates C D S is
> lower level stuff.
>
> Concerning the former statement
> I would like to raise the question:
> "Do we really need an FTDIA ?"
> or is an FTIA sufficient?
> Then, we would have do define how an algorithm can be performed on bare
> decoratiións. But that may be simpler
>
> Juergen
>
Juergen & all others,
Since having this discussion is the motivation for the
amendment, let me see if I can argue that these details do
not belong at level 1. Or, at the very least, that the
consequences of having these details at level 1 raises
difficulties for an FTDIA.
There is only one property that is required of an interval
arithmetic for FTIA. That is, that xx \subset yy implies
f(xx) \subset f(yy) for all xx, yy, & f in the arithmetic.
Similarly, there is only one property that is required of
a decorated interval arithmetic that is required for an
FTDIA. One must impose a partial ordering on the
decorations such that (to use Nate's total ordering) we
have that xx \subset yy implies BOTH f(xx) \subset f(yy)
AND decoration(f,xx) >= decoration(f,yy).
Now, how does the use of the bits D(f,X)+, D(f,X)-, & C(f,x)
together with the linear order D0 < D1 < D2 < D3 < D4 cause
problems with that property?
First, let me note that Nate defines two decorations in his
motion. One, S(f,X) which characterizes the decorations that
arise from the evaluation of f() itself over X (which one might
call a static decoration). And another, T(f,(X,D)) which,
according to definition 3, is the infimum of S(f,X) and the
decorations of all the inputs to f(). This may be called a
tracking decoration.
Now Nate does not say in so many words WHICH decoration he
would have us use in our decorated arithmetic which led to my
earlier confusion. But I must assume from his subsequent
remarks that he wishes the latter to be used.
But, no matter, let's see how both behave WRT a possible FTDIA.
Using examples as close to Nate's own as possible let us look
at xx = {[1,4],D3}, yy = {[-4,4],D3}, & f() = sqrt(). We have
f(xx) = {[1,2],D3}, D(f,xx) = D3, T(f,(xx,D)) = D3,
f(yy) = {[0,2],D1}, D(f,yy) = D1, T(f,(yy,D)) = D1.
Thus, no matter which property we label our results with we
have that xx \subset yy implies decoration(f,xx) >=
decoration(f,yy) & everything is hunky dory.
Now, let's change one element, xx to {[-3,-2],D3} & we have
f(xx) = {empty,D0}, D(f,xx) = D0, T(f,(xx,D)) = D0,
f(yy) = {[0,2],D1}, D(f,yy) = D1, T(f,(yy,D)) = D1.
But now we have xx \subset yy & yet decoration(f,xx) <
decoration(f,yy) & the one property we need to prove an FTDIA
is violated.
Now let's try a related example that brings in Nate's
definition 3. Let's try xx = {[1,4],D3}, yy = {[-4,4],D3},
& f(xx) = xx + sqrt(xx). We have
f(xx) = {[2,6],D3}, D(f,xx) = D3, T(f,(xx,D)) = D3,
f(yy) = {[-4,6],D1}, D(f,yy) = D1, T(f,(yy,D)) = D1.
And once again xx \subset yy implies decoration(f,xx) >=
decoration(f,yy) & we're sitting pretty.
But changing xx to {[-3,-2],D3} as we did before & we have
f(xx) = {empty,D0}, D(f,xx) = D0, T(f,(xx,D)) = D0,
f(yy) = {empty,D0}, D(f,yy) = D0, T(f,(yy,D)) = D0.
And either way we have xx \subset yy implies decoration(f,xx)
>= decoration(f,yy). This would seem to be a good thing.
But, paradoxically, by tracking the operands' decorations into
this result we have lost track of the previous violation of an
FTDIA.
So in what sense is this tracking anything?
All this because we (1) used the bits D(f,X)+, D(f,X)-, &
C(f,x) to (2) define a linear order D0 < D1 < D2 < D3 < D4, &,
more subtly, (3) allowed the tracking to take precedence over
decorations that make sense for this function.
(I say more subtly because, while this example does not
actually test that case, I believe it is a consequence of
Nate's definition 3. One might illustrate that by the function
f(xx) = xx \intersect sqrt(xx) but that requires a discussion
of the difference between tracking & static. And as that is not
the point of my amendment I do not want to confuse the argument
with that example.)
Since these (IMHO, unneeded) properties impose contradictions
on a decoration scheme that otherwise might be made consistent,
I believe those properties must be removed. Or changed.
In fairness, it would be sufficient to change the imposed linear
order from D0 < D1 < D2 < D3 < D4 to D1 < D0 < D2 < D3 < D4.
But this too is something imposed by a particular implementation
not by the level 1 properties needed for an FTDIA.
Well, that's my argument folks.
Make of it what you will.
Yours,
Dan