Re: Possreps and numeric types

On Mar 26, 1:40 pm, Bob Badour <bbad..._at_pei.sympatico.ca> wrote:

>

Sure.

However it does not follow from that that it is impossible to represent *any* number precisely.

We are perhaps speaking across each other with regards to the issue of the set-of-all-rationals, and specific rationals.

Let R(x) mean "x is exactly representable in a computer under   a given model M."
Let Q be the set of rational numbers.

Proposition A - there is some rational number that is not representable:
  exists x in Q: not R(x)

Proposition B - there are no rational numbers that are representable:   not exists x in Q: R(x)

Clearly B does not follow directly from A. B may be *true* but it is certainly not an implication of A.

I accept A. Proof:

{ x | R(x) } is a finite set, because a computer has a finite number of states. Q is an infinite set. Therefore we can conclude proposition A because of the pigeonhole principle.

I also claim proposition C - some rational numbers are representable:   exists x in Q: R(x)

Propositions A and C are consistent.

An alternative perspective:

Consider 32 bit numbers. Consider addition, subtraction, and multiplication defined over these numbers such that the result is the standard twos complement result, unless there is an overflow or underflow, in which case the result is a fault. (I believe that many CPUs support the necessary instructions to do this fairly cheaply, although few compilers take advantage of this fact.)

Any set of operations under the above system will do one of two things:

1. exactly model the behavior of the Integers
2. fault

Not every Integer is representable under the above system. But that's a necessary condition; there is *no* system possible which will represent all possible Integers.

Now, it is possible that one might attempt to solve some complex formula, and get a fault. If you get a fault, all bets are off, you really can't say anything about what happened. However, if you *don't* get a fault, you have a valid, precise result that faithfully models the arithmetic of the Integers.

This has some specific implications. For a simple example:

for all x, y, z in Z, evaluating the below equation

  (x+y)+z = x+(y+z)

will yield either true or fault. Under floating point arithmetic, that is not the case; associativity, perhaps the second simplest algebraic property in existence, does not hold.

Marshall

PS. In fact, even the above claim is too strong. Cosmic rays can cause CPUs to fail in ways they can't detect. So really no one ever knows anything absolutely. However I still feel that some systems are better than others. Received on Tue Mar 27 2007 - 02:28:35 CEST