Collatz-Problem and undecidability

Supergrass
Supergrass

So there is the assumption, that the famous 3x+1 problem is undecidable.
But doesn't that mean, we would be unable to ever find a counter example? And woudn't that actually proof the collatz conjecture?

Attached: colaltz.jpg (38 KB, 657x391)

Raving_Cute
Raving_Cute

undecidable means it can not be proven.

this does not mean its false.

Soft_member
Soft_member

Yeas but when it can't be proven nor disproven, we aren't able to find a counterexample. How does this not immediatly prove it?

Firespawn
Firespawn

"Not being able to find a counter example" is different than "counter example not existing".

There are a lot of things that us humans are unable to do. For instance, there are locations in the universe that we cannot observe. Does this prove that only the locations exist that we can observe? No.

Methshot
Methshot

how can we say we won't be able to find a counter example if one of them exists ?Iit might happen with some kind of lucky guess, a guy testing the precise number for which the conjecture does not work. As huge as this number is, if it exists the probability to pick it randomly wouldn't be 0

Illusionz
Illusionz

I thought undecidability guranteed there doesn’t exist an algorithm for deciding something in finite time. This problem is would technically be semi-undeciadable I think btw.

girlDog
girlDog

When you pick a number, you can prove that the conjecture is true for this number, but you'll never be able to prove that this number was the counterexample. Because if you compute X iterations without finding 1 then you give up that proves nothing, maybe you had to do X+1 iterations

RumChicken
RumChicken

You can prove the number is a counterexample if it's part of a different loop than 4-2-1.
So if Collatz conjecture is proven to be indecidable it would still mean that there is not any other loop i guess..

Stark_Naked
Stark_Naked

I thought undecidability guranteed there doesn’t exist an algorithm for deciding something in finite time.
Not in maths, faggot.

Gigastrength
Gigastrength

Not the same guy but you aren't understanding at all. No statement about Collatz has be proven. If you found a counter example, you'd probably win some sort of prize. But that's hasn't happened. Also nobody has proven it for all n, just the first several million or so.

TurtleCat
TurtleCat

How would you determine if a proposed counter example was indeed a counter example?

StrangeWizard
StrangeWizard

By performing the computation

Spazyfool
Spazyfool

The easy case would be if a given x entered into a finite cycle that wasn't the 4-2-1 cycle. This could be checked in finite time by iterating until a repeat is seen.

The more difficult case would be if x never entered into a cycle. This could not be brute forced through iteration and would require some clever logic to show that it never enters into a cycle.

You are forgetting the case where x never enters a cycle.

Nude_Bikergirl
Nude_Bikergirl

you dont understand what undecidability is, and yet you insist on bothering people on this board with your stupidity.
you could pick up any standard undergraduate computability textbook and see why you're hopeless. but no. you refuse to help yourself.

a predicate is decidable means that there exists a computable procedure which terminates in finite time, returning one definitive value when the input satisfies the predicate and a different definitive value when the input does not satisfy the predicate.

when you theorize that the collatz conjecture is "undecidable" you in essence mean that there is no algorithmic way to determine if a given input will reach 1 or will not reach 1.
"oh i randomly picked the right number" is not an algorithmic procedure, so this doesn't count as a computable algorithm to find a counterexample to the collatz conjecture.
The undecidability of the collatz conjecture then would merely indicate that the finding of a counterexample to the conjecture is at best uncomputable. Since you can't guarantee to that the process of just computing via the function will end in finite time, this is completely possible.
Of course, there might be no counterexamples. But if we were to find one, that would in no way imply that the process to find one is computable.
Similarly, I can look at a program and spend a lot of time staring at it and tell you whether or not it will stop. But there's no algorithm to do that. Just because I can do it when you hand me a pretty easy program doesn't make the Halting Problem decidable.

kizzmybutt
kizzmybutt

you could pick up any standard undergraduate computability textbook and see why you're hopeless. but no. you refuse to help yourself.

it's 2am where i am so no, i don't think i could find a book about it right now...
besides, it's precisely because i don't know much about undecidability that i'm on this thread hoping to find someone that will explain it to me. I was hoping for someone to explain it without being a jerk though.

But anyway, you did explain it pretty well in the rest of your post. I guess calling this kind of problem "undecidable" was a bit of strange choice, since even undecidable conjectures could theoretically be proved/disproved.

TechHater
TechHater

The proof for this shit lies in either proving the number of iterations for a number n aproaches infinity or proving by contradiction which will always lead to the first proof?
Wtf kinda shit is this? Can this even be proven/disproven? Sorry im just an undergrad baby taking calc 2, don't really know any pure maths

Spamalot
Spamalot

You are forgetting the case where x never enters a cycle.
If you are given an actual counter example that never enters into a cycle, it may be impossible to decide if it is actually a counter example.

cum2soon
cum2soon

This shit doesn't make any sense. Why 3x+1? Why x/2? Could I just make any random bullshit like this and call it the Retard Conjecture?

