The set of all positive whole numbers is denoted by $\mathbb{N}_+$.
Let $f\colon\ \mathbb{N}_+\to\mathbb{N}_+:n\mapsto \begin{cases}\frac{n}{2}&\text{$n$ even}\\3n+1&\text{$n$ odd}\end{cases}$.
Conjecture (Collatz). $\forall n\in\mathbb{N}_+.\ \exists N\in\mathbb{N}.\ f^N(n)=1$.
Let $m,n\in\mathbb{N}_+$. We define: $m\sim n:\iff\exists N_1, N_2\in\mathbb{N}.\ f^{N_1}(m)=f^{N_2}(n)$.
It is easy to see that $\sim$ is an equivalence relation on $\mathbb{N}_+$. If we suppose the truth of the Collatz conjecture, then there is only one equivalence class.
- How to prove that there is only a finite number of equivalence classes of $\sim$? Has somebody ever proven this? Or is the question whether there is only a finite number of equivalence classes open?
- Is there an algorithm solving the following decision problem?
INSTANCE: A pair $(m, n)\in\mathbb{N}_+\times\mathbb{N}_+$
QUESTION: Does $m\sim n$ hold?