The 3x+1 Problem [video] • Hacker News Board

Re: The 3x+1 Problem [video]

#81

Post by teruakohatu » Tue, Aug 10, 2021, 4:59 AM UTC

romwell wrote: post #79

teruakohatu wrote: post #44

Earlier quoted context omitted.

> 3x+1 is, too, a programming language What does this mean? Isn't having a catalog essentially precomputing a function for every possible input?

>What does this mean? A 3x + 1 program is a positive integer N . "Running" this program would be iterating 3x + 1 until it gets stuck in a loop (this would be the "halting condition"). The "output" would be a fixed function of the numbers in the loop (e.g. the loop itself; like 4, 2, 1). As far as we know, all "programs" in 3x + 1 output 4, 2, 1. This makes for a very boring language (essentially, one you can only ma…

> Which is what they do in FRACTRAN: they show how to encode an arbitrary program and its input as a number N, and how to read the output from the iteration.

What I don't understand is the encoding part. Is the encoding not essentially the same as execution? In other words the encoding function needs to be turning complete?

T(X) = N(E(T, X))

Re: The 3x+1 Problem [video]

#82

Post by smegger001 » Tue, Aug 10, 2021, 5:05 AM UTC

spoonjim wrote: post #77

soheil wrote: post #53

Earlier quoted context omitted.

I guess even if they're not common, clearly the person who first came up with 3x+1 didn't know it was going to be so hard to solve. So it was a random simple problem to formulate that ended up being very difficult to solve.

The entire mathematical world realized how interesting the Collatz conjecture was as soon as it was put forward. And it took until 1937 when Euclid figured out most of geometry 2000 years ago.

Euclid figured out most of geometry 2000 years ago...

*for flat planes. there was this thing about parallel lines he got wrong

Re: The 3x+1 Problem [video]

#83

Post by StephenAmar » Tue, Aug 10, 2021, 5:44 AM UTC

cgrealy wrote: post #58

jraph wrote: post #4

I recommend Veritasium, his videos are quite good. This one probably has good and useful visualizations but I was doing the cleaning while listening to it so I missed that. Still possible to follow without watching though.

Absolutely. His "gravity is not a force" video led me through a whole range of emotions from "this is ridiculous" to "actually..." to "holy crap, I've been wrong about this my entire life". In terms of sheer brain-breaking... this is my favourite: https://www.youtube.com/watch?v=ovJcsL7vyrk But this is the one I think people on HN need to watch most https://www.youtube.com/watch?v=3LopI4YeC4I

The gravity video was instrumental in me finally understanding years of physics classes.

And the YouTube algorithm was actually really useful and made discover this series of video on special relativity: https://youtube.com/playlist?list=PLoaVOjvkzQtyjhV55wZcdicAz...

Re: The 3x+1 Problem [video]

#84

Post by wodenokoto » Tue, Aug 10, 2021, 6:58 AM UTC

feoren wrote: post #62

gary17the wrote: post #37

This was a great video. But the one titled "Math Has a Fatal Flaw"[1] was even more interesting: the meta-mathematics, thus mathematics of entire mathematics (Gödel). [1] https://www.youtube.com/watch?v=HeQX2HjkcNo

I can't get over the clickbaity, obviously incorrect title to that one. I refuse to watch it for that reason alone. If the flaw is fatal, then every mathematician is wasting their time.

It’s about the gödel incompleteness theorem. I think it’s fair to say that’s as big a flaw in math as flaw gets.

It says there are things in math that are true but unprovable, and we can’t know if it’s unprovable.

Re: The 3x+1 Problem [video]

#85

Post by elcomet » Tue, Aug 10, 2021, 7:41 AM UTC

cgrealy wrote: post #58

jraph wrote: post #4

I recommend Veritasium, his videos are quite good. This one probably has good and useful visualizations but I was doing the cleaning while listening to it so I missed that. Still possible to follow without watching though.

Absolutely. His "gravity is not a force" video led me through a whole range of emotions from "this is ridiculous" to "actually..." to "holy crap, I've been wrong about this my entire life". In terms of sheer brain-breaking... this is my favourite: https://www.youtube.com/watch?v=ovJcsL7vyrk But this is the one I think people on HN need to watch most https://www.youtube.com/watch?v=3LopI4YeC4I

Forces are just models to predict interactions between particles.

It's only a model (a very accurate one though) so nothing is "really" a force. They are not material objects. But for gravity, something even more accurate was found to model it.

Re: The 3x+1 Problem [video]

#86

Post by haspok » Tue, Aug 10, 2021, 7:44 AM UTC

Why 3x+1? Why not any other polynom (or at least generalize to ax+b)? Where does it come from?

Re: The 3x+1 Problem [video]

#87

Post by vintermann » Tue, Aug 10, 2021, 7:59 AM UTC

bob1029 wrote: post #68

imperialdrive wrote: post #18

Earlier quoted context omitted.

I know so little about programming but this video absolutely left me up late trying to follow along: $count = 1 do { $count++ $i = $count [string]$array = "$i" $range = $i - 1 do { if ($i % 2 -eq 0) {$i = $i / 2} else {$i = (3 \* $i) + 1} $array = "$array" + ",$i" if ($i - $count -gt $range) {$range = $i - $count} if ($i -eq 2) {$i = "Break"} } while ($i -ne "Break") $array = "$array" + ",1" $hits = (($array -split "…

Here's a C# example: using System.Numerics; using System; var myBigStartingNumber = BigInteger.Parse("12893123812148934789012378957891325789012357891238912319824589123589012358915891589158989125"); Collatz(myBigStartingNumber); Console.WriteLine("Collatz returned 1"); static int Collatz(BigInteger x) { Console.WriteLine(x); return x == 1 ? 1 : x % 2 == 0 ? Collatz(x / 2) : Collatz(3 * x + 1); } (stack overflows virtu…

Yes, unless C# does tail call elimination (it doesn't, right? I'm a bit behind the times on such things) that will blow through the stack very quickly.

But something which is worth doing while playing with such programs, (besides writing it nonrecursively), is looking into alternative BigNum representations. Tree based number representations can make huge numbers expressible through few operations much smaller, at the cost of making "typical" numbers (those that can't be expressed by arithmetic expressions much shorter than themselves) only slightly larger.

Knuth made one such representation, called TCALC, which lets you do arithmetic on numbers far too large to fit into computer memory in regular byte string bignum representation. A US academic, Paul Tarau, has made similar huge-num libraries (slightly more elegant since representations are unique) for modern programming languages.

Re: The 3x+1 Problem [video]

#88

Post by rcxdude » Tue, Aug 10, 2021, 8:41 AM UTC

feoren wrote: post #62

gary17the wrote: post #37

This was a great video. But the one titled "Math Has a Fatal Flaw"[1] was even more interesting: the meta-mathematics, thus mathematics of entire mathematics (Gödel). [1] https://www.youtube.com/watch?v=HeQX2HjkcNo

I can't get over the clickbaity, obviously incorrect title to that one. I refuse to watch it for that reason alone. If the flaw is fatal, then every mathematician is wasting their time.

well, the theorem basically did show that a huge number of mathematicians were wasting their time on an impossible task.

Re: The 3x+1 Problem [video]

#89

Post by quux » Tue, Aug 10, 2021, 9:37 AM UTC

jraph wrote: post #4

I recommend Veritasium, his videos are quite good. This one probably has good and useful visualizations but I was doing the cleaning while listening to it so I missed that. Still possible to follow without watching though.

In his earlier days I used to dislike Veritasium because I felt he relied too much on the "go out and ask random strangers about science" format too much. But over the last few years he's really upped his game and evolved the format to the point where I'm subscribed to his channel and get excited when I see a new video from him.

Re: The 3x+1 Problem [video]

#90

Post by monopoledance » Tue, Aug 10, 2021, 1:53 PM UTC

WJW wrote: post #8

hashmash wrote: post #5

After watching this video, how many of us wrote a program to see if we could just randomly find a case which didn't converge? I wrote one, but of course, the program didn't prove the 3x+1 problem wrong.

I wrote one many years ago as part of going through (I think) the project Euler series. No hope of actually solving it ofc. It's a fascinating problem because it just seems so simple. I wouldn't be surprised if it turns out in the end that it's connected to some other seemingly unrelated (lack of) order in mathematics like prime numbers or whatnot.

Twin primes come to mind. Feels very similar in nature.

Overall, there might be a connection to complex systems and ontogenesis. Maybe our struggling with this is all down to some original sin in our perception. Some false axiom we all carry. Pathogenic, hereditary logic, which prevents us from seeing beyond the chaos. 3x+1 seems to capture the pleasing ordered imperfection of real living things, not artificial "organic" structures made by humans.