A model for computation over the reals \({\mathbb{R}}\) (or an arbitrary ordered ring \({\mathcal R})\) is presented. A machine over \({\mathcal R}\) is a digraph with two kinds of nodes: computation (fan-out 1) nodes labelled by polynomial maps \({\mathfrak g}: {\mathcal R}^ n\to {\mathcal R}^ n\), and branching (fan-out 2) nodes labelled by tests ``\({\mathfrak h}(x)\geq 0''\) where \({\mathfrak h}: {\mathcal R}^ n\to {\mathcal R}\) are polynomials. The concepts of universal machine, recursive function and NP-completeness are introduced for such a model of machines. The theory obtained reflects the classical one over \({\mathbb{Z}}\), and captures the special mathematical character of the underlying ring \({\mathcal R}\). Specifically, it is shown that complements of Julia sets (a concept from dynamic system theory) provide natural examples of undecidable sets over the reals. An analogue of Cook's NP-completeness theorem over the reals is also proved, and the 4-feasibility problem (i.e. the problem of deciding whether or not a real degree 4 polynomial has a zero) is shown to be NP-complete over \({\mathbb{R}}\). The paper is almost self-contained and provides a natural setting for the theory of algorithms and complexity in numerical analysis.