Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The 3x+1 Problem [video]

youtube.com

Post reply on HN
Print view View original

91–100 of 102 posts

Re: The 3x+1 Problem [video]

#91

Post by natmaka »

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…

Why, adding an accumulator, can't the "output" be the number of steps before reaching 1?

Re: The 3x+1 Problem [video]

#92

Post by romwell »

natmaka wrote: post #91
romwell wrote: post #79

Earlier quoted context omitted.

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

Why, adding an accumulator, can't the "output" be the number of steps before reaching 1?

Yes, it can be, lack of imagination on my part.

As others pointed out, though, if it always gets stuck in a 4-2-1 loop, that would mean that every "program" terminates, which would imply that the language isn't Turing-complete.

Re: The 3x+1 Problem [video]

#93

Post by romwell »

teruakohatu wrote: post #81
romwell wrote: post #79

Earlier quoted context omitted.

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

Encoding is not the same as execution because you only encode the program and its input.

You don't know what the output is unless you execute it on the FRACTRAN machine; the thing that gets you the output is execution.

Note that execution is not a function that gives a finite output, as some programs never halt, or never return an output at all.

So while you can always encode, you don't always get an output from that encoding (like in cases where the Turing machine never halts).

TL;DR: encoding is a function (finite #of bits -> finite #of bits). Execution is a function (finite #of bits -> ???), where ??? can be a finite or infinite sequence, or an empty set, and there is no way to tell which it is other than executing, which may take infinite time (see: Halting problem).

Re: The 3x+1 Problem [video]

#94

Post by ryankrage77 »

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.

Here's my attempt in python, https://gist.github.com/ryankrage77/345419fd223a8029699e12ee...

Re: The 3x+1 Problem [video]

#95

Post by EthanHeilman »

IIAOPSW wrote: post #59
romwell wrote: post #30

My biggest take-away from this was FRACTRAN[1], The Bestest Ever™ programming language designed by the (sadly, late) John Conway. To run a FRACTRAN program, you lookup its catalogue number, and repeatedly evaluate a certain simple function on it (which has the same spirit as the 3x + 1 one in the video). As in 3x+1, all operations are integer operations. FRACTRAN is Turing-complete, of course, so you can rewrite any…

If 3x+1 is a programming language, the Collatz conjecture must be false as otherwise it would always halt. I suspect 3x+1 is not Turing complete.

The collatz could be false and still never halt. For instance the counter example could have an infinite number of numbers between it and 1. Perhaps the cycle found is infinite in length.

Re: The 3x+1 Problem [video]

#96

Post by EthanHeilman »

EthanHeilman wrote: post #95
IIAOPSW wrote: post #59

Earlier quoted context omitted.

If 3x+1 is a programming language, the Collatz conjecture must be false as otherwise it would always halt. I suspect 3x+1 is not Turing complete.

The collatz could be false and still never halt. For instance the counter example could have an infinite number of numbers between it and 1. Perhaps the cycle found is infinite in length.

I might be wrong here.

Re: The 3x+1 Problem [video]

#97

Post by jones1618 »

kilroy123 wrote: post #20

I watched this the other day. I was left wondering one big question. Why does this need to be solved? Would that even change anything?

Decades ago the problem was considered a "deadend" because it was hard to solve but seemed unrelated to any other fields of mathematics and solving it wouldn't yield any techniques or partial solutions that could crack other well-known problems.

I wonder if that thinking has changed in the age of Computer Science since solving this kind of recursive/iterative problem might open up new ways to analyze algorithms or tackle the Halting Problem for some classes of programs.

Re: The 3x+1 Problem [video]

#98

Post by jones1618 »

spoonjim wrote: post #33
soheil wrote: post #25

It sometimes amazes me how utterly random problems like this end up being their own fields in mathematics. This ended up being a pretty fascinating problem, but coming up with an arbitrary equation like this and then checking to see if it satisfies yet another arbitrary requirement doesn't seem very difficult to do. Am I completely missing something here?

The conjectures where the condition is very simple (Collatz, Goldbach, Fermat) but the proof is very elusive are not as common as you think.

FYI: Many variations of Collatz (Mx+N where M and N are different numbers, imaginary numbers, etc.) have been explored. If I remember right many behave trivially/uninterestingly or are equivalent to Collatz only not as simple. So, Collatz is uniquely simple yet complex.

Re: The 3x+1 Problem [video]

#100

Post by ajross »

karmakaze wrote: post #76
ajross wrote: post #41

Earlier quoted context omitted.

> Why does this need to be solved? Obviously it "doesn't". Equally obviously this is mathematics, and it's worth doing if it's interesting. But a somewhat more serious answer is this: the fact that we don't know the answer to this relatively simple question implies strongly that we don't know how numbers work . And if there are obvious gaps in our understanding of number theory that show themselves in trivial ways li…

I didn't think that anyone believed that number theory was consistent and complete. [0] https://en.wikipedia.org/wiki/Peano_axioms

That's nitpicky and missing the point. If the only problem with a theory is that it's been reduced Goedel-style to an axiomatic base, then most people would argue we "understand it". Needless to say 3x+1 does not follow in any kind of obvious way from Peano. It's emergent behavior that flies in the face of axiomatic understanding. And that's why it's interesting.
Post reply on HN