My initial idea is to go the other way around: We can count natural numbers using the successor function, starting at 1. E.g.: 1, s(1) = 2, s(s(1)) = s(2) = 3, and so on. So if we see a number n, we know it's s(n-1), which is s(s(n-2)) and so on, until we reach 1. So we have a nice, linear chain, and it's trivial to construct an algorithm f(n) [or more mathematically, a function f: N -> {s,ss,sss,...}] that (i) produces the necessary operations to reach any given natural number n in that chain, starting at 1, and (ii) terminates for every input n.<p>Now we don't use s(x), but instead two operations that are inverse to the Collatz rules: a(x) = 2*x and b(x) = (x - 1)/3 (with b of course is not always being possible). Starting at 1, this can now be used to construct a tree containing "some" numbers, and we can use that it to describe a path to a number from the root.<p>If the conjecture holds, the tree constructed from these functions has to contain all natural numbers.<p>My nudge is then: If I have a number n, can I give an algorithm/function f': N -> {a,b,aa,ab,ba,bb,...} that (i) finds a path to n, and (ii) always terminates? Answer: I have no idea =)<p>E.g.: f'(5) = aaaab <=> b(a(a(a(a(1))))).<p>So we have f'(1)=no idea how to represent, f'(2)=a, f'(3)=aaaabab, f'(4)=aa, f'(5)=aaaab, f'(6)=aaaababa, f'(7)=aaaabaaab[...], f'(8)=aaa,...<p>(However, maybe it is not possible to even construct f': I believe the target space of f is of another infinity than the target space of f' -- obviously this isn't my area of expertise).