solrize on Nostr: The Collatz conjecture is possibly a lot harder. It's a \(\Pi^0_2\) proposition ...

The Collatz conjecture is possibly a lot harder. It's a \(\Pi^0_2\) proposition (forall n, exists k such that n's Collatz sequence reaches 1 after k steps) and it's one of a family of problems the general case of which is \(\Pi^0_2\) complete. This antihydra example has a basic resemblance but it's only \(\Pi^0_1\) (forall n, the number of odds seen is < 2x the number of evens seen).

The antihydra never terminating is very plausible since imagine that the odd-even sequence is replaced by random fair coin flips. Imagine that after some (large) N of flips, there have been 2x as many heads as tails. View the flips as a sequence of 1's and 0's, so 2/3 of the sequence is 1's. From the binomial distribution this gets extremely unlikely very fast. Or using Shannon entropy you could notice that the string must be compressible to about 92% of its original length, again putting it into a very rarefied subset of such possible strings (at most \(2^{-.08N}\) of them).

How to prove that the antihydra sequence acts like enough like a random sequence to transfer something like the above argument? No idea, but I'd like to hope it's not as hard as the Collatz conjecture.