Variety defined by a recursively enumerable set of polynomials Suppose we have a recursively enumerable set of polynomials $\mathcal{P}=\{ p_1({\bf x}), p_2({\bf x}), \ldots\}, p_i \in \mathbb{Z}[{\bf x}], {\bf x} = (x_1, \ldots, x_n)$. Let $V(\mathcal{P})$ denote the affine variety in $\mathbb{C}^n$ defined by $\mathcal{P}$. Is there an algorithm to compute $V(\mathcal{P})$? By the Nullstellensatz, we know that we need only use finitely many of the polynomials $p_i$ to cut out $V(\mathcal{P})$. We can recursively compute varieties cut out by $\{p_1, \ldots, p_k\}$, for example by computing a Grobner basis for the radical ideal of $(p_1,\ldots,p_k)$. But is there a way to compute $k$ such that $V(\mathcal{P})=V(p_1,\ldots,p_k)$? 
Please let me know if this question needs clarification or if I'm not using the correct notation. 
Addendum: This problem was motivated by this MO question. It would follow from:
If one has a finitely generated group $G$ with solvable word problem, for any $n$ can one compute the representation variety $G\to SL_n(\mathbb{C})$? 
I view $G$ as being given as the homomorphic image of a free group $\\langle g_1,\ldots,g_k\\rangle$. Moreover, there is a Turing machine which takes as input any element $h\in \\langle g_1,\ldots,g_k\\rangle$ and tells if $h$ is trivial in $G$. The space of representations  $\rho:G\to SL_n(\mathbb{C})$ is an affine variety, with $kn^2$ variables given by the entries of the matrices of $\rho(g_i)$. One can recursively generate polynomials 
which are the entries of the matrices $\rho(h)-I$ which cut out the representation variety (together with $det(\rho(g_i))-1$). So the algorithm should depend on how these polynomials are generated, if one wants to be able to compute the representation variety for each $n$. 
I suspect that the answer is no, although I'm not sure how to generalize Borcherds or Groves' answers to this context.  
If one could compute the representation variety, then one could determine if $G$ has a homomorphism to a finite group. 
 A: There cannot be such an algorithm.  Suppose that there were and call the algorithm $A$.  Let $\mathcal P$ be a sequence which has a nonempty set $V(\mathcal P)$, and suppose that 
$V(\mathcal P) = V(\{p_1, \ldots , p_k\})$.  Feed $\mathcal P$ to $A$ and look at what happens.  $A$ decides that $k$ suffices on the basis of reading a finite number of polynomials, say up to $p_j$.  Now, $j$ may be much bigger than $k$, and I'll assume that $j \ge k$.  Now make a sequence $\mathcal P'$, which is the same as $\mathcal P$ except that $p_{j+1} = 1$.  Then $V(\mathcal P') = \emptyset$, but $A$ won't discover this and will output that for $\mathcal P'$ the number $k$ suffices.  But it doesn't, since for $\mathcal P'$ we need to go to $j+1$ to find that $V(\mathcal P') = \emptyset$.  So there's no such $A$.
A: There is no such algorithm, even if n is zero. Take p_i to be 0 unless you can find a counterexample of length i to your favorite unsolved math problem (such as "is 2i+4 the sum of 2 primes?"), in which case p_i is 1. 
A: Answering the same question twice with opposite answers seems a little indecisive, but anyway:
Hilbert ran into essentially this problem in his work on invariant theory. More precisely he showed that certain ideals were finitely generated without at first giving an algorithm for finding a finite basis. It was this that provoked Gordan's famous comment about Hilbert's work being theology not mathematics (which was a joke, not a criticism of Hilbert: Gordan had a humorous streak and thought very highly of Hilbert's work). However Hilbert was later able to make his work on invariant theory constructive, and show that it was possible to find finite generating sets in `the cases that actually came up in invariant theory. 
The point of this is that although the problem as stated has no solution for arbitrary recursively enumerable sequences of polynomials, it is quite likely that there is an algorithm `that covers all the recursively enumerable sequences you are  interested in.
A: I think the answer is no, but let me first give a precise version of the question
(which I think Daniel's argument doesn't quite address).
Fix some reasonable listing $P_0,P_1,\dots$ of recursively enumerable sets of polynomials.
[See below for a ``reasonable" coding.]
I claim that there is no algorithm to determine if $V(P_e)=\emptyset$.
Let $K$ be the diagonal halting set.  Namely, $K=$ {$e$:  the $ e^{\rm th}$ Turing machine
halts on input $e$}.
For each $e$ let $P_e=\{p_0,p_1,\dots\}$ be the recursively enumerable sequence of
polynomials where $p_i=0$ if the $e^{\rm th}$ Turing machine has not halted by
stage $i$ and $p_i=1$ if has.
Then $V(P_e)=\emptyset \Leftrightarrow e\in K$. Since $K$ is undecidable there is no algorithm to decide if $V(P_e)$ is empty.
One way to code sequences of polynomials would be to  let $q_0,q_1,\dots$ list all polynomials, and let $P_e$ be
{$q_i:$ the $e^{\rm th}$ Turing machine halts on input $i$}. To get to Ian's setting 
we could view $P_e$ as the sequence $p_0,p_1,\dots$ where $p_{(i,j)\}$ is 0
unless the $e^{\rm th}$ Turing machine halts on input i at stage $j$ in which
case it is $q_i$ and $(i,j)$ is some computable pairing function.
A: Agol's other question (If one has a finitely generated group G  with solvable word problem, for any n  can one compute the representation variety G -> SLn(C)) also has a negative answer. In fact one cannot even compute the number of homomorphisms to the group of order 2 when G is generated by one element g. 
Take the relations to be g^(2k+1)=1 if  some given Turing machine halts for the first time after k steps. A little thought shows that this group has an effectively solvable word problem and an effectively recursive set of relations, but one cannot decide if it has a homomorphism to the group of order 2 without solving the halting problem for the given Turing machine. 
A: If you make some further assumptions about how that recursively generated set is actually generated, then yes you can [other answers show that, without these, you can't].  The most natural one is some degree condition -- i.e. that the total degree of your polynomial grows.  That's actually not enough.  What you really need is a condition which will imply that the Newton Polygon of your set of polynomials will no longer change once $k$ is large enough.
In other words, for your problem to switch from 'undecidable' to 'solvable', you need stronger invariants than what you get simply by saying 'recursively enumerable over $\mathbb{Z}[\mathbf{x}]$'.  And, frequently, you do have such invariants right in your generation procedure for the $p_i$'s; whenever the $p_i$'s do not encode some kind of (undecidable) arithmetic statement, there's a chance.  In other words, in your case, do you actually have more structure than you gave in your question?
