3
$\begingroup$

Floating point numbers are not compatible with the usual theory of type 2 theory of effectivity (TTE), and not even the real-RAM model; there are functions that are computable in one model but not another. However, is there a way to generalize TTE as to yield floating point numbers as a special case? For example via some form of multi-representation?

One obstruction would be that in any floating number implementation, there are only finitely many numbers, so the "natural" topology on the "resultant reals" would be discrete. But the current reality from the programmer's point of view is that the reals can be manipulated as easily as the integers, and this perspective seems unlikely to yield to the treatment of reals as infinite objects in the near future. So perhaps a more robust theory of real computation should take this finiteness into account (perhaps sacrificing some elegance of combining topology with computation in TTE).

Otherwise, is there a current theory that accounts for the behavior of floating point reals better than the real-RAM model, for example by integrating numerical stability as well?

$\endgroup$
  • $\begingroup$ I think you need to be a little more specific about what you mean by "floating point number". For example, following the IEEE-754 definition, there are only finitely many floating point numbers which makes a lot of things trivial (for silly reasons). However, I suspect you mean something different. $\endgroup$ – François G. Dorais Sep 2 '15 at 3:42
  • $\begingroup$ That's exactly what I meant. My second paragraph explained that finiteness is an obstruction to the current usual theory of TTE, but I wonder if there is a generalization, for example some kind of topology based on complexity, that could account for the finiteness as well. $\endgroup$ – SorcererofDM Sep 2 '15 at 4:33
  • $\begingroup$ @SorcererofDM That theory is the IEEE-754 standard. I am not joking. Treating floating point arithmetic as "a real arithmetic + errors" is not correct, as the standard specifies how rounding is done, and that information is actually used. See, for example, the Kahan summation algorithm among many others. $\endgroup$ – Boris Bukh Sep 2 '15 at 14:54
  • $\begingroup$ I would be very interested in a good answer to this question. However, I do not know a lot of the relevant background, and questions in this general area are not common on Mathoverflow, so I suspect that few other people know the relevant background either. So I would encourage you to expand your question with further explanation. $\endgroup$ – Neil Strickland Sep 2 '15 at 15:38
3
$\begingroup$

Background: For those who don't know, TTE is two things: A type-two Turing machine a theoretical model of computation whose input and output is an infinite sequence of natural numbers. (Such a machine is "physically feasible" in that given a long enough initial segment of the input, the machine can build a long enough initial segment of the output.) Type-two effectivity is also a method, using Type-two Turing machines, to talk about computable functions from one topological space, i.e. the reals $\mathbb{R}$ to another. For many, TTE is synonymous with computable analysis. (The name TTE is due to Weihrauch, but the ideas of computable analysis are much older, even dating back to Turing and Brouwer, and standard in computability theory and constructive mathematics---especially for the real numbers.)

Basic facts of computable analysis:

  • Every way to representation a real in $\mathbb{R}$ induces a topology on $\mathbb{R}$.
  • The standard representation of a real $x$ is by a sequence of rational approximations $(q_0, q_1, ...)$ such that $x = \lim_n q_n$ and $|q_n - q_k| \leq 2^{-n}$ for all $k>n$. This induces the standard topology on $\mathbb {R}$.
  • Representing a real by its binary expansion (where 0.1111... and 1.000... are both acceptable ways to represent 1) induces a topology on the reals given by the subsist of intervals $[q,r]$ where $q<r$ are dyadic rationals.
  • Every computable function $f:\mathbb{R} \rightarrow \mathbb{R}$ (computable in the standard representation) is continuous (in the standard topology on $\mathbb{R}$.
  • In the binary representation, multiplying by $3$ is not computable since it is not continuous on the induced topology.

Why this question doesn't exactly make sense: First off, like the other commentators, I think there is a fundamental flaw in this question. Comparing TTE to floating point arithmetic is like comparing a Turing machine to a small pocket calculator or integrated circuit (i.e. some sort of finite state machine with a really small, fixed state size).

  • TTE and Turing machines are both idealized forms of computation. They are elegant, not practical to implement, unlimited in size, general, and best for exploring what is theoretically possible. They are also equivalent to a number of very different models.
  • A finite state machine and floating point arithmetic are messy in details, practical, limited in size, designed for a specific purpose, and best for real world applications. Also, they are designed to very specific specifications (of which I know little of the details).
  • A Turing machine can of course mimic any finite state machine. In the same way, TTE can represent floating point arithmetic as a discrete topological space with $2^{64}$ elements. All the floating-point operations are continuous functions on this space.
  • Also finite state machines can resemble true Turing machines. For example, a Macbook Air acts a lot like a true universal Turing machine. To a lesser degree a calculator or integrated circuit also looks like an approximation of a Turing machine. In the same way, floating point arithmetic looks (when viewed from a distance) like computation on the reals. (Arbitrary persuasion real numbers, even look more like computation on the reals.)
  • However, if a finite state machine is small it starts to differ a lot from a Turing machine. For example, it may be possible to loop over all the states in a reasonable amount of time, solving problems resembling the halting problem. By analogy, floating point arithmetic can represent functions which resemble discontinuous functions like $\mathtt{sign}(x)$.

A reformulation of the question: Now, as for the OP's question, I am going to modify the question slightly.

New question 1: If we increase the precision of floating point arithmetic to say 1 Terabyte floating point arithmetic (instead of $64$ bit), what topology on the reals does this resemble?

Equivalently,

New question 2: As the precision goes to infinity, what is the topology on $\mathbb{R}$ that we get in the limit?

Unfortunately, I don't know know much about floating point arithmetic, but I from a quick look at the Wikipedia article it seems that a floating point number is stored as a bit for the sign, the exponent, and the significant field (basically the binary representation of the significant digits).

Therefore, the answer to my new questions is that (infinite precision) floating point arithmetic induces the topology on the reals given by a subbasis given by all closed intervals $[q,r]$ where $q < r$ are positive dyadic rationals.

As for what functions are computable in this representation/topology, notice that multiplying by 3 is not computable (at least for certain inputs). Calculating the sign would also not be computable because of $0$. Similarly, equality testing would not be computable either since one would have to look at two infinite bit sequences to decide if they are the same.

Now returning to the case of just large precision, say 1 terabyte (in place of 64 bits), notice that equality testing would be ridiculously difficult having to read a whole Terabyte of information. The same goes for multiplying by 3 (at least for certain inputs like $0.111...\pm \varepsilon$ in binary.) Indeed there seams to be some (very loose) correlation to the operations that are computable on the ideal infinite representation and those that are easy to do in the 1 terabyte case. However, this also gets into a lot of issues with what is "easy". (For example, adding 1 could even be hard if one has to copy over every bit into the new number.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.