Exploring the Collatz Problem: Is it Undecidable?

[MathematicalPhysicist]

in mathworld, they say that conway proved "that Collatz-type problems can be formally undecidable."
does it mean that this problem is undecidable?
if yes i don't know why for example in the website of plus.maths.org they still saying it hasnt been proven/disproven.

anyway, i tinkerred around with the original conditions of the problems and instead of when n is even n'=n/2 and when n is odd n'=3*n+1
i decided to switch to when n is even n'=n/2+1 when n is odd n'=2n

this sequence is limited from the original because if you start with 2 you get 2 all the way, but besides this and the number 1 (which gives you a repeating sequence of 1,2,1,2...) they yield also a repeating cycle as the one given by the original problem but instead of 4,2,1 cycle you get a 6,4,3 cycle (yes plus two than the original), I am not familiar too much to recursion so I am not sure if this is a trivial thing.

 

[TenaliRaman]

in mathworld, they say that conway proved "that Collatz-type problems can be formally undecidable."
does it mean that this problem is undecidable?
if yes i don't know why for example in the website of plus.maths.org they still saying it hasnt been proven/disproven.

Because there is a difference proving a problem to be undecidable and whether it is provable or not.

Note that Collatz problem can be conveniently converted into a decision problem. That is given a number , decide whether it will converge to 1 or not. Being undecidable means that one cannot find an algorithm which can decide upon this problem.

The same formally in the theory of languages :
"If e is a reasonable encoding of a decision problem P over the alphabet A, we say P is solvable or decidable, if the associated language Y(P) = {e(I)| I is a yes-instance of P} subset of A* is a recursive language."

The above quite confusing statement simply states that if one can design a Turing Machine that can give output true or false depending on whether the input of the problem is accepted or not, then the problem is said to be decidable.

You can see that this does not mean there is no way something can be proven or disproven.

-- AI

 

[MathematicalPhysicist]

undecideable

according to mathworld: "Not decidable as a result of being neither formally provable nor unprovable."

and if conway did this it means you can never know if collatz problem (or conjecture) is always correct, because it is undecidaebale therefore there is no use in trying to prove/disprove it because it's already undecideable, is it not?

 

[matt grime]

he didn't show that the Collatz problem was undecidable, or anything else. He showed there were collatz type conjectures that are undecidable. that is why that webist says it it is still an open question.

 

[TenaliRaman]

yeah he did prove that a class of Collatz type problem (Conway-Collatz Problem) is undecidable, which includes Collatz problem as a special case.

But i really am surprised with Mathworld's definition of undecidability, which is certainly wrong and misguiding. Maybe i should write to Mr. Eric about this. Luckily, wikipedia has a better definition http://en.wikipedia.org/wiki/Undecidability .

However, repeating myself , undecidability doesn't necessarily translate into "proof does not exist".

-- AI

 

[master_coda]

yeah he did prove that a class of Collatz type problem (Conway-Collatz Problem) is undecidable, which includes Collatz problem as a special case.

But i really am surprised with Mathworld's definition of undecidability, which is certainly wrong and misguiding. Maybe i should write to Mr. Eric about this. Luckily, wikipedia has a better definition http://en.wikipedia.org/wiki/Undecidability .

However, repeating myself , undecidability doesn't necessarily translate into "proof does not exist".

-- AI

The Mathworld definition isn't wrong; the definition is just used in different fields. One usage is from mathematical logic and the other is from computability theory. In fact, Mathworld even provides the computational definition under "Recursively Undecidable".

The only problem is that when the Collatz Problem article said "undecidable" it isn't made clear that it's actually referring to the definition Mathworld calls "Recursively Undecidable".

 

[TenaliRaman]

The Mathworld definition isn't wrong; the definition is just used in different fields. One usage is from mathematical logic and the other is from computability theory. In fact, Mathworld even provides the computational definition under "Recursively Undecidable".

The only problem is that when the Collatz Problem article said "undecidable" it isn't made clear that it's actually referring to the definition Mathworld calls "Recursively Undecidable".

You sure

