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.
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.
If the conjecture holds, the tree constructed from these functions has to contain all natural numbers.
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 =)
E.g.: f'(5) = aaaab <=> b(a(a(a(a(1))))).
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,...
(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).
The algorithm is easy: enumerate all possible strings in increasing order of length, and return the first string you found that returns n.
If there is such a string for n, then this will find it. It will terminate if and only if there is such a string for every integer (i.e., the Collatz conjecture).
If it only was that simple :) since we can not solve the halting problem, pure breadth first search doesn't help. We need to find another algorithm that makes use of the tree's structure.
If bfsearch could be proven to be the best algorithm, this would reduce the conjecture to the halting problem.
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.
If the conjecture holds, the tree constructed from these functions has to contain all natural numbers.
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 =)
E.g.: f'(5) = aaaab <=> b(a(a(a(a(1))))).
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,...
(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).