Is there an algorithm to compute the degree of a polynomial? Let $f\in k[X]$ be a polynomial in one unknown over any field (or any nice enough commutative ring, I imagine - it shouldn't matter) and suppose that all we can do to understand $f$ is to evaluate it at any $x\in k$. Trivially, if $\deg f$ is known then so is $f$, for instance by finding the values of $f$ at $\{0,\dots,\deg f-1\}$ and taking successive differences. But what if $\deg f$ is unknown? The most obvious thing to do to try and compute successive differences at $\{0\},\{0,1\},\{0,1,2\},\dots$ and wait for a pattern to occur, but my preliminary intuition tells me that this does not necessarily work. In short, is it possible to compute $\deg f$ (and thus $f$) from evaluation at (finitely many) points?

No. If the field is finite, you can't reconstruct $f$ even by computing $f(x)$ for every $x \in \mathbb{K}$. There are only a finite number of functions from $\mathbb{K}$ to $\mathbb{K}$, but infinitely many polynomials. For example $x^3+x$ evaluates to $0$ for every $x\in\mathbb{Z}_2$.
If the field is infinite, and you evaluate on a finite set of points, there is a polynomial $p$ vanishing on the given set, so again you have no chance of identifying $f$. (If $f$ is a possible solution, then so is $f+p$.) 
Added: Curiously enough, if you have a polynomial in $\mathbb{Z}[x]$ and know that all the coefficients are positive, you can reconstruct $f$ by computing just two values. (Compute $f(1)$ to get a bound on the degree and the size of the coefficients, then compute $f(n)$ for a sufficiently large $n$ and read the coefficients off the base-$n$ expansion of $f(n)$. Fill in the details!) Even more cheating, compute $f(x)$ where $x$ is transcendental over $\mathbb{K}$.
