Collatz conjecture proved?
Written by Mike James   
Saturday, 04 June 2011

A proof has been proposed for the Collatz conjecture by a German mathematician who is a former student of Collatz who originally came up with this addictive problem. If it is solved it may improve the lives of mathematicians everywhere.

 

If you don't know what the Collatz conjecture is then you haven't missed out on anything really important - with the possible exception of the excellent Xkcd cartoon reproduced below:

Collatz Conjecture

 

The cartoon is accurate but let's make the conjecture clear:

  • Pick a number, a positive integer.
  • If even divide by 2
  • If odd multiply by 3 and add one
  • Repeat above two steps with new value

If you try it you will discover that you eventually reach a result of 1. For example, 10, 5,16, 8, 4, 2, 1. At first you think it must be an accident and so you try a few more tests. Then you become obsessed and write a program - and you always end up at 1.

So far it has been verified for values up to 5.76x10^18.

The Collatz conjecture is that this is indeed always true but can you prove it?

The sequence of numbers is also known as a "hailstone sequence" and the conjecture is a "halting problem". It is has already been proved that for a generalization of the sequence the problem is undecidable - but this doesn't settle the specific conjecture.

Somehow it seems like a simple problem but it is remarkably tough and it just goes to prove that very complex systems arise out of simple algorithms. Only in this case it is the proof of the behavior that is complex, not the actual behaviour. It is an example of a class of iteration problems that are hard to prove.

Paul Erdos (and if you don't know who he is you're not even interested in mathematics) said of the conjecture:

"Mathematics is not yet ready for such problems"

and he offered $500 for a solution.

The problem also has a reputation for being addictive if you have that sort of mind. It was reported then when introduced to Yale everyone worked on it but got no where. The same thing happened when the problem arrived at the University of Chicago and it quickly got a reputation for being a conspiracy to slow down mathematical research in the US.

Now at long last a German mathematician, Gerhard Opfer, a former student of Collatz has announced a proof. It hasn't been peer reviewed yet but you can read the pre-print.

So is the problem solved?

The paper runs to 32 pages and we will have to wait for it to be checked for errors. Such is mathematics in the Internet age - no longer are proofs brought down from the mountain top in their perfection but they are thrown to the crowd to survive being torn apart.

See:

 An analytic approach to the Collatz 3n + 1 Problem

Related reading:

Computability

 

Banner


Open Source Code Puts Android At Risk
30/07/2014

A flaw in the Apache Harmony project has come back to threaten every version of Android from 2.1 to 4.4. It makes it possible to load apps that claim to be from almost any legitimate authority.



Amazon Live App Testing
18/08/2014

Amazon has released a tool that lets you test mobile apps on a group of users before going fully live.


More News

Last Updated ( Saturday, 04 June 2011 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.