I'll write $\longrightarrow$ for some standard iterations and $\implies$ for some possibly non-standard iterations. The relaxed Collatz conjecture is that for all $x$, $x \implies 1$. I'll call counterexamples to the conjecture escapees.
First of all, since it's a good example of the notation, a lemma: for all $a$, $4 a \implies 9 a + 1$.
Proof: $4a \implies 12 a + 1 \longrightarrow 36a + 4 \longrightarrow 18a + 2 \longrightarrow 9 a + 1$.
$\square$
Now here is what I will try to show:
Theorem: If $x$ is the smallest escapee, then $4x \implies 1$.
Proof: By elementary considerations, $x \equiv 3 \pmod{4}$. If $x \equiv 2 \pmod{3}$, then $\frac{2 x - 1}{3} \longrightarrow 2 x \longrightarrow x$. So in this case, $2 x$ can't be an escapee, and neither can $4 x$.
The next case is $x \equiv 0 \pmod{3}$. Write $x = 12k+3$. Using the lemma, $4x \implies 27k+7$. Observe that $x > 9k+2 \rightarrow 27k+7$ if $k$ is odd. Now if $x \equiv 15 \pmod{24}$, we also have that $4x \implies 1$.
It's also possible that $x \equiv 3 \pmod{24}$. In that case, we have $x = 24 j + 3$ and $x \longrightarrow 27j+4$. This means $j$ cannot be even. So we drill down again, with $x = 48i + 27 \longrightarrow 81i+49$. This means $i$ cannot be odd. But also, $4x = 4(48i+27) \implies 81i + 92$, so if $i$ is even, the next step brings us under $x$. This covers all the $x \equiv 0 \pmod{3}$ cases.
So far, our result is that if $x \implies 4x$, then $x \equiv 7 \pmod{12}$. Now I'll handle that case. Suppose $x \implies 4x$ and $x = 24k + 7$. Then we have:
$4x = 4(24k+7) \implies 9(24k+7)+1 = 216k+64 \longrightarrow 108k+32 \longrightarrow 54k+16$.
But also, $18k+5 \longrightarrow 54k+16$. This means $18k+5$ is an escapee too, but it can't be, since it's less than $x$. So the hypothesis is false and we have $x = 24k + 19$ instead.
Now, consider:
$4x = 4(24k+19) \implies 216k + 172 \longrightarrow 108k + 86 \longrightarrow 54k + 43 \longrightarrow 162k + 130 \longrightarrow 81k+65$.
By similar reasoning, $k \neq 3 \pmod{4}$, or else we can continue the chain two more steps to get an escapee less than $x$. Finally,
$x = 24k+19 \longrightarrow 72k+58 \longrightarrow 36k + 29 \longrightarrow 108k + 88 \longrightarrow 54k + 44 \longrightarrow 27k + 22$.
shows that $k$ can't be even, and substituting $k = 4 j + 1$:
$27k + 22 = 108j + 49 \longrightarrow 324j + 148 \longrightarrow 162j + 74 \longrightarrow 81j + 37 < x$
completes the proof, since that's all the cases.
$\square$
Corollary: if the Collatz conjecture is false and the smallest counterexample leads back to itself then that number is not a counterexample to the relaxed Collatz conjecture. In other words, if $y$ is the smallest number satisfying $\neg(y \longrightarrow 1)$, then $y \longrightarrow y$ implies $y \implies 1$. This is a weaker version of what I originally thought I had proved.
Corollary: If $4x$ is an escapee, then there is an escapee smaller than $x$. This suggests to me a recursive descent strategy where we attempt to show $z \implies 4k < 4x$. But it's not clear if number-crunching will get us anywhere further.
Let's note that this is not a question of whether Collatz is undecidable.
The statement $\neg\mathrm{Con}(PA)$ is undecidable (by $PA$, assuming $PA$ is consistent) but nevertheless $\neg\mathrm{Con}(PA)$ is provably equivalent to a certain Turing machine halting (the one that searches for a proof of a contradiction in PA).
Rather, the question is whether
there is a $\Pi^0_1$ statement $\varphi$ such that the Collatz problem, which on its face is $\Pi^0_2$, is already known to be equivalent to $\varphi$.
Here already known means in particular that we are not allowed to assume that Collatz is or is not provable or disprovable in any particular system, unless we already know that.
The best evidence that there is no such $\varphi$ seems to be in the paper mentioned by @Burak:
Kurtz, Stuart A.; Simon, Janos, The undecidability of the generalized Collatz problem, Cai, Jin-Yi (ed.) et al., Theory and applications of models of computation. 4th international conference, TAMC 2007, Shanghai, China, May 22--25, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72503-9/pbk). Lecture Notes in Computer Science 4484, 542-553 (2007). ZBL1198.03043.
Namely, they give a parametrized family of similar problems such that the collection of parameters for which Collatz-for-those-parameters is true, is $\Pi^0_2$-complete and hence not $\Pi^0_1$.
They can do this without thereby solving the Collatz problem, just like Matiyasevich et al. could show that solvability of diophantine equation was $\Sigma^0_1$-complete, without thereby solving any particular equation themselves.
If Collatz could somehow be simplified to a $\Pi^0_1$ form then quite plausibly the generalized version could too by the same argument (whatever that hypothetical argument would be) but that Kurtz and Simon show will not happen.
Best Answer
The current state of research excludes none of the two cases. The occurrence of some small cycles has been actually ruled out. You can easily find the relevant references in the Wikipedia page devoted to Collatz conjecture (the same that you linked), at the section "Cycles".