Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
How do you code $\Sigma$? In the standard definition of computability, inputs to programs are required to be coded as natural numbers – in particular, you can't code the entire powerset of an infinite set. –  Zhen Lin Dec 10 '12 at 23:38
    
@Zhen Lin: it is perfectly normal in computability to look at computable functions that take a set of natural numbers as input. It's usually covered about one chapter later than regular computability (plus or minus). The formalism is sometimes called "oracle computation" or "Turing reducibility". –  Carl Mummert Dec 11 '12 at 11:36
    
Yes, but even then there are still problems, as you pointed out in your answer. I was trying to suggest that the naive interpretation of the question is uninteresting: as soon as you allow inputs of infinite length, then any program that checks for duplicates in the input would have to run forever, and so it fails to halt in a very trivial way. –  Zhen Lin Dec 11 '12 at 12:02

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
"and a set never has duplicates" Whoops. That makes everything suddenly trivial. I meant a multiset. >_> –  Joe Z. Dec 11 '12 at 17:03
    
"there is no effective way, given a set Σ, to tell whether the set is empty." Didn't know that either. how come? –  Joe Z. Dec 11 '12 at 17:05
2  
If the set $\Sigma$ is presented as an infinite string of zeros and ones (i.e. as its characteristic function) then you would have to read the entire list before being able to determine whether it is empty – obviously, this will take an infinite amount of time. If we cut down to recursive sets, so that $\Sigma$ can be presented by the program that determines membership, we still wouldn't be able to effectively decide whether that program ever says that something is in $\Sigma$ or not. –  Zhen Lin Dec 11 '12 at 17:27
    
That makes sense. But are there any other representations that would make it possible to determine whether a set was empty? –  Joe Z. Dec 11 '12 at 22:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.