h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

Just looking at it, it looks like asking whether the algorithm (as that is what it is) always stops on the number 1 is just a special case of the halting problem, which Alan Turing proved to be undecidable.

I could be wrong on this, though. I'm no expert.

I'm sure if you could prove that it was unprovable, then you would qualify for the reward.

It says that the prize is for a rigourous proof or disproof of the conjecture, though, and even if this counted then the prize should surely go to the estate of Alan Turing!

But I'm thoroughly convinced that this is where the answer lies.

The halting problem is, according to wikipedia: "Given a description of an algorithm and its initial input, determine whether the algorithm, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting." And Turing proved it to be undicidable; there is no solution.

Now, if we look at this 3n + 1 conjecture as an algorithm we can see that it either reaches 1 (and the program terminates) or it doesn't, and therefore repeats forever. So yes, proving that the algorithm works for any input is essensially the same problem as the one that Turing proved was insoluble.

Turing just said that you can't devise a procedure which will look at every algorithm and tell whether it finishes or not. THere are obviously plenty of algorithms that it is possible to prove they will finish. For example:

Count up to 10, then stop.

We can prove this will finish because we know that there are numbers 1 - 10 and that they go in sequence.

The 3n+1 conjecture is not so straightforward, but it still might be amenable to some sort of proof.

The example you give only has one possible input, though, but I see where you're coming from. I guess it's not so simple after all!

I'll get back to by rigorous proof of Sod's Law, then.

Just before I go to bed, lying awake thinking of what I could spend £1000 on before earth is destroyed;

It seems to me that for the conjecture to fail such a sequence would have to be unbounded.

Their is of course the problem of repeat elements, and I can't get my head round that at the moment. It just don't look right.

So; assuming the rogue sequence hasn't got any repeats then if K is a really big number, it is easy to see that the rogue sequence eventually has more members than K, no repeats.

So as usual I'm looking for a different problem/s, showing that the sequences are bounded.

(I'm rambling because this is supposed to be a conversation,) but that might be just as hard as the original problem.

I mentioned primes on My Space, they crop up in the sequence cycle, as they would, but in a pattern I can't put my finger on.

This is going to take a long time.

Addendum
error: 'the sequence eventually has greater than K members.' K is just a whole number and not to be thought of as a set. Sorry

Some years ago I read a paper in a Mathematics magazine whose title was "Don't try to solve these problems!" and the first problem was Collatz Conjecture.

Since we are talking about problems, how to solve the exponential equation below without guessing? Is there a method for that?

2^x = 4x


Of course one "looks and sees" that 4 is a root. But how to find it mathematically?

Gus

This sort of problem can often be solved by taking the log of both sides, but I can't see an easy way of doing it in this case.

Another approach is to use Newton's successive approximation method. Write the equation as a function set equal to zero: f(x) = 0. In this case,

f(x) = 2^x - 4x = 0

You make a guess at a value of x that solves the formula, then calculate (f'(x).x - f(x))/f'(x) as a better guess for x. In this case f'(x) means the derivative of the function.

Keep on repeating this process to get closer and closer to the accurate value for x.

That formula would be better written as:

xnew = xold - f(xold)/f'(xold)

Let T be the class of all hard problems that are true. We can see that 1+1=2 belongs to this class. But it seems to me their is another class H of problems almost true over the domain in question, and H is contained in T. Fermat's theorem is an example of this, the domain is restricted in order for it to be true.

The 3n+1 conjecture does not belong to H, but this does not mean it is either true or easy.

It is clear that consideration of algorithms on their own is unlikely to solve the problem, because of Turing and the Halting problem. The algorithm for 3n+1 can be explicitly stated and is primitive recursive.

But I no longer think it is unsolvable, just hard.

If you assume it is true, you can conveniently look at the end of the sequences and work back, but you come across another problem that might belong to H.

Applying some structure you can then arrange these sequences into equivalence classes, and a canonical bijection with N, a 1-1 onto correspondence with the natural numbers.

That doesn't prove anything!

So now we assume it's not true; we can construct therefore a sequence, x1,x2,x3,..... where non of the members belong to any of our partition of N into equivalence classes.

If we can do this for every bijection we have proved the set of our equivalence classes is uncountable. But our set is just made up of sets in N, and its not the Boolean or a Power set because we don't have any repeats.

I've had a look at a reference in the Edited Entry of 3n+1 and found it hard to follow, it doesn't explain every function in use, but they claim their are only finitely many cycles generated by any rule over N, and I hope somebody solves the 3n+1 problem soon.

On the 3n+1 conjecture which can be easily shown to be true for infinitely many non trivial starting points, all the trivial starting points, and with consideration to recent research is probably only false if at all for finitely many starting points:

Is their an m belong to N where p is any odd number such that (p*2^m)-1 is divisible by 3?

I know this to be true in specific cases because I've been using it to construct sequences, it turned out its easier brother was very easy, I was just overwhelmed by the question 3n+1 which caused me to think everything related was hard.

ps ^=power of

When it comes to statements made on the likelihood of a proposition being true or not, I always think of this quote from Arthur C. Clarke

“If an elderly but distinguished scientist says that something is possible, he is almost certainly right; but if he says that it is impossible, he is very probably wrong.”

I prefer to keep trying; sometimes “something wonderful will happen”

dbp

I had forgotten all about that.

What's this talk about canonical bijections? You're giving me a headache. If you want a migraine, try reading Gunther Wirsching's "The Dynamical System Generated by the 3n+1 Function".

P.S. I'm back to writing a long Guide Entry entitled "The 3n+c Problem". I hope I live long enough to finish it.

That's is all nonsense you know; in 1998 I suffered a brain injury in which I lost the ability to think more than one steps ahead, but then I got the unreasonable idea that if I tackled a hard problem I might get it back.

Instead I behaved like an eleven year old making elementary errors and dismissed them as a result of a spurious exercise in demonstrating ways to think mathematically.

However I now know what those without any special mathematical abilities feel when given a hard problem, not to suggest I had any really special abilities beyond being able to see further than a couple of steps making 'o' level stuff really easy and 'A' level not much harder. Now I can't even understand some of my own work.

I can sympathize; when I was in high school, I could multiply two 12-digit numbers together in my head (and get the right answer). Now I'm hard-pressed to multiply two 1-digit numbers together and get the right answer without a lot of re-checking.

cheers; same here.

I used to be really good at maths, but I was never able to do arithmetic - I have problems multiplying numbers bigger than 5 together.