5
$\begingroup$

From Wikipedia

computers can directly evaluate polynomials

What precisely does direct evaluation mean? As far as I know, function evaluation can be difficult in complexity theory.

I was wondering if polynomials are the only functions that computers can evaluate directly? Thanks and regards!

  • 1
    I suppose "direct evaluation" is just a matter of plugging in the value and using addition/multiplication to get the result. For example, "calculating" $\sqrt{2}$ doesn't work like that.2012-12-31
  • 0
    If a function is recursive, so Turing computable, in what sense would its value not be "directly" evaluable by following the steps in the Turing program??2012-12-31
  • 0
    @PeterSmith: I am not sure. But for example, is $f(x)=\sqrt{x}, x \in \mathbb{N}$ recursive and therefore directly evaluable?2012-12-31
  • 1
    Which function? The partial sqrt function from $\mathbb{N}$ to $\mathbb{N}$ is recursive; the totalsqrt function from $\mathbb{R}^+$ to $\mathbb{R}^+$ isn't.2012-12-31
  • 0
    Thanks, @PeterSmith! It can be both cases in your comment.2012-12-31

2 Answers 2