I've been thinking about the following problem for a while, and hope that others have also.
The problem is: how do you establish communication with someone you don't know, and someone who doesn't speak the same language ?
Somehow, when we are babies, we manage to figure out how to communicate with our parents.
Somehow, when we are travelling, we manage to communicate -- to some extent -- with people who don't speak the same language.
Let's put things into a bit more formal context.
Suppose we have some number of Turing Machines that want to establish communications with one or more other TM's.
Suppose that they all have some sort of shared linear channel -- e.g., audio -- that they can both listen to and send on. This is a *public* channel, so every TM can "listen"/"read" this channel, and with some error probability associated with local conditions and clock differences, get a significant percentage of the bits from the channel.
There is plenty of noise on this channel (the "ether"), so not everything that is being received is necessarily from another TM. There may also be a certain amount of passive echoing, which is caused by the channel itself, and not another TM.
Let's assume that the TM's are close enough that latency isn't a big issue.
Let's assume that the TM's are initially in "similar" states -- i.e., each TM is aware of its own existence, and that there *may* be 1 or more other TM's trying to establish communications with it.
We can't assume that any of the TM's have clocks synchronized with any other TM's.
Each TM can't assume that there is only 1 other TM that wants to establish communication -- i.e., TM#1 may get confused if TM#2 and TM#3 both try to establish communication with TM#1 at the "same" time.
Each TM has its own "identity" in the form of an *independent* (infinite) random stream of bits, so with enough tests, TM#1 can eventually distinguish between TM#2 and TM#3 -- assuming that it can ever get far enough into a communications protocol to perform various tests.
Presumably, TM#1 sends out some sort of message with several parts: a part saying "HI", a part saying "This is a part of my identity XXXXX", and a part indicating "This is my idea of what time it is".
TM#2 somehow has to *parse* this message out of the ether, and figure out that another TM is trying to establish communication, and which part of the message is "HI", which part is the other TM's identity, and which part is the other TM's clock time.
Given the noisy channel, it may take a large number of attempts before any progress is made. Indeed, one aspect of this mental exercise is to determine noise bounds which might preclude ANY communications.
It is my intuition that TM#1, TM#2, etc., can *eventually* -- after some number of "rounds" -- develop good hypotheses about whichever other TM's there are, and develop some number of *shared state* with those other TM's, where "shared state" can be measured in *bits*.
I would imagine that some form of a "monkey see, monkey do" protocol works here. If TM#1 sends out a semi-long message -- say 256 bits -- and it later sees a significant number of those bits again with roughly the same clock frequency -- then either it has simply seen some sort of non-sentient *echo*, or some other TM is repeating those bits as part of *its* reply message. If the number of copied bits is large enough, then the chance that this reply message is random noise is negligible.
So the first order of business for TM#1 is to send out a large number of test messages, with distinguishing subsequences of random bits, and at different clock rates, but *remember them all*, so that when it "sees" some of those same bits coming back, there is some chance that it could be another TM attempting communications.
---
Does any of this discussion ring a bell? Surely, someone must have studied this sort of problem before?
