If I understand correctly, the idea is that you can never have a sign function that is 100% accurate because there’s no way to measure whether something really close to 0 is actually above or below it? In other words, any measurement of 0 is really 0 ± x, where x is your level of precision.
Well, yes. But I only need one discontinuity. If it’s easier, we can consider a version of Sign, call it Sign2(x), which returns -1 for negative argument, and +1 for zero or positive.
Don’t most representations actually in use have an “is this negative or not” field? Since I was initially responding to Hari Seldomn’s comment that “every function that can be calculated by a computer is automatically continuous”, saying that I can’t use the representations actually in use by computers to question that statement doesn’t seem reasonable.
I don’t think this is what Indistinguishable means*, but I’ll respond anyway that if you have a true value T, but you measure it as M and assign that to a variable v = M, when you calculate Sign(v) (or sign2(v) ), it should give you Sign(M), not Sign(T). From the point of view of Sign(x) it doesn’t matter that there’s an error in your measurement. It takes whatever value you give it as correct.
- I think he was instead arguing that representations with a sign bit are flawed, for the reason you gave. The problem with Sign(x) is more of a symptom.
It also can’t be calculated since it is generally undecidable whether a number is positive negative or 0. Suppose, for example, I describe a number by giving you its decimal expansion, one at a time. The first google of digits are 0. You still don’t know if they all are. You might say that I can tell it isn’t negative because once I start with 0, it cannot go negative. Point taken but the problem is that decimals (or binary) digits are not the only way to present a number. You might use trits, with numerals 0, 1, and -1 or just present it as a sequence of rational approximations.
Yes, but most computer representations of numbers actually in pragmatic use describe a finite, discrete domain, on which all functions are continuous (e.g., 32 bit signed integers, or 80 bit IEEE floating point, or what have you). The sign function you calculate on those is a continuous function (after all, it’s just the same as the restriction of the general continuous function defined piecewise by “I’m -1 on values less than -epsilon, I’m X/epsilon on values from -epsilon to epsilon, and I’m 1 on values above epsilon”, where epsilon is the smallest nonzero magnitude). So Hari’s statement would still be true for those; Sign is not a discontinuous function, if you restrict its domain as such.
But if you really want to capture the mathematical essence of the standard definitions of the real numbers, using representations analogous to the definitions of the reals as Cauchy sequences or Dedekind cuts of rationals, you can, but you will end up with representations for which only continuous functions are computable. Consider, as Hari just implored you to and as I was getting at with the Halting Problem business, the task of constructing a value in [0, 1] from a digit-sequence, and then determining whether this is 0 or positive. Either your representation will be such that you cannot compute the function mapping digit-sequences to numbers, or your representation will be such that you cannot compute the Sign of real numbers. You can pick your poison, but analysis is a lot nicer if you pick the latter…
But if you’re constructing a value in [-1, 1], and determining whether this is negative or not, this is easy. Just look at the sign bit.
If you use a sign bit “Negative or non-negative”, then you once again must fail to be able to construct values from digit-sequences Consider constructing a value -0.abcdefgh… from the digit sequence abcdefgh… Determining whether to set the negative bit or not amounts to determining whether this sequence ever goes non-zero or not.
(Now, in something like IEEE floating point, there’s a sign bit which distinguishes between +0 and -0. But if you have separate +0 and -0, then, again, it’s like there’s a discrete gap between the two, and a sign function which sends +0 to 1 with all the other positives and -0 to -1 with all the other negatives will be perfectly continuous on the relevant topology.)
Require inputs to be well-formed, meaning no -0.00000… no 0.1111…, so each number has a unique bit-sequence.
Then it becomes impossible to carry out summations… If the sequence that’s coming in looks like a bunch of 1s (perhaps that’s the result you naturally got from adding 0.10101010… to 0.0101010101…), how do you know “Oh, I shouldn’t represent this as 0.1111…, I should represent this as 1.00000…”? You can’t know that until you’re sure the sequence that’s coming is all 1s, which you’ll never know in finite time.
These are all well-studied issues. Sign bits, unique decimal representations, and the like really aren’t very good ways of representing real-arithmetic, and we know better ones. The ones that are any good don’t let us compute discontinuous functions, but the ones that do let us compute continuous functions have worse problems.
Perhaps the point is best put another way: to any computer datatype, there is a natural associated topology (this is the idea of domain theory), and all computable functions are continuous with respect to these topologies.
You pick the computer datatype you like, and I’ll tell you the associated topology.
You can pick datatypes which, viewed as topological spaces, are like the real numbers equipped with some topological structure dissimilar to the standard one, and these will let you compute functions which would not be continuous with respect to the standard topology. But all the same reasons we are motivated to use the standard topology in ordinary mathematics will also lead us to want, for most purposes, those datatypes which lead to that topology.
If it’s taking an infinite time to do your summation, then you can’t ever do summation. It’s not because you’re requiring the representation to be well-formed.
You can do infinite-time summation, taking input and producing output piece by piece (in the same way as, say, Haskell’s handling of infinite lists), or in an on-demand fashion (like any language’s handling of infinite sequences of Xes via the type “Functions from naturals to Xes”). That’s what people usually mean by exact real arithmetic: computations which produce an infinite stream describing the result.
For example, here’s a Haskell program that will carry out that addition of 0.101010101… to 0.01010101…
summand1 = cycle [1, 0]
summand2 = cycle [0, 1]
sum = zipWith (+) summand1 summand2
Feed that into a Haskell interpreter, ask it to output “sum”, and watch as the infinite stream of 1s comes raining down.
Now, there is a natural constraint on the manipulation of infinite data in such stream computation: each finite chunk of the output stream can only depend on finitely much of the input stream. Which is basically the definition of epsilon-delta definition of continuity, as Hari pointed out. That’s the reason why computable functions have to be continuous.
This isn’t some deluded fantasy. There are actually libraries for exact real arithmetic out there, should you want to play around with them. For example, here’s one, and here’s another. Here’s a nice writeup from a student who implemented an exact real number calculator. Here’s a good introduction to the idea from a luminary of the field, so you don’t have to keep listening to me babbling. It’s easy to pull up a near infinite-stream of work on exact real-number computation.
Er, you know what I meant to say…