2
$\begingroup$

I was attempting to write a computer algorithm to determine if a particular number breaks the Collatz conjecture. It is very easy to determine if a particular number falls into a loop, however I cannot think of any way to determine if a particular number is on an infinite divergent trajectory.

Is it Computable to determine whether or not a particular number is on an infinite trajectory?

$\endgroup$
6
$\begingroup$

In short: we don't know :-)

There is a ((very) little) chance that the Collatz sequence is Turing complete (with probably some caveats like in the case of Two-counter Machines); i.e. there is an algorithm which for every turing machine $M$ outputs an $x$ such that:

$Collatz(x)$ is on a divergent trajectory if and only if $M$ doesn't halt on empty tape

in other words "deciding if a particular Collatz trajectory is divergent" could be undecidable.

$\endgroup$
2
  • $\begingroup$ Your condition should be uniform, i.e.: "There is algorithm which for every Turing machine $M$ outputs a number $x$ such that $\mathrm{Collatz}(x)$ is divergent iff $M$ does not halt on empty tape." $\endgroup$ Feb 25 '17 at 19:54
  • $\begingroup$ @AndrejBauer: thanks, it was/is a quite informal answer (perhaps a reduction to HALT exists); however I changed it according to your suggestion. $\endgroup$
    – Vor
    Feb 26 '17 at 18:38
2
$\begingroup$

It is not possible to write that program today, and be completely sure that it is correct.

But that's not what computability is about. The Collatz conjecture is probably true, so determining whether a number is "Collatz" or not is probably computable, and in fact can probably be computed just like this:

boolean isCollatz(int x)
{
    return (x>0);
}
$\endgroup$
7
  • $\begingroup$ Why is this not possible? $\endgroup$ Feb 24 '17 at 1:09
  • $\begingroup$ Because we have no proof that the Collatz conjecture is true or false, and we know of no way to prove that a number doesn't follow the rule (presuming the such numbers even exist). $\endgroup$ Feb 24 '17 at 1:11
  • $\begingroup$ I don't think what you are saying is correct. We do not know if there are any odd perfect numbers but we sure do know how to check to see if a particular number is one. $\endgroup$ Feb 24 '17 at 1:12
  • $\begingroup$ My answer only works for the question I answered, not all other questions that are similarly phrased $\endgroup$ Feb 24 '17 at 1:12
  • 2
    $\begingroup$ We just don't know of a way. It could very well be that someone will invent a reliable test (without proving the conjecture), but it hasn't been done yet. $\endgroup$ Feb 24 '17 at 1:21
0
$\begingroup$

First, some small tips about the testing:

The following are easily shown to be equivalent: a. The Collatz sequence reaches 1 for every starting point x ≥ 1. b. The Collatz sequence reaches a value y < x for ever starting point x ≥ 2. This reduces the work a lot.

You need to make sure that large numbers in a sequence are handled correctly. For example, if you use 64 bit integer arithmetic and don't watch out, you will get integer overflow and therefore rubbish results for relatively small starting values.

Now it's easy if you are a bit careful to write code that tries to test if the Collatz sequence ends at 1, with the following possible outcomes: a. Your code proves the sequence ends. b. Your code notices that it encountered numbers too large for it to handle. c. Your code detects a cycle. d. Your code detects that it didn't reach 1 in a very large number of steps. e. Your code just continues running forever.

Case a is fine. In case b, you change your code. Case c disproves the conjecture. Case e has never been encountered by anyone. Case d has never been encountered by anyone with the right definition of "very large". If you find a number where you can't prove it reaches 1, that's when you need to worry about it - but it's likely it will never happen.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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