A civilization has a "magic" computer with memory and processing capacities far beyond what our physics says is possible. They decide to run a massive simulation of Conway's Game of Life with a random "big bang" initial state. The goal is to see if, given enough simulated time steps and a large enough random initial canvas, intelligent life will evolve.
But here's the question: even if intelligent life did evolve, how would the simulator civilization know it was there, when all they (or rather, their algorithms) can see is a semi-chaotic pattern of blinking dots?
Edit: The "life" bit isn't that important; "intelligent non-life" would also work. And the "signs of intelligence" need not be definitive. What sorts of things would scientists (and philosophers) consider when trying to decide if intelligence had arisen? What sorts of debates might they have?
Philosophical digression (trying to provide a substitute for the best of the comments moved to chat)
Skeptic: What is life? What is intelligence? If you will not define these two, your question is unanswerable. [line quoted from user Molot]
Enthusiast: You don't have to define intelligent life to search for signs of it in astronomy. Why should this be any different?
OP: Both points are good. Consider why you think other people have minds (as opposed to being mindless automatons). The most relevant response here is that minds have explanatory power: there are certain actions people take -- such as having discussions about the nature of minds -- that would be absurd if they did not, in fact, have minds. If we were searching for alien intelligence, we would look for signs like buildings or radio message patterns that can most easily be explained by the existence of an alien civilization. In the same way, we can look for patterns in the Game of Life that -- while not violating the rules -- are virtually impossible to imagine without deliberate design.
Skeptic: Where to begin? First of all, postulating intelligence cannot possibly add any explanatory power to what we already have. The Game of Life is deterministic and we know all the rules.
Second, you can't assume intelligence just because you have an elaborate mechanism for accomplishing a purpose. Many things (like eyes) appear to have been designed for a specific purpose, but were in fact produced by natural selection without any actual intent.
OP: Let's take these points one at a time.
Explanatory power in a deterministic system: Consider the laws of statistical mechanics -- most notably entropy. Technically speaking, if you know a physical (Newtonian) system perfectly, the laws of statistical mechanics are completely unnecessary: you can predict exactly where every particle will be after any specified amount of time. But in practice, applying statistical mechanics will allow you to make certain predictions much more cheaply, such as the average velocity of the particles in one particular spot. So statistical mechanics has explanatory power even though in this instance it adds no information.
Enthusiast: I think your criteria for "explanatory power" is still too stringent. Many explanations have no predictive power whatsoever, even in terms of making cheaper predictions. For instance, if (in real life) we received a radio signal that was the first twenty primes repeated over and over, we would probably postulate an intelligent source even though that explanation doesn't really help us predict anything more cheaply.
OP: That's true enough. Cheaper prediction is a nice illustration of explanatory power in the face of determinism, but it's not the whole concept. Like many philosophical ideas, "explanatory power" is precise enough to be useful but vague enough that no two people have exactly the same definition.
Skeptic: How exactly is that useful?
OP: Let's just agree to disagree on the usefulness of imperfectly defined terms. To be considerate of our readers' time--
Skeptic [aside] That ship has sailed.
OP: --let's move on to your second point from earlier.
Designed technology vs evolved organ: Let's remind ourselves of the earlier exchange:
OP: We can look for patterns in the Game of Life that -- while not violating the rules -- are virtually impossible to imagine without deliberate design.
Skeptic: You can't assume intelligence just because you have an elaborate mechanism for accomplishing a purpose. Many things (like eyes) appear to have been designed for a specific purpose, but were in fact produced by natural selection without any actual intent.
That's fair enough. In our own world, certain kinds of patterns -- such as projectiles or wheels -- seem to be exclusively the domain of designed technology rather than evolution. But even in our own universe these distinctions are hardly intuitive, and spotting them in a completely alien universe like Conway's Game of Life would be all but impossible. Perhaps radial propagation of information might be a sign of designed technology? (In the Game of Life, diagonal, vertical, and horizontal movement are much more natural than movement at any other angle; propagating information in all directions at the same rate could be something highly desirable that would never show up "on its own" (without intent), even through evolution. But who knows?)
Another way to think about it is that artifacts designed with intent tend to be good at things that have nothing to do with their own survival. For instance, if we found something in a simulation that appeared to be a program for playing the board game Go exceptionally well, it would certainly be worth publishing as a "sign of intelligence" whether or not the program itself were considered intelligent.
Another thing to look for would be advanced communication -- especially concerning mathematics, since that is universal. But it's also possible that things that are difficult to compute in our universe, typically requiring advanced intelligence, can be done comparatively simply in a GoL universe, and vice versa.
Enthusiast: Perhaps we (or our fictional protagonists) could scan the GoL universe for patterns that obey differential equations! Clearly no differential equations could show up in such a universe without deliberate intent.
OP: Maybe. But differential equations are so powerful I have a feeling they would work their way in just fine without intelligent help.
Anyway, perhaps if we ask on WorldBuilders.SE they'll have some suggestions.