4
$\begingroup$

To unify the numerical computation and classic computability theory, or to pave a foundation for the numerical computation, mathematicians present variant computation model and computational complexity over reals, for example, the one in the book by Blum,Cucker,Shub, and Smale, or the one in Weihrauch's book Computable Analysis. mathematicians on such topics usually give the definition from their own view, and as far as I know, they usually do not compare their model with others. But we know, if they give a suitable model, eventually those variant model will be proven to be equivalent, as what had happened to the classic models.

So, first, let's give a list of computation model and computational complexity over reals.

Second, are they equivalents? Any proof for their equivalence?

Obviously, the suitable models have to include the classic computation models as special case, and possibly,the computational complexity have to be consistent with the classic ones. As a special case, computable numbers ,especially computable irrational algebraic and transcendental ones have to have uniform or consistent definition over classic model and the computational complexity.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The following models are probably the two most well known, and they are not equivalent at the level of computability.

  1. BCSS
  2. standard/Grzegorczyk (same as in Weihrauch's book)

In fact, the function $$x\mapsto e^x$$ is computable in the standard model, but not in the BCSS model as it is not "semi-algebraic" in a sense.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you very much for you answer, Bjørn, you always give me helpful answer. Yes, so I suspect that BCSS model has not capture all we intend to capture. But the authors say their model is natural, and they even give some results of their model based on descriptive complexity which is independent of classic model. To tell the truth, I am afraid that BCSS model is not the suitable one. $\endgroup$
    – XL _At_Here_There
    Commented Nov 5, 2014 at 1:25
  • 1
    $\begingroup$ Okay, the last sentence of your answer has solves the problem about suitability, I am preemptied with sentence on the equivalence problem $\endgroup$
    – XL _At_Here_There
    Commented Nov 5, 2014 at 1:36
  • 2
    $\begingroup$ Just to justify why it could be natural that exponentiation is computable classically but not in BCSS: BCSS does exact computations, while classical computability is about computable approximation. $e^x$ can certainly be approximated by BCSS machines, eg via the Taylor series. $\endgroup$
    – Kevin Carlson
    Commented Nov 12, 2014 at 19:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .