Ada.Strings.Bounded
in [ADA]
|
From: Eric Hughes on 14 Apr 2008 22:07 On Apr 14, 12:52 pm, "Dmitry A. Kazakov" <mail...(a)dmitry-kazakov.de> wrote: > I think it is wrong to consider N and universal_integer equivalent. Sure. It's {\bb Z} and universal_integer that are equivalent. Seriously, we just disagree about this. I can't take universal_integer seriously as a root class, because it's impossible to write down any representation of it. I believe the approach I've been thinking about could provide some reasonably solid grounding for what universal integer is. > Subseting is not a sufficient condition for a > successful modeling. In a discussion that's got a lot of formal logic in it, the word "model" already means something pretty specific, usually involving a Tarski structure. On the other hand, the informal use of the word "model", in this context, is basically beside the point, which is to get a precise definition of a hypothetical universal real type, amongst others. There are plenty of useful things that are not-quite- real numbers, such as the one- and two-point compactifications of the real line, but these are the same thing as real numbers. If you want them, fine; just don't try to claim that they are same thing and use a confusing name for them. > Actually it is the opposite, a perfect subset cannot > be a good model. There was paper from the fifties (sorry, no reference handy), which used Turing machines to compute a Dedekind cut. On input a rational number, it returned one of the two symbols "<=x" or ">=x". (You cannot compute exact trichotomy without solving the halting problem.) In any language describing these machines, there's a least one (Kleene minimization), so there's a unique representative of such a machine for every computable real number, which means there's a subset bijection. Addition, multiplication, and their inverses are defined in terms of the underlying operand-machine (it's pretty easy coding, actually). So there's pretty close to a perfect model of the real numbers, whose only real limitation is that run times are horrendously slow. But it's also completely exact, with no compromises but execution speed and representation size of a machine. The subset is every real number that's computable. About as good as you can do with computers, I'd say. > The best models of R aren't even close to subsets. For > example intervals with rational bounds. In the precise meaning of model, it's just not a model, because there's no total ordering on such intervals, so the ordering axioms are not satisfied. In an imprecise meaning, it's real numbers plus some other concept, which is more than {\bb R}. Eric
From: Dmitry A. Kazakov on 15 Apr 2008 04:02 On Mon, 14 Apr 2008 19:07:25 -0700 (PDT), Eric Hughes wrote: > On Apr 14, 12:52 pm, "Dmitry A. Kazakov" <mail...(a)dmitry-kazakov.de> > wrote: >> I think it is wrong to consider N and universal_integer equivalent. > > Sure. It's {\bb Z} and universal_integer that are equivalent. > > Seriously, we just disagree about this. I can't take > universal_integer seriously as a root class, because it's impossible > to write down any representation of it. Yes, because it is not what you wanted it be. >> Subseting is not a sufficient condition for a >> successful modeling. > > In a discussion that's got a lot of formal logic in it, the word > "model" already means something pretty specific, usually involving a > Tarski structure. That is beside the point. A subset of values is not yet a type. The requirement to be a subset (of values) alone does not enforce anything useful. >> Actually it is the opposite, a perfect subset cannot >> be a good model. > > There was paper from the fifties (sorry, no reference handy), which > used Turing machines to compute a Dedekind cut. On input a rational > number, it returned one of the two symbols "<=x" or ">=x". (You > cannot compute exact trichotomy without solving the halting problem.) > In any language describing these machines, there's a least one (Kleene > minimization), so there's a unique representative of such a machine > for every computable real number, which means there's a subset > bijection. Addition, multiplication, and their inverses are defined > in terms of the underlying operand-machine (it's pretty easy coding, > actually). So there's pretty close to a perfect model of the real > numbers, whose only real limitation is that run times are horrendously > slow. But it's also completely exact, with no compromises but > execution speed and representation size of a machine. > > The subset is every real number that's computable. About as good as > you can do with computers, I'd say. No. It cannot represent pi and e. Now consider the following: type A_Subset_Of_R is (pi, e); -- Ready! The above is a perfect subset of R containing both pi and e. Isn't it good? >> The best models of R aren't even close to subsets. For >> example intervals with rational bounds. > > In the precise meaning of model, it's just not a model, because > there's no total ordering on such intervals, so the ordering axioms > are not satisfied. In an imprecise meaning, it's real numbers plus > some other concept, which is more than {\bb R}. For any model there are properties which are not satisfied. Intervals are good because they preserve *interesting* properties and provide fair approximations for properties lost. Total ordering is mere a property, which has a minor importance to numeric computations. In fact, each second handbook on numeric methods starts with something like "never ever compare reals." -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Eric Hughes on 15 Apr 2008 09:56 On Mon, 14 Apr 2008 19:07:25 -0700 (PDT), Eric Hughes wrote: > Seriously, we just disagree about this. I can't take > universal_integer seriously as a root class, because it's impossible > to write down any representation of it. On Apr 15, 2:02 am, "Dmitry A. Kazakov" <mail...(a)dmitry-kazakov.de> wrote: > Yes, because it is not what you wanted it be. I assert that that Ada as currently defined has no bound on the size of numbers within universal_integer. Here is my argument. The best definition is in ARM 3.4.1(6/2-7). (Defect report: this doesn't appear in the index entry for universal_integer.) Wherein: > The set of values of a universal type is the undiscriminated > union of the set of values possible for any definable type > in the associated class. The associated class to universal_integer is the signed integer type (3.5.4), delineated by ranges given by static simple_expression. Simple expressions allow for exponentiation, so it's quite easy to define ranges that take petabytes to implement. There's no length limitation on an expression in the language, so arbitrarily large ranges are possible. Thus I can define the following series of types: > > >> Subseting is not a sufficient condition for a > >> successful modeling. > > > In a discussion that's got a lot of formal logic in it, the word > > "model" already means something pretty specific, usually involving a > > Tarski structure. > > That is beside the point. A subset of values is not yet a type. The > requirement to be a subset (of values) alone does not enforce anything > useful. > > > > >> Actually it is the opposite, a perfect subset cannot > >> be a good model. > > > There was paper from the fifties (sorry, no reference handy), which > > used Turing machines to compute a Dedekind cut. On input a rational > > number, it returned one of the two symbols "<=x" or ">=x". (You > > cannot compute exact trichotomy without solving the halting problem.) > > In any language describing these machines, there's a least one (Kleene > > minimization), so there's a unique representative of such a machine > > for every computable real number, which means there's a subset > > bijection. Addition, multiplication, and their inverses are defined > > in terms of the underlying operand-machine (it's pretty easy coding, > > actually). So there's pretty close to a perfect model of the real > > numbers, whose only real limitation is that run times are horrendously > > slow. But it's also completely exact, with no compromises but > > execution speed and representation size of a machine. > > > The subset is every real number that's computable. About as good as > > you can do with computers, I'd say. > > No. It cannot represent pi and e. Now consider the following: > > type A_Subset_Of_R is (pi, e); -- Ready! > > The above is a perfect subset of R containing both pi and e. Isn't it good? > > >> The best models of R aren't even close to subsets. For > >> example intervals with rational bounds. > > > In the precise meaning of model, it's just not a model, because > > there's no total ordering on such intervals, so the ordering axioms > > are not satisfied. In an imprecise meaning, it's real numbers plus > > some other concept, which is more than {\bb R}. > > For any model there are properties which are not satisfied. Intervals are > good because they preserve *interesting* properties and provide fair > approximations for properties lost. Total ordering is mere a property, > which has a minor importance to numeric computations. In fact, each second > handbook on numeric methods starts with something like "never ever compare > reals." > > -- > Regards, > Dmitry A. Kazakovhttp://www.dmitry-kazakov.de
From: Eric Hughes on 15 Apr 2008 10:20 On Mon, 14 Apr 2008 19:07:25 -0700 (PDT), Eric Hughes wrote: > Seriously, we just disagree about this. I can't take > universal_integer seriously as a root class, because it's impossible > to write down any representation of it. On Apr 15, 2:02 am, "Dmitry A. Kazakov" <mail...(a)dmitry-kazakov.de> wrote: > Yes, because it is not what you wanted it be. My belief about universal_integer is rooted in the language definition. I assert that that Ada as currently defined has no bound on the size of numbers within universal_integer. Here is my argument. The best definition is in ARM 3.4.1(6/2-7). (Defect report: this doesn't appear in the index entry for universal_integer.) Wherein: > The set of values of a universal type is the undiscriminated > union of the set of values possible for any definable type > in the associated class. The associated class to universal_integer is the signed integer type (3.5.4), delineated by ranges given by static simple_expression. There's no length limitation on an expression in the language, so arbitrarily large ranges are possible. Thus I can define the following series of types: type I1 is range -2^10 .. 2^10 ; type I2 is range -2^100 .. 2^100 ; type I3 is range -2^1000 .. 2^1000 ; -- ... The exponent in I(n) is an integer within the range of I(n-1). The type of an integer literal is universal_integer (2.4), which means that if I(n-1) is well-defined, then so is I(n). (Hence the requirement for bignum arithmetic in the compiler.) If you want to exhibit a bound on universal_integer as a counterexample, I will take its logarithm, round up, and add 1, and use that index to exhibit a type definition that exceeds this bound. Every integer is thus a member of universal_integer. If you can show me a Ada definition that can store a universal_integer, only then will I believe you that it's the kind of type that's just like an ordinary Ada type. Perhaps you could explain what you want universal_integer to be. Eric
From: Dmitry A. Kazakov on 15 Apr 2008 10:58
On Tue, 15 Apr 2008 06:56:57 -0700 (PDT), Eric Hughes wrote: > On Mon, 14 Apr 2008 19:07:25 -0700 (PDT), Eric Hughes wrote: >> Seriously, we just disagree about this. I can't take >> universal_integer seriously as a root class, because it's impossible >> to write down any representation of it. > > On Apr 15, 2:02 am, "Dmitry A. Kazakov" <mail...(a)dmitry-kazakov.de> > wrote: >> Yes, because it is not what you wanted it be. > > I assert that that Ada as currently defined has no bound on the size > of numbers within universal_integer. It specifies the lower bound and leaves the upper bound up to the vendor. Which by no means imply that there were no upper bound. In any given instance of Ada compiler universal_integer has an upper bound. Moreover, because the number of all instances of all existed, existing and future Ada compilers is obviously finite, there also exists the upper bound of universal_integer as a whole. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de |