3 ms·
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 s
by jcranmer 7y ago
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).
- archi42 7y agoIf 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.