# Converse of Collatz Conjecture

How to write a pseudocode program that halts only if the Collatz Conjecture is false.

-
In general, if you want code written you should ask in a computer forum, not in a math forum. In THIS forum, if you want help with homework, first you should show what you have done so far. –  GEdgar Jan 31 '13 at 19:51
There's a Collatz Tag! –  jspecter Jan 31 '13 at 20:19
"If Collatz conjecture is false then halt else go to infinite loop." I don't think code comes more pseudo than that! –  Gerry Myerson Feb 1 '13 at 2:24
@GEdgar This question isn't phrased in the most sophisticated way, but (as I read it) it is a mathematical question, not a CS one. Is there an algorithm which we can prove halts iff Collatz is false? The sophisticated framing is "can we find a $\Pi^0_1$ reformulation of Collatz"? I don't see how to do it, but I will certainly be interested to see if someone can find one. –  David Speyer Feb 1 '13 at 15:19
See math.stackexchange.com/questions/100218/… , where this same problem is discussed in much more sophisticated language, but without finding a solution. –  David Speyer Feb 1 '13 at 20:59

If the Collatz-conjecture is false, then we have either a "nontrivial" cycle (we have some in the domain of negative integers) or a divergent trajectory.

If we check all numbers, whether their trajectory arrives at 1 and find, that on a certain trajectory an earlier number occurs a second time, then the program may halt and print "collatz conjecture false for integer [n]" where [n] is the first number which signalled the occurence of a cycle.

However, this does not detect (and then halt the program) if we arrive at a divergent trajectory - so this answers your question only half way...

-
I would modify to loop and each step advance all the previously started sequences - if possible; and start the one at the next integer. If you found a cycle then it halts. Sort of a diagonalization-walk. –  Asaf Karagila Jan 31 '13 at 19:57
Since "verifying" that a trajectory is divergent is highly non-trivial, an algorithm that finds other cycles (like this) is probably the best you can do. –  TMM Jan 31 '13 at 20:00
@Asaf : well, there is another cycle-detecting method which procceds for each conjectured cycle-length (say "L") and for L=1 to infinity: <perform check>" the <perform check>-routine needs only finitely many steps (however increasing with L) - but that needs a bit more pseudocode... –  Gottfried Helms Jan 31 '13 at 20:05