HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is it computable if a particular number follows the Collatz conjecture?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#70745, answer score: 6

Revisions (0)

No revisions yet.