Banner
    Collatz Conjecture: Decided Or Undecidable
    By Sascha Vongehr | June 7th 2011 02:40 AM | 2 comments | Print | E-mail | Track Comments
    About Sascha

    Dr. Sascha Vongehr [风洒沙] studied phil/math/chem/phys in Germany, obtained a BSc in theoretical physics (electro-mag) & MSc (stringtheory)...

    View Sascha's Profile

    Undecidability is weird, much weirder than quantum theory, which is benign by comparison. Let me give a simple example for something that may well be undecidable:

    Take any natural number N. If it is even, divide it by two. If it is odd, then first multiply by three and add one before you also divide by two. This gives you a new number N1 which is either N/2 or (3N + 1)/2. Now repeat the same procedure over and over again, i.e. look at whether N1 is even or odd and get either N2 = N1/2 or - well you know what.

    The about 60 years old Collatz conjecture by the German mathematician Lothar Collatz is the proposal that all numbers will result at some point in the number 1 via the just described procedure. Start with 11 for example: N1 = 17, N2 = 26, then 13, 20, 10, 5, 8, 4, 2, and finally 1, as promised. The number N = 27 will at some point grow to 4616 before finally reaching 1.


    Nobody knows any counter example to this conjecture, but there is also no proof of it. There is a new claim of a proof spooking the media, but it is only a claim rather than a proof according to sober experts.

    If you cannot prove it, then obviously you can never be sure of whether there is not some large number for which the procedure does not lead to 1. Maybe there is a number where the procedure leads to N itself after a number of iterations, thus cycling for ever instead of ending at 1.

    The really intriguing aspect is: There is a generalization of this conjecture that is proven to be undecidable. Although the Collatz conjecture itself is not yet proven to be undecidable, it may well be. What would be weird about that?

    Lets imagine for a moment that we have a conjecture C, one just like the Collatz conjecture, that claims “C is true for any number N”. What does it entail if it is proven to be undecidable, meaning that one can neither prove nor disprove this conjecture?

    If you cannot prove it, then obviously you can never be sure of whether there is not some large number for which the conjecture is wrong. However, if there were even just one such number found, and it could be found any day if it existed, then obviously the conjecture would be disproved and thus decided. But undecidability is already proved, so this cannot happen. A counter example cannot possibly be found. However, this fact in turn is the proof of the conjecture itself, because it is precisely what the conjecture claims: that there is no such example where C is wrong.

    So the undecidability kind of decides it although the undecidability itself is of course the proof that it cannot be decided. You may and should suspect that something here is impossible or plain wrong. Undecidability proofs are solid proofs, but they do tell us something about truth.

    Much like quantum physics tells us that there is no naïve reality just decided “out there” in front of the door or our eyes, so undecidability teaches similar lessons about truth - well at least that it is a lot less "either this or that, period!" than we would like to believe.

    Undecidability and related non-computability may be important at the very basis of fundamental physics, for example, at least according to Roger Penrose, whenever gravity may bring nonlinearity into quantum mechanics. These types of suggestions are at least from one perspective promising:


    Generalizing the Collatz procedure to the complex plane results in the Collatz fractal, which reminds of the Mandelbrot set. Given the nature of related problems, undecidability is certainly suggested (not proved). These structures are the same in any universe – there is no multiverse of different mathematics as there may be for different viable physics. This may have deep implications for how we think about the universe if non-computability turned out to be a vital ingredient of fundamental physics.

    Quantum mechanics has disproved local realism, a lay-person accessible proof of that you can find here. Crackpots insist on local realism, while most physicists insist on non-local realism, but the latter does not deal much better with the “weirdness” of quantum physics. The perhaps most advanced but unpopular is antirealism.

    Undecidability/non-computability in physics is mostly put out by people who kind of like to keep the realism, as Roger Penrose does as far as I can tell (what else would “objective reduction” be motivating or motivated by). However, our ever finding non-computable physics would prove antirealism, which I will get back to at some point hopefully soon, so stay tuned.

    Comments

    Hi Sacha

    Your „paradoxon“ has ist roots, I think, in two wrong concepts:
    1: there are three! (not only the usual 2) possibilities for a statement on natural numbers (and on other axiomatic systems): True, false and undecidebal. So you cannot reason: if it is not true, it is false or vice versa.
    2: For prooving the decidability of a statement, you have to give a deduction of the statement or of its negation from the axioms (you can also use all proven statements) of the system, the usual deduction rules (= ordinary logic) and that in a finite number of steps. If you can do that with the statement, you have prooven it, if you do that with the negation of the statement, you have disprooven it.
    You violated the last thing, invoking that it might be, that one day someone finds a counterexample. That violates the “in finite steps “ part of the rules and invokes something the scholastic philosophers (Duns Scottus, Walter Burley, William of Ockham (that’s the guy with the razor)) called “potential infinite”. Those philosophers were aware, that with actual infinities (God can creat a infinite number of worlds, matter is infinitely devidable) they got problems and so they tried to use statements as “God can always create another world, if he wishes”. That trick helps only in well-behaved cases, as in the foundations of calculus (the epsilon/delta-trick).

    If you have proven the undecidability of a statement, you can add it to the axiomatic system (eg Peano for the natural numbers) and you get a new and consistent system of natural numbers, in which that additional statement is prooven to be true (as it is one of the axioms). Two problems stay: (1): That will not reduce your (or my) tax-bill and (2) there will be other undecidable statements in that new system (that is Gödels theorem). And that “ad infinitum”!

    Peter Gerber

    vongehr
    Not sure what you are trying to say. I am not claiming anything about the Collatz conjecture - I am just telling readers that it has recently been claimed solved while closely related questions are undecidable, and I talk about that the latter is a philosophically very interesting subject that may become important in physics - however, it is beyond my expertise and actually interest to dive into the fine details of undecidability versus independence from certain axiom systems and all that. So if you say that
    there are three! (not only the usual 2) possibilities for a statement on natural numbers (and on other axiomatic systems): True, false and undecidebal.
    then that is basically my point entirely, namely that truth is far from as clear cut as we would like. As I clearly also write: Something here is wrong and should be doubted. Of course there is something wrong in the argument as I have given it.
    You violated the last thing, invoking that it might be, that one day someone finds a counterexample. That violates the “in finite steps “ part
    I do not get what I violated. The Collatz conjecture is not proven, and for all we know, tomorrow somebody may find a very large number that violates the conjecture. If you mean I should not have put it into the paradox in that way - well yes, the paradox is all wrong anyway, as is stated. Paradoxes are not strict contradictions but there to make people interested into a subject.