Anders Kaseorg

There really isn’t any wiggle room here. The OP made it clear in both the spirit and the letter of the challenge that they’re talking about mathematical integers.

You’ll have to come up with a function other than id. I think it’s clear that any use of id is banned by this challenge.

The mathematical sense is ℤ → ℤ, not (Python variable) → (Python variable).

OP also said ‘Interpret "function" in the mathematical sense.’

OP = original poster. The OP did say “given the same input, it must produce the same output”. The id function doesn’t satisfy that.

Also they make no attempt to define the earliest generation on which an escaping pattern is considered to have escaped.

I think they are based on a large database of heuristics that need to be extended when a pattern is found that doesn’t match them.

Given a Turing machine T, one can build a Life pattern that (1) simulates T until it halts, and if so (2) translates itself in some direction and restarts. Then it’s a spaceship iff T halts.

In fact, since one can build Turing machines in life, even the question “is this pattern a spaceship” is undecidable.

Even if it does, I can’t imagine how it could be checked efficiently by a program.

If it does, it depends on a very nonobvious claim that needs to be proved, not just failed-to-be-disproved.

I honestly don’t know whether it does or doesn’t at this point.

The burden is on you to prove that your definition makes sense.

And you probably see why that proof isn’t convincing at all.

Surely you at least understand that there’s a claim here that demands proof.

Well the lowest cell isn’t directly affected by the removal of 1 glider but is affected by the removal of 2. It happens that in your example there are other cells that don’t have that property. But how do you know that in every case (not just this one) there will always be some other cell without that property?

The 3 neighbors in question need not be adjacent to each other.

How do you know that?

Could this be extended from a local observation about one cell to an entire pattern? I don’t know! But that’s the whole point: “I don’t know” is not a good enough foundation for a formal definition.

Imagine there’s an alive cell with 3 neighbors, one of which is part of A and one of which is part of B. If only A is removed, it has 2 neighbors and remains alive. If only B is removed, it has 2 neighbors and remains alive. But if both A and B are removed, it has 1 neighbor and dies.

Think about what you’re saying formally. We have some pattern A + B + C. If “A is a spaceship”, the evolution of B + C is the same as the evolution of A + B + C. If “B is a spaceship”, the evolution of A + C is the same as the evolution of A + B + C. We can make no deductions about the evolution of C itself.

The fact that the evolution of the pattern is unaffected by the removal of B does not imply that the evolution of the pattern minus A is unaffected by the removal of B.

Or vice versa.

Also, one could imagine that there could be two spaceships A and B, such that the pattern is not affected when either one is individually removed, but is affected when they are simultaneously removed.

(Except the width 1025 thing, that is legitimately ambiguous when even speaking informally.)

No I mean I understand what these things are in informal language. But this is a programming problem, we need an exact definition that applies in all cases.

You still haven’t answered where the boundary is placed if a width 1023 pattern grows to width 1025.

You still haven’t defined “spaceship”, “glider”, “*WSS”, and especially “etc.”.

If you wait until everything hits the 1024×1024 boundary, at least you have a chance at defining an objective result. But you do still need to finish defining that boundary. If it’s dynamically placed when the pattern gets big enough, what happens when a width 1023 pattern grows in both directions simultaneously to width 1025? I’d really recommend keeping everything as simple as possible: fix the boundary in place at the start with the initial pattern centered. (And add the guarantee that the initial pattern is 8×8 or at least even×even.) Dealing with the boundary shouldn’t be the hard part.

Your edits say to exclude escaping gliders and spaceships, but now you need to define exactly what gliders and spaceships are and what it means for one to be escaping. That isn’t just nit picking, I’m legitimately not sure how one would define that precisely (much less compute it), especially when taking into account that the potential interaction radius of a glider is larger than the glider itself.

Your reference answers are wrong. The R-pentomino, for example, evolves to a stable configuration plus six gliders at generation 1103. You then need to wait for those gliders to crash into the boundary of the grid before the result is truly stable by your definition. (And you still haven’t told us exactly where the boundary of the grid is?)

@PeterTaylor Indeed, in a world of free arbitrarily fast computation or omniscient mathematicians where we can evaluate all 9.208 · 10^10306 possible test cases, that would be a more precise way to evaluate the score. Lacking easy access to such a world, I see no reason to complain about the present method that uses a Monte Carlo approximation to this ideal. Especially given that the present answers are separated in score by thousands of orders of magnitude and an approximation error of a couple percent won’t make the slightest difference. Come on.

@PeterTaylor If OP gets hit by a bus today, we generate new random test cases and get the same scores (within statistical tolerances), since we know exactly what distribution they’re drawn from. There’s no mystery at all about which objective the challenge asks us to optimize.

@edc65 Er, great! What did I say that was different?

@edc65 Yes. Program A outputs a gigantic number (sure, it could be 26k digits, but the other answers here are a bit more efficient) that encodes, in any way that you choose, enough information about the input (a, b) pairs for program B to be able to recover each b given the corresponding a. How would you prefer for this to be explained?

@PeterTaylor The pretest data is provided with a TIO program that generates uniformly random test cases, and the challenge explains that the hidden test cases are produced by the same generator. It’s clear to me that the objective winning criterion is the smallest expected output integer over that uniform input distribution (and the hidden test cases are just a mechanism to prevent cheating when that is deterministically evaluated).

I don’t know why people are downvoting this, it’s a perfectly fine challenge (despite the outstanding trivial complaint about disallowing 0). But perhaps a little anthropomorphization would help the people who think they don’t understand math: “Alice needs to send 1024 messages, one to each of her 1024 Bots, which are indistinguishable except that each has a unique 32-bit identifier. She wants to do this by encoding them all into a single number, which she wants to make as small as possible…” Or something? I dunno, honestly the math was fine as far as I’m concerned.

@l4m2 For example, 0 0; 1 0; 2 0; 3 0; …; 1023 0.

@l4m2 The other answer has the same issue.

Trivial nitpick: can we change “positive integer” to “nonnegative integer” just so we don’t have to insert adjustments by ±1 to avoid an incredibly unlikely output of 0?

The point stands, though, that you can’t use big O when all the variables are fixed at constants like 250. Sorting a list of N elements: O(N log N). Sorting a list of 250 elements: O(1).

(Conjecturally.)

One of my slow side projects has been to understand arxiv.org/abs/1610.04633, which claims to go beyond the ordinal for Zermelo set theory.

Ah, okay, that would take some work then.

Hmm, perhaps the small Veblen notation from my answer could work for that. I’ll try it later. Thanks!

If you agree that it’s absurd for f_α(n) to terminate with a non-integer result, then you should agree that we’ve reached the desired contradiction in the proof by contradiction.

Hi!

We have shown in PA that this is impossible.

Stepping back to top level: we wish to prove your program doesn’t terminate. Suppose it does terminate. Then it must have broken out of the loop. It only breaks out of the loop it it finds an n such that the evaluation of f_α(n) does terminate, and the result is a non-integer.

Like I said, it doesn’t.