Exploring the Collatz Problem: Is it Undecidable?

  • Thread starter MathematicalPhysicist
  • Start date
In summary, in mathworld, it has been stated that Conway proved the undecidability of Collatz-type problems. This means that there is no algorithm that can determine the truth or falsity of these types of problems. However, this does not necessarily mean that the Collatz problem itself is undecidable. It is also important to note that there is a difference between undecidability and being unprovable.
  • #1
MathematicalPhysicist
Gold Member
4,699
373
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.
 
Physics news on Phys.org
  • #2
loop quantum gravity said:
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
 
  • #3
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?
 
  • #4
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.
 
  • #5
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
 
  • #6
TenaliRaman said:
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".
 
  • #7
master_coda said:
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 :confused:

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
 
  • #8
matt grime said:
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 ).
 
  • #9
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.
 
  • #10
TenaliRaman said:
You sure :confused:

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.
 
Last edited by a moderator:
  • #11
matt grime said:
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.
 
  • #12
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?
 
  • #13
master_coda said:
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? :smile:

loop quantum gravity said:
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 :smile:

-- AI
 
Last edited by a moderator:
  • #14
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?
 
  • #15
loop quantum gravity said:
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.
 
Last edited by a moderator:

FAQ: Exploring the Collatz Problem: Is it Undecidable?

What is the Collatz Problem?

The Collatz Problem, also known as the 3n+1 problem or the hailstone problem, is a mathematical conjecture that was first proposed by Lothar Collatz in 1937. It is a simple problem that involves starting with any positive integer and repeatedly performing the following operations: if the number is even, divide it by 2, and if it is odd, multiply it by 3 and add 1. The conjecture states that no matter what number you start with, you will eventually reach 1.

Is the Collatz Problem still unsolved?

Yes, the Collatz Problem is still an unsolved conjecture in mathematics. While it has been extensively studied and verified for numbers up to 268 (which is a very large number), no one has been able to prove or disprove its validity for all numbers.

Why is the Collatz Problem considered to be a difficult problem?

The Collatz Problem is considered to be a difficult problem because it involves a simple set of operations, yet it has not been solved for all numbers even after decades of research. It also has connections to other unsolved problems in mathematics, making it a complex and fascinating problem to explore.

Are there any known patterns or properties of the Collatz Problem?

There are many known patterns and properties of the Collatz Problem that have been discovered through computer simulations and mathematical analysis. For example, it is known that all numbers eventually reach a cycle of 4, 2, 1, and that certain numbers, such as powers of 2, have very simple and predictable trajectories.

How does the Collatz Problem relate to the concept of undecidability?

The Collatz Problem is closely related to the concept of undecidability, which is a fundamental concept in computer science and mathematics. Undecidability refers to problems that cannot be solved by an algorithm, and the Collatz Problem is a prime example of this. It is believed to be undecidable because it is impossible to create a general rule or algorithm that can determine whether any given number will eventually reach 1.

Similar threads

Collatz Conjecture - Bouncing Ideas
Replies
2
Views
5K
Similar to Collatz Problem (Please Read)
Replies
7
Views
3K
B Exploring Variations of the Collatz Conjecture: A Computational Approach
Replies
11
Views
2K
I Can this method be used to prove the Collatz Conjecture?
Replies
3
Views
2K
Challenge: Find the minimum amount of draws possible for a list of integers
Replies
9
Views
2K
Rotations of 3-Spheres: Exploring 4D Space & Beyond
Replies
13
Views
2K
Logical Systems+new Principles+attempt To Solve Collatz Conjecture
Replies
5
Views
5K
I Find an explicit formula for this n-sum problem
Replies
7
Views
2K
Some ideas concerning the Goldbach conjecture
Replies
2
Views
3K
Challenge Math Challenge - February 2019
3
Replies
86
Views
20K

Hot Threads

Recent Insights

Back
Top