This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real numbers are specified as input. E.g., when it's stated that LDT has certain polynomial lower bounds, how are the real numbers specified when they are treated as input?
I disagree with your accepted answer by Kaveh. For linear programming and Nash equilibria, floating point may be acceptable. But floating point numbers and computational geometry mix very badly: the roundoff error invalidates the combinatorial assumptions of the algorithms, frequently causing them to crash. More specifically, a lot of computational geometry algorithms depend on primitive tests that check whether a given value is positive, negative, or zero. If that value is very close to zero and floating point roundoff causes it to have the wrong sign, bad things can happen.
Instead, inputs are often assumed to have integer coordinates, and intermediate results are often represented exactly, either as rational numbers with sufficiently high precision to avoid overflow or as algebraic numbers. Floating point approximations to these numbers may be used to speed up the computations, but only in situations where the numbers can be guaranteed to be far enough away from zero that the sign tests will give the right answers.
In most theoretical algorithms papers in computational geometry, this issue is sidestepped by assuming that the inputs are exact real numbers and that the primitives are exact tests of the signs of roots of low-degree polynomials in the input values. But if you are implementing geometric algorithms then this all becomes very important.
You might also have a look at Andrej Bauer's talk on The Role of the Interval Domain in Modern Exact Real Arithmetic, which surveys some of the different approaches to specifying computation over the real numbers both in theory and practice.
This is not a direct answer to your question, more of a response to Raphael. There has been quite some work recently specifying real number computations using coinduction. Here are some articles on the topic.
Coinduction for Exact Real Number Computation, Ulrich Berger and Tie Hou: THEORY OF COMPUTING SYSTEMS Volume 43, Numbers 3-4, 394-409, DOI: 10.1007/s00224-007-9017-6
Coinductive Formal Reasoning in Exact Real Arithmetic, Milad Niqui, Logical Methods in Computer Science, 4(3:6):1–40, 2008.
Calculus in Coinductive Form by Dusko Pavlovic and Martin Escardo, LICS 1998.
They hardly cover the full spectrum of real number computation, but progress is being made to chip away at various problems.
The computational complexity of computations over real numbers is considered by Blum, Cucker, Shub, and Smale. Here's a partial description of the book:
The classical theory of computation has its origins in the work of Goedel, Turing, Church, and Kleene and has been an extraordinarily successful framework for theoretical computer science. The thesis of this book, however, is that it provides an inadequate foundation for modern scientific computation where most of the algorithms are real number algorithms. The goal of this book is to develop a formal theory of computation which integrates major themes of the classical theory and which is more directly applicable to problems in mathematics, numerical analysis, and scientific computing. Along the way, the authors consider such fundamental problems as: Is the Mandelbrot set decidable? For simple quadratic maps, is the Julia set a halting set? What is the real complexity of Newton's method? Is there an algorithm for deciding the knapsack problem in a ploynomial number of steps? Is the Hilbert Nullstellensatz intractable? Is the problem of locating a real zero of a degree four polynomial intractable? Is linear programming tractable over the reals?
You may find a review of this book on ACM SIGACT News.
Edited/Corrected based on the comments
When authors talk about real number inputs in linear programming, Nash equilibrium computation, ... in most papers (papers which are not on the topic of computation/complexity over real numbers) they don't really mean real numbers. They are rational numbers and numbers that arise from them due to their manipulations (algebraic numbers). So you can think of them as represented by finite strings.
On the other hand, if the paper is on computability and complexity in analysis, then they are not using the usual model of computation, and there are various incompatible models of computation/complexity over real numbers.
If the paper does not specify a model of computation over real numbers, you can safely assume that it is the first case, i.e. they are just rational numbers.
Computational Geometry is different. In most papers in CG, if the authors does not specify what is the model which with respect to it the correctness and complexity of an algorithm is being discussed, it can be assumed to be the BSS (a.k.a. real-RAM) model.
The model is not realistic and therefore the implementation is not straight-forward. (This is one of the reasons that some people in CCA prefer Ko-Friedman/TTE/Domain theoretic models, but the problem with these models is that they are not as fast as floating-point computation in practice.) The correctness and complexity of the algorithm in the BSS model does not necessarily transfer to the correctness of the implemented algorithm.
Weihrauch's book contains a comparison between different models (Section 9.8). It is only three pages and worths reading.
(There is also a third way, which may be more suitable for CG, you may want to take a look at this paper:
Chee Yap, "Theory of Real Computation according to EGC"
where EGC is Exact Geometric Computation.)
They are not and they can not, in general. We can only treat a countable number of inputs (and outputs and functions) with our models of computation. In particular, any input has to be finite but not all real numbers have finite representations.
You could, I guess, assume some kind of oracle that yield the next digit of a certain real number upon request (sth like a stream). Otherwise you will have to live with (arbitrarily precise) approximations.