Is the halting of a program that checks for duplicates in an infinite multiset decidable?

Question

A program $P(\Sigma)$ takes input $\Sigma$, which is an nonempty multiset.

Let $\Phi$ be an empty multiset.

1. Take any element $\sigma$ from $\Sigma$.
2. If $\sigma \in \Phi$, return true.
3. Otherwise, remove $\sigma$ from $\Sigma$ and put it in $\Phi$.
4. If $\Sigma$ is now empty, return false. Otherwise, repeat from step 1.

My claim is that if $\Sigma$ is infinite, determining whether or not $P(\Sigma)$ halts is undecidable. Is this true?

Answer 1

The question was edited to refer to multisets. Here is a completely different kind of answer that shows that there is no way to decide effectively whether there is some element that appears more than one time in a multiset.

The proof shows that if there were such an element, then the halting problem would be decidable. It goes as follows. Given a number $e$, we need to determine if the Turing machine $T_e$ with index $e$ halts when it is run with no input.

Given $e$, we can make a multiset $A$ as follows. For all $s$, if $T_e$ halts in exactly $s$ steps then $s$ is put in $A$ twice, and otherwise put $s$ in $A$ once. The multiset is computable: given any $n$, we can tell whether $n$ is in $A$ (it always is), and we can tell how many times $n$ is in $A$ by checking whether $T_e$ halts in exactly $n$ steps.

We are assuming we have a procedure to tell whether there are any duplicates in a given multiset. So we can feed the set $A$ to that procedure, and it tells us. But by construction $A$ has a duplicate if and only if $T_e$ halts. So we can solve the halting problem as follows: given $e$, check whether $A = A_e$ has any duplicates. That would be a computable method to solve the halting problem if there was a computable way to solve the duplicates problem. But there is no computable method to solve the halting problem, so there must be no method to decide if a multiset has duplicates.

Answer 2

I will assume, as is usual in computability theory, that by "set" you mean "set of natural numbers". Then we use the standard methods of oracle computation to formalize the algorithm.

Unfortunately, the algorithm stated never halts, but it also has some issues.

• Line 2 will never cause the program to halt, because the only numbers in $\Phi$ are ones that were previously removed from $\Sigma$, and a set never has duplicates: it contains each number zero times or one time. So any number still in $\Sigma$ is not in $\Phi$, and any number in $\Phi$ is not in $\Sigma$.

• Line 4 is not computable: there is no effective way, given a set $\Sigma$, to tell whether the set is empty. I will simply ignore that line.

• If you run the algorithm on the empty set, it will run forever on the first line, because it has to search for an element of the set and there is none. In general, "find an element of the set" requires an exhaustive search of each possible element.

• If you run the algorithm on a finite set, it will go through removing elements form $\Sigma$ until $\Sigma$ is empty, and then it will fail to halt when it looks for another number in $\Sigma$, as in the previous case.

• If you give it an infinite set $\Sigma$ it will keep removing elements forever, and never halt.