Real-number model—pros and cons

  11 What are the advantages of the real-number model? Be­cause physicists generally assume a continuum, their mathematical models are often continuous, employing the domain of the real (and complex) numbers. It seems natural, therefore, to use the real numbers in analyzing the numerical solution of continuous models on a digital computer.

12 If we leave aside the possibility of numerical insta­bility, computational complexity in the real-number model is the same as it is for fixed-precision, floating-point arithmetic. Therefore the real-number model is predictive of running times for scientific computations. Studying computational complexity in the real-number model has led to new, superior methods for doing a variety of scien­tific calculations.

13 Another reason for using the real-number model is that it makes available the full power of continuous mathematics. I give an example below, when I discuss a result on non-computable numbers and its possible impli­cations for physical theories. With the real-number model and the techniques of analy­sis (that is to say, the mathematics of continuous functions), this result is established in about a page. With the Turing-machine model, by contrast, the proof requires a substantial part of a monograph.

14 The argument for using the power of analysis was already made in 1948 by John von Neumann, one of the leading mathematical physicists of the century and a father of the digital computer. In his Hixon Symposium lecture, von Neumann argued for a "more specifically analytical theory of automata and of information." He said: “There exists today a very elaborate system of formal logic, and specifically, of logic as applied to mathematics. This is a discipline with many good sides, but also serious weaknesses.... Everybody who has worked in formal logic will confirm that this is one of the technically most refractory parts of mathematics. The reason for this is that it deals with rigid, all-or-none con­cepts, and has very little contact with the con­tinuous concept of the real or of the complex number, that is, with mathematical analysis. Yet analysis is the technically most successful and best-elaborated part of mathematics.... 15 The theory of automata, of the digital, all-or-none type as discussed up to now, is certainly a chap­ter in formal logic.”

We may adopt these observations, mutatis mutandis, as an argument for the real-number model. Recently, Blum and coauthors have argued for the real-number model, asserting that "the Turing model... is fundamentally inadequate for giving... a foundation to the theory of modern scientific computation, where most of the algo­rithms... are real-number algorithms."

16 Against the real-number model, one can point out that digital representations of real numbers do not exist in the real world. Even a single irrational real number is an infinite, nonrepeating decimal that requires infinite resources to represent exactly. We say that the real-num­ber model is not finitistic. But neither is the Turing-ma­chine model, because it utilizes an unbounded tape. It is therefore potentially infinite. Nevertheless, the Turing-machine model, because it is unbounded but discrete, is less infinite than the real-number model. It would be attractive to have a finite model of computation. There are finite models, such as circuit models and linear bounded automata, but they are only for special-purpose computation.

Information-based complexit

17 To see the real-number model in action, I indicate below how to formalize computational complexity issues for con­tinuous mathematical problems and then describe a few recent results. To motivate the concepts, I choose the example of d-dimensional integration, because of its im­portance in fields ranging from physics to finance. I will touch briefly on the case d = oo, that is to say, path integrals.

18   Suppose we want to compute the integral of a real-valued function f of d variables over the unit cube in d dimensions. Typically, we have to settle for com­puting a numerical approximation with some error ε < 1. To guarantee an ε-approximation, we need some global information about the integrand. We assume, for example, that this class of integrands has smoothness r. One way of defining such a class is to let Fr be the class of those functions whose derivatives, up through order r, are uni­formly bounded.

19 A real function of a real variable cannot be entered into a digital computer. Therefore, we evaluate the func­tion at a finite number of points, calling that set of values "the information" about f. An algorithm then combines these function values into a number that approximates the integral.

20 In the worst case, we guarantee an error of at most εfor every f in F_r. The computational complexity is the least cost of computing the integral to within e for every such f. We charge one unit for every arithmetic operation and comparison, and с units for every function evaluation. Typically, с» 1. I want to stress that the complexity depends on the problem and onε, but not on the algorithm. Every possible algorithm, whether or not it is known, and all possible points at which the integrand is evaluated, are permitted to compete when we consider the least cost.

Nikolai Bakhvalov showed in 1959 that the complex­ity of our integration problem is of order ε^-d/r. For r = 0, with no continuous derivatives, the complexity is infinite; that is to say, it is impossible to solve the problem to withinε. But even for any positive r, the complexity increases exponentially with d, and we say that the problem is "computationally intractable."