4 ms·
I never thought one could actually do arithmetic on Graham-size numbers. If you didn't have the branch in Collatz, then it would be algorithmically computable.
by ballenf 4y ago
I never thought one could actually do arithmetic on Graham-size numbers. If you didn't have the branch in Collatz, then it would be algorithmically computable. But then so would Collatz itself.
- pclmulqdq 4y agoI don't think that's the issue. The Collatz conjecture has a non-branching form in binary (using weird operations), but that doesn't really help anything because the operations are hard to analyze as mathematical operators. Here is the non-branching form: 0. Start with an odd number n 1. Apply n = 3n + 1 2. Count trailing zeroes of n 3. Right shift n by the trailing zero count 4. Return to (1), stopping at n = 1
- leereeves 4y agoHow do you "count trailing zeroes of n" without branching?
- pclmulqdq 4y agoI don't know how you formulate it mathematically for unbounded numbers without branching. On a computer, there are a variety of ways (including a single assembly instruction), but pretty much all of them rely on n being bounded. If you're trying to feed a SAT solver, you can bound the size of the numbers at some level, and then pass one of the closed-form formulas into the solver.
- leereeves 4y agoYeah, it seems important that the formula support unbounded numbers, because the numbers can grow inside the sequence. Naively, it seems like any starting value (except those for which you already know the full sequence) might lead to values that exceed any arbitrary bound.
- pclmulqdq 4y agoFrom a theoretical standpoint, I think you could also attempt to approach this by thinking about a field where the "remove trailing zeros" step is built in. It may be a very weird field to do math on, and we may be unprepared for the math that is required, but it's a way to remove branching from the operations required for a proof. There's nothing inherently special about the branchiness of "remove trailing zeros" as an operation if you drill down into it: addition, for example, also needs conditional execution (based on the carry in to each section of a number). Otherwise, if you're searching for a counterexample, bound n by some ridiculous number of bits (whatever your supercomputer supports) and run your solver with a simple closed form.
- eru 4y agoHere's how you can do a 'branchless' one, using Python syntax: f = lambda n: (n & 1) * n + ((n + 1) >> 1) No need to count any trailing zeros. Of course, the multiplication sort-of acts as a branch.
- eru 4y agoI don't think 'non-branching' is something we can rigorously define. I mean, lambda calculus doesn't have any build-in branching, but you can style write arbitrary programs in it. Same for 'post correspondence problem' or SKI calculus.
- pclmulqdq 4y agoI agree with you completely. People get hung up on the fact that the conjecture has a "2-way" decision, but if you redefine the problem, there are a ton of ways to make it have no decision points. The one I posed is a simple mutation, but there are turing machines that compute the Collatz algorithm, you can turn it into a geometry problem, etc. All of these can be defined as "branching" or "non-branching" however you want.
- eru 4y agoYes. 'Branching' and 'non-branching' make sense in the context of specific architectures and/or languages. Just not really in an abstract algorithmic sense.