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.
Best Answer
I gave a sequential machine computing the 3n+1/n:2 function in base 2 in several courses since 1990, but of course I am not claiming any originality here, since it is just an easy exercise.
Anyway, if you want to see in more details how this sequential machine can be computed in a systematic way, you can look at http://www.liafa.univ-paris-diderot.fr/~jep/PDF/Exposes/Sequential.pdf, slide 59.