The way i read it in logic was,
"A particular logic was undecidable if there is no algorithm that can decide true or false over whether a sentence is valid in that particular logic"

So it turns out that predicate logic is undecidable.

Please do correct me if i am wrong and also please do give online references if possible. (I am giving exams on these things, so its better for me to get things corrected than to have muddled ideas abt them).

-- AI

 

[MathematicalPhysicist]

he didn't show that the Collatz problem was undecidable, or anything else. He showed there were collatz type conjectures that are undecidable.

such as?? (i had to lengthen my message, sorry :grumpy: ).

 

[matt grime]

Weel, from my understanding of it, and it appears to be wrong, and I am basing this on something I read a while ago that I didn't pay attention to, he constructed various iterative formulae with convergence conjectures akin to Collatz type conjectures that were unprovable in ZFC, or something like that. I'm not an expert on the difference between undecidable and unprovable, and wouldn't comment on that.

Apparently he showed something about the Collatz conjecture itself, according to TenaliRaman, though I hadn't read it like that.

 

[master_coda]

You sure

The way i read it in logic was,
"A particular logic was undecidable if there is no algorithm that can decide true or false over whether a sentence is valid in that particular logic"

So it turns out that predicate logic is undecidable.

Please do correct me if i am wrong and also please do give online references if possible. (I am giving exams on these things, so its better for me to get things corrected than to have muddled ideas abt them).

-- AI

Your usage of "undecidable" is probably the better one, and more standard now. It's just that I've seen the other usage a lot in lectures and conversations that I'm not willing to say that it's outright wrong.

I don't have a good reference, but here's a http://www.math.niu.edu/~rusin/known-math/99/undecidable that gives a pretty good summary of the confusion. It does suggest that the usage you're objecting to is confusing and obsolete, but not entirely non-standard. It's not really an authority of any kind, but there really isn't an authority that gets to decide what definitions are "correct" anyway.

 

[master_coda]

Weel, from my understanding of it, and it appears to be wrong, and I am basing this on something I read a while ago that I didn't pay attention to, he constructed various iterative formulae with convergence conjectures akin to Collatz type conjectures that were unprovable in ZFC, or something like that. I'm not an expert on the difference between undecidable and unprovable, and wouldn't comment on that.

Apparently he showed something about the Collatz conjecture itself, according to TenaliRaman, though I hadn't read it like that.

As far as I know (and I may also be wrong) what was proven is that there are Collatz-type problems which are undecidable, but that the Collatz problem itself may or may not be; that is still an open problem.

And I mean undecidable in the sense that TenaliRaman was using; the definition from Wikipedia.

 

[MathematicalPhysicist]

so this collatz type problems, are they like the modification i had given in my first post, i.e:when n is even n'=n/2+1 when n is odd n'=2n which gives you a repeated cycle plus two?

 

[TenaliRaman]

Your usage of "undecidable" is probably the better one, and more standard now. It's just that I've seen the other usage a lot in lectures and conversations that I'm not willing to say that it's outright wrong.

I don't have a good reference, but here's a http://www.math.niu.edu/~rusin/known-math/99/undecidable that gives a pretty good summary of the confusion. It does suggest that the usage you're objecting to is confusing and obsolete, but not entirely non-standard. It's not really an authority of any kind, but there really isn't an authority that gets to decide what definitions are "correct" anyway.

So undecidable is undecidable eh? :rofl:

so this collatz type problems, are they like the modification i had given in my first post, i.e:when n is even n'=n/2+1 when n is odd n'=2n which gives you a repeated cycle plus two?

a bit of research on net gave me this link , check it out and yes u are sort of correct

-- AI

 

[MathematicalPhysicist]

TenaliRaman, i checked the link you gave and it got me to a page which had this title :"Permission denied", so i guess something is wrong in the address, any tips on how to reconcile this mistake?

 

[master_coda]

TenaliRaman, i checked the link you gave and it got me to a page which had this title :"Permission denied", so i guess something is wrong in the address, any tips on how to reconcile this mistake?

Use http://www-2.cs.cmu.edu/afs/andrew.cmu.edu/course/15/354/www/postscript/iteration2.pdf instead.