<p>Your first question is the topic of Brendan Juba's PhD thesis on <a href="http://people.csail.mit.edu/bjuba/thesis/">Universal Semantic Communication</a>. You should take a look at it, as well as some of the papers on his website.</p>

<p>As for your second question, you might want to read about <a href="http://en.wikipedia.org/wiki/Zero-knowledge_proof">zero-knowledge proofs</a>.</p>

CC BY-SA 2.5
2011-02-18T04:31:42.560Z
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?
Mike Cole
CC BY-SA 2.5
2011-02-19T10:28:37.050Z
@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.
chazisop
CC BY-SA 3.0
2011-04-10T15:40:55.883Z
@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?
Sai Venkat
CC BY-SA 3.0
2011-04-10T17:05:53.167Z
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.
chazisop
CC BY-SA 2.5
2011-02-17T23:39:37.777Z
2011-02-17T23:39:37.777Z
Aaron Roth
<p>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.</p>

<p>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).</p>

<p>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?</p>

<big-picture><communication-complexity>
Best alien communication protocol?
mhadley
# Best alien communication protocol?

(Asked by: username_0 on 2011-02-17)

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?

**Tags:** big-picture, communication-complexity

---

## 1 answers

### Answer by username_1 on 2011-02-17. Score: 14 | Accepted answer

Your first question is the topic of Brendan Juba's PhD thesis on [Universal Semantic Communication](http://people.csail.mit.edu/bjuba/thesis/). 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](http://en.wikipedia.org/wiki/Zero-knowledge_proof).

> **Comments:**
> **username_2**: 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?  
> **username_3**: @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.  
> **username_4**: @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?  
> **username_3**: 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.  

---

