Is algebraic dependency decidable? A set of numbers $S=\{x_1,...,x_n\}$ is said to be algebraically dependent if there exists a (multivariate) polynomial $p$ with coefficients in $\mathbb Q$ whose roots contain $x_1,...,x_n$ (or a subset thereof).


  Given numbers $S=\{x_1,...,x_n\}$, is it decidable whether they are algebraically dependent?


Now, there is obviously an encoding issue here, since the numbers need to be transcendental, so describing them is problematic. Any solution would do, but specifically, I am interested in the case where all the numbers are of the form $e^{a_i}$, where the $a_i$'s are linearly independent over $\mathbb Q$.

The motivation for this question is understanding whether a (positive) solution to Schanuel's conjecture would automatically lead to a constructive solution.

UPDATE (based on the comments): the encoding of the numbers is an issue. I'll accept any answer which suggests either a reasonable encoding for a subset of the reals for which the problem is non-trivial, or a solution that uses a computational model that allows real numbers.
A model of computation allowing real numbers is the Real-RAM model. In this model, it is impossible to even decide if a number is rational. Indeed, the time-T halting sets are semialgebraic. If any one of them has a non-empty interior, then the time-T yes-set and time-T no-sets are semialgebraic subsets with no-empty interior, which is a contradiction. If none of the time-T halting sets is semialgebraic, then their union cannot be $\mathbb{R}$.

Answer to the previous version of the question:

If $a_1,\dotsc,a_k$ are algebraic numbers that are linearly independent over $\mathbb{Q}$, then $e^{a_1},\dotsc,e^{a_k}$ are algebraically independent over $\mathbb{Q}$. This is the Lindemann–Weierstrass theorem. So, if $a$'s are algebraic (as in the current version of the question), then the answer to your question is "yes".