patternMinor
Is it computable if a particular number follows the Collatz conjecture?
Viewed 0 times
numbercomputablethefollowsconjectureparticularcollatz
Problem
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.
Assuming the Collatz conjecture is false, is it computable to determine whether or not a particular number is on an infinite trajectory?
Assuming the Collatz conjecture is false, is it computable to determine whether or not a particular number is on an infinite trajectory?
Solution
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.
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.
Context
StackExchange Computer Science Q#70745, answer score: 6
Revisions (0)
No revisions yet.