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?

# Collatz-Problem and undecidability

undecidable means it can not be proven.

this does not mean its false.

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?

"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.

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

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.

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

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..

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

Not in maths, faggot.

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.

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

By performing the computation

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.

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.

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.

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

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.

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?

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.

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

Does not*

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

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

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

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

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

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

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.

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).

even so, a computable one

Under what circumstance would it ever not be computable?

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.

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.

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.

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

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

Because we haven't tried all the numbers.

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.

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

Thanks senpai