Let's say we discover alien civilizations that are able to send and receive messages using an interstellar digital communications channel. (Say using modulated radio waves, laser pulses, re-positioning stars in various orbits, what have you.) Let's assume we have decided to make contact with them.

Once we initiate a dialog, how would we go about establishing a communications protocol and language? What methodology would we use to agree on a basic vocabulary and ways of expressing logical ideas? Is it ad-hoc or is there some way to optimize the process of establishing a common language based on symbolic manipulations. We would want to agree on a language quickly and minimize the resources required to encode and send messages (since they're quite slow to send).

Next, reciprocity: Once we have a shared language, how would we make sure that both sides reciprocate in trading secrets? That is, we don't want to be in a situation where we give away valuable technology without receiving anything in return. Can both sides prove that they posses certain technology? Is there a way to send results piecemeal, gradually, so that each side can have increasing confidence in the value of the message?


2 Answers 2


Your first question is the topic of Brendan Juba's PhD thesis on Universal Semantic Communication. You should take a look at it, as well as some of the papers on his website.

As for your second question, you might want to read about zero-knowledge proofs.

  • 1
    $\begingroup$ In the abstract example for zero-knowledge proofs, why didn't Victor just wait at the entrance to the cave to watch Peggy do a full loop? $\endgroup$
    – Mike Cole
    Commented Feb 18, 2011 at 4:31
  • $\begingroup$ @Mike C. If that was the formulation, Victor would be certain that Peggy was not cheating, so the example would not capture the essense of ZK proofs. $\endgroup$
    – chazisop
    Commented Feb 19, 2011 at 10:28
  • $\begingroup$ @chazisop The knowledge lies in the secret word which Peggy knows. And as far as he doesn't know it, there is still ZK. So why not he see which way Peggy takes and then watch her take a full round? $\endgroup$
    – Sai Venkat
    Commented Apr 10, 2011 at 15:40
  • $\begingroup$ It is not the matter of knowledge, it is to allow the prover to cheat. By requiring that Peggy randomly selects a path that Victor does not know, we allow Peggy to pull a trick on the verifier Victor and that Victor is powerful enough as a verifier so he can be tricked with only small probability. $\endgroup$
    – chazisop
    Commented Apr 10, 2011 at 17:05

I have heard that relaying prime numbers is the preferred choice for communication, but I always thought that transmitting fibonacci numbers made much more sense. (After all, how many people on our world would recognize a prime series if they saw it, whereas fibonacci series is more intuitively observable)

  • 1
    $\begingroup$ Maybe aliens taught prime numbers in their kindergarten schools!! $\endgroup$ Commented Feb 18, 2011 at 6:24
  • 2
    $\begingroup$ When I TAed a first year course, the majority of students did not recognize Fibonacci numbers. $\endgroup$
    – Raphael
    Commented Feb 18, 2011 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.