idontknow
idontknow

If it reaches 1 or reaches a number that reaches 1, it is not a counter example. The problem is to prove either all numbers reach 1 or that there exists a number that does (And which one?). Nothing to do with cycles.

StonedTime
StonedTime

Yes you could, but it wouldn't necessarily be interesting

Spazyfool
Spazyfool

Does not*

Stark_Naked
Stark_Naked

what if the counter example is bigger than wildberger's constant?

Lunatick
Lunatick

What subset of functions over the integers have this property of returning to a number? I guess that's a hard question to answer.

askme
askme

No shit. The conjecture states all natural numbers return to 1. It appears to be true. This hasn't been proven or disproven.

idontknow
idontknow

there's probably an infinite number of these things but since we can't prove them either way we can never know
But is there a way to know that something's similar

happy_sad
happy_sad

besides, it's precisely because i don't know much about undecidability that i'm on this thread hoping to find someone that will explain it to me. I was hoping for someone to explain it without being a jerk though.
you could do that without wasting all of our time, killing a thread, and looking like a complete fucking retarded faggot on the internet by just using Google.com or picking up a textbook

kill yourself

BinaryMan
BinaryMan

I don't understand your point. Every number tested hus far entered the same cycle.

haveahappyday
haveahappyday

Not the same guy, but if the number never gets into the same cycle, how would you know it is not in a cycle? A different one. Or even so, a computable one.

SomethingNew
SomethingNew

OP's claim is that the undecidabilty implies there are no counter examples.

My argument is that the undecidability would be in agreement with the existence of a counter example that cannot be proven to be a counter example.

The only way a counter example couldn't be able to be proven to actually be a counter example is if it doesn't enter a cycle (it goes on forever).

Inmate
Inmate

even so, a computable one
Under what circumstance would it ever not be computable?

Nojokur
Nojokur

why are you on this thread if you already understand everything that is known about this conjecture and if you're not willing to share your knowledge ?

speaking about retards, i'll let you guess how stupid you look when you go crazy about a random post in a random thread.

Lord_Tryzalot
Lord_Tryzalot

So there is the assumption, that the famous 3x+1 problem is undecidable.
That doesn't even mean anything. Undecidability does not mean what you think it means.

CouchChiller
CouchChiller

sorry i was a jerk, but i was trying to remind you that the internet exists.
if you're interested in the subject, search up Cutland's Computability. It's a pretty nice intro book. It doesn't talk about collatz, but you'll learn a bunch about what undecidability means (even in just the first few chapters) and getting a basic understanding of recursion theory made me a better mathematician even if i dont care for logic.
the dude who responded to you telling you to kill yourself wasn't me. the way i responded was standard Veeky Forums, that guy is just a fucking dick.
hope you continue to stay motivated, and enjoy some computability theory! it's really exciting and enlightening. plenty of people describe cantor's diagonal argument as one of their favorite proofs for its mixed mystical and beautifully visual nature, and that's how a lot of computability theory feels.

BlogWobbles
BlogWobbles

What the fuck is the point of this board then other than to discuss math and science? Iq threads?

Spazyfool
Spazyfool

I have a proof of this that will come out later this year, here is the intuition:
in a chain of successive evaluations, if on average we have the number of evens that come up is the same as the number of odds, we will on average keep growing exponentially at order 3/2
the key is that the natural numbers do NOT allow for this kind of "on average the number of evens is the same as the number of odds", they are structured in a way such that the number cone (the posisble numbers we can obtain, think light cones from relatively) for a specific odd number contains greater than 2/3s even numbers and so we always bring down the number eventually

screencap this

SniperGod
SniperGod

Because we haven't tried all the numbers.

BinaryMan
BinaryMan

So there is the assumption, that the famous 3x+1 problem is undecidable.

An assumption doesnt proof anything.
EXAMPLE
Lets assume OP is a faggot,
Then he likes other men.
So he doesnt have a girlfriend that he likes.
Conclusion, OP does not have a girlfriend that he likes.

my assumption doesnt proof shit. All i've done is say that A implies B holds as a statement.
But that does not tell me anything about the truth value of A.

we would be unable to ever find a counter example? And woudn't that actually proof the collatz conjecture?
Just because you are unable to get a girlfriend doesnt mean it cant be done.

Booteefool
Booteefool

Just because you are unable to get a girlfriend doesnt mean it cant be done.
Thanks senpai

Attached: u6n5h.jpg (192 KB, 1066x805)

Disable AdBlock to view this page

Disable AdBlock to view this page

Confirm your age

This website may contain content of an adult nature. If you are under the age of 18, if such content offends you or if it is illegal to view such content in your community, please EXIT.

Enter Exit

About Privacy

We use cookies to personalize content and ads, to provide social media features and to analyze our traffic. We also share information about your use of our site with our advertising and analytics partners.

Accept Exit