2
$\begingroup$

In studying properties of polynomial functions I have read that they are computable. The usage of the word read implies that I cannot prove this statement, and withhold using learned for this reason. Additionally, I chose to ask this question here, as opposed to the cs exchange, since I am interested in the mathematicians' vantage point for this question.

Without further ado I would like to know how the polynomial functions can be shown to be computable. Moreover, I am also interested in how this property of polynomial functions helps the applied and computational mathematician in their endeavors.

In order that this question be deemed addressable it might be best to restrict the latter question to "favorite" usages of the polynomial functions being computable in applied and computational mathematics.

$\endgroup$
7
  • 1
    $\begingroup$ What is the definition of "computability" in this context? $\endgroup$ Feb 25, 2015 at 17:05
  • $\begingroup$ @Uncountable I am unsure of a good definition, which is why I avoided specifying one. Admittedly, that seems like a mistake. My hope was that someone would provide a "working" definition of computability, i.e. one used in applied and computational research, and then show that the polynomials are computable. $\endgroup$
    – sunspots
    Feb 25, 2015 at 17:10
  • 1
    $\begingroup$ The terms computability and polynomials are often combined in complexity theory. Maybe you are referring to this? en.wikipedia.org/wiki/Time_complexity#Polynomial_time Otherwise I'm sorry but I don't really understand the question. $\endgroup$ Feb 25, 2015 at 17:13
  • $\begingroup$ @Uncountable that was my surmise on what it meant for the polynomials to be computable. The wiki for polynomial functions just lists computable as a property, en.wikipedia.org/wiki/Polynomial and I was trying to understand what this meant. It should also be noted that no citation was given. This is in part why my question is so vague. $\endgroup$
    – sunspots
    Feb 25, 2015 at 17:17
  • $\begingroup$ Ah, I understand what you mean now. I'm not familiar with this concept, but from what I read just now on en.wikipedia.org/wiki/… is that for a function to be computable there must be a finite algorithm to compute it. In my interpretation computing now means "giving a $y$ by input of an $x$". For polynomials such an algorithm exists, since they are by definition finite, so the algorithm for a polynomial $P$ given by $P(x)=a_nx^n+\cdots+a_1x+a_0$ would consist of finitely many multiplications and additions. Does this help somehow? $\endgroup$ Feb 25, 2015 at 17:27

1 Answer 1

4
$\begingroup$

Actually, they're not.

Based on the Wikipedia article you linked, it looks like the polynomials in question are functions from $\mathbb{R}$ to $\mathbb{R}$. Such a function $f$ is computable if there is an oracle Turing machine that, when given $x \in \mathbb{R}$ as an oracle and $n$ as an input, produces the $n$-th digit of $f(x)$. Caveat: this definition is only essentially correct.

So if a polynomial has a non-computable real number as a coefficient, then it might not be a computable function. For example let $K$ be the real number corresponding to the halting set, so the $n$-th binary digit of $K$ is $1$ iff the $n$-th machine halts. Then the constant function $f(x)=K$ is not computable but is certainly a polynomial.

But if the polynomial has, for example, rational coefficients, then it is computable.

$\endgroup$

You must log in to answer this question.

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