Given a tuple $(x_1, \ldots, x_n)$ of computable real numbers $x_1, \ldots ,x_n$ and its cardinality $|\{x_1, \ldots x_n\}|=d \leq n$, is it decidable which numbers have which multiplicity? In other words, can we decide whether $x_i=x_j$, for $ i, j = 1, ...,n$ with $i\neq j$ ?
Here is the origin of this question:
On
No. This isn't possible even if $n = 2$.
"Computable" means "we can approximate the number to within any desired precision by a finite terminating algorithm". There's a MathOverflow answer which states that equality of computable numbers is not decidable, by using it to decide whether an arbitrary Turing machine halts.
(My original answer, which OP correctly pointed out was nonsense).
Yes. The following algorithm will work:
list = {}
for i=1 to n
for j=i+1 to n
if x[i] == x[j]: add (i, j) to list
return list
By the Church-Turing thesis, there is a Turing machine which does the above.
What if we just enumerate and check the $n$ computable approximations $(A_k(x_1),\cdots,A_k(x_n))$ of $(x_1, \cdots x_n)$ up to an error of $\frac 1 {10^k}$ iterating on $k$?
As an example we may have:
So we conclude that that $x_5$ and $x_6$ are different from the other ones and we have two groups $(x_1,...,x_4)$ and $(x_5,x_6)$ that have a distance of $1$ at lest so that we can be sure that $x_i\neq x_j$ for $i=1,\cdots ,4$ and $j=5,6$. If $d=2$ we are done otherwise we continue:
Now we can see four groups: $(x_1,x_2)$, $(x_3,x_4)$, $(x_5)$, $(x_6)$. If $d=4$ we are done, otherwise we continue with the error $0.01$.
If $m$ is the minimum distance between the $d$ distinct numbers (that we don't know) we will have $10^{-k}<m$ at the step $k>\log_{10}(m)$ where we will see exactly $d$ different groups. We don't know $m$ but will know that we have finished because we know the number $d$ in advance.