4 ms·

I loved this. Some comments. Not really spoilers I hope... For "Unwanted Expansion" the answer is technically correct but I am displeased that it doesn't prove

I loved this. Some comments. Not really spoilers I hope... For "Unwanted Expansion" the answer is technically correct but I am displeased that it doesn't prove there wont be any infinite loops. Whereas analyzing invariant in the tree should prove that. For Boxes in Boxes it says "But, if we take ε to be huge", but how big is huge, and what if it isn't huge? Seems like something in the proof is being hand waved over. The natives and suicides I enjoyed they really made me go aah!. The irony about the suicides is that the if the people were too dumb to apply the logic, they'd survive.

Sniffnoy 9y ago
"If we take ε to be huge" just means "let's analyze the growth rate as ε goes to infinity". More formally, what's going on is that you have a function which is polynomial in ε and which is always positive; therefore the leading coefficient must be positive, as if it were negative, the polynomial would be eventually negative. The question "what if it isn't huge" makes no sense; we can pick ε, it's not some external given. (Actually, as mentioned, we're not picking it to be one specific value but rather letting it tend to infinity, but that's another matter.)
- quickthrower2 9y ago
  Thanks. Nice explanation. It's been a while (18 years) since I've read maths proofs.
gowld 9y ago
Turn the "suicides" into escaping prisoners, so being smart enough makes them survive.
gowld 9y ago
Yes, the solution to "Unwanted Expansion" is simply "because we assume that math works". It's begging the question. If you don't know what he's assuming, you don't know what proofs are "interesting". You could just as well say, "Because it's a finite" expression. "Boxes in Boxes" doesn't really fit the theme. It's a complicated elementary math problem that's hard to solve, but not "tricky" in way that makes it seem impossible.
- ezrast 9y ago
  The unstated observation made in Unwanted Expansion is that if every variable is equal to 2, then every operation in the expression must increase the total by at least 2 (note that only addition and multiplication are allowed, not subtraction or division). In other words, an expression with n terms or factors will always evaluate to at least 2n. This puts an upper bound on how far any finite-valued expression can be expanded.
jakear 9y ago
I was is similarly displeased with "Unwanted Expansion". I'd prefer some sort of fixpoint algorithm, which could then be a applied to the case with "-", which their version couldn't.

Sniffnoy 9y ago

"If we take ε to be huge" just means "let's analyze the growth rate as ε goes to infinity". More formally, what's going on is that you have a function which is polynomial in ε and which is always positive; therefore the leading coefficient must be positive, as if it were negative, the polynomial would be eventually negative. The question "what if it isn't huge" makes no sense; we can pick ε, it's not some external given. (Actually, as mentioned, we're not picking it to be one specific value but rather letting it tend to infinity, but that's another matter.)

quickthrower2 9y ago
Thanks. Nice explanation. It's been a while (18 years) since I've read maths proofs.

gowld 9y ago

Turn the "suicides" into escaping prisoners, so being smart enough makes them survive.

gowld 9y ago

Yes, the solution to "Unwanted Expansion" is simply "because we assume that math works". It's begging the question. If you don't know what he's assuming, you don't know what proofs are "interesting". You could just as well say, "Because it's a finite" expression. "Boxes in Boxes" doesn't really fit the theme. It's a complicated elementary math problem that's hard to solve, but not "tricky" in way that makes it seem impossible.

ezrast 9y ago
The unstated observation made in Unwanted Expansion is that if every variable is equal to 2, then every operation in the expression must increase the total by at least 2 (note that only addition and multiplication are allowed, not subtraction or division). In other words, an expression with n terms or factors will always evaluate to at least 2n. This puts an upper bound on how far any finite-valued expression can be expanded.

jakear 9y ago

I was is similarly displeased with "Unwanted Expansion". I'd prefer some sort of fixpoint algorithm, which could then be a applied to the case with "-", which their version couldn't.