[pavel_lishin]

But any alien that can build a receiver knows math, and understands physics, and probably has come to similar conclusions about computation. They might be so different from us that communication would be impossible, but it's not likely.

If nothing else, you can draw simple two-color pictures by sending pixels in a NxM grid, where N and M are both primes. Enough minds thinking about the problem will eventually figure it out.