Yesterday I watched CONTACT, a movie about a scientist obsessed about Search for Extra-terrestrial Intelligence (SETI) and contacting some alien in the form of her dead dad on VEGA. The story also has a theologian who is not against Science but questions the privilege that Science gets. There is one line that is very nice. "...Universe is vastly huge...if we are the only ones in this universe..then it's awful waste of space..."
One thing that got my interest is the assumption that our Math is the universal language. Math is certainly standard language of Science on Earth. But why should we assume that it is universal. Even the purest of Mathematics on Earth depends on a set of assumptions like ZFC. What if ZFC is not valid in other parts of the universe? What if axioms of deduction are not valid? Perhaps this might be very important question that people already think about in that field. What might be important for CS on Earth is this. We often believe (for some reason) that aliens must be super intelligent than we are. And if so can they solve NP-Complete problems? Let's say that if they are able to solve then is communicating with them NP-hard? Is this the reason we are not able to communicate with them (if at all they are) in the first place. My conjecture is that the communication is NP-hard since the search space of mapping between their assumptions and our assumptions is close to be unstructured and exponential in size.
BTW it's a good long movie to watch.