[math-fun] Mathematics of SETI protocols ?
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?
On 31 Oct 2018 at 7:32, Henry Baker wrote:
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.
Yes -- and that's accomplished, from what i can tell from reading some books about it [I'm hopeless with languages], because primarily we are all humans, we have the same body parts, we do the same things [eat, sleep, etc], and by and large share our emotions. And are generally in visual proximity to one another [and so can share the identification, and action with, nearby objects]. Many animals here on earth communicate with one another and we haven't done so well with sorting out their "languages" -- perhaps we should really start seriously with Dolphins and Ravens and.. before we try to communicate with unknown beings.
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*.
Has that worked with any non-human species on earth? Sorry but I'm very skeptical /Bernie\ Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
The movie “Contact” (1997) deals with this, plus lots of drama to make it commercially viable entertainment. The first step is that the signal is bursts of “noise”, clustered in groups of 1, 3, 5, 7, 11, 13, … 137(?) bursts, then repeating. The sequence convinces the team that it’s not a natural phenomenon. Then they discover an old signal from earth embedded, like your idea of playing back part of the other entity’s identifier. Then discovery of how some more images are coded, then how the images go together, etc. Not a lot of math, but… Based on a story “Contact” (1985) by Carl Sagan and Ann Druyan. — Mike On 31 Oct 2018 at 7:32, Henry Baker wrote:
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 ?
I haven't read the book "Contact", but I did see the movie -- good flick! I purposely made a substantive change in the model -- I eliminated the speed-of-light problem for communicating across 10's/100's/millions of light years, and posited short latencies. This is because I suspect that many "rounds" are going to be required to "settle" into some mutually agreed communications protocol. However, all of that cleverness about prime numbers, etc., is useless until you've established more basic communication mechanisms -- e.g., what is the approximate clock rate? What distinguishes *your* signal from everyone else's? For example: if a 21st Century TM wants to communicate with *me*, it has to wait *eons* -- e.g., more than 10^9 cycles -- for any sort of reply. This isn't a latency thing, but a time scale thing. Furthermore, my bit rate is also slower than its own by 10^9, so this TM could probably be simultaneously probing 10^6 or more people for some sort of response. So the first order of business is to establish an appropriate time scale. Ditto if humans wanted to talk with some non-human race: we don't know if their neurons operate in the millisecond range, the nanosecond range, or the century range. Here's a place for math: I said that 1) TM#1 wants to send out a whole bunch of test signals with different clocks and different time-of-day sequences; and 2) TM#1 needs to *remember* all of these signals so that if any of them come back again, TM#1 can recognize them. So an interesting math problem: what kind of data structure could be used to emit a huge number of different types of signals, while simultaneously scanning the channel for delayed copies? It sounds very much like a sort of lossless compressor -- e.g., gzip or equivalent. Of course, gzip assumes that one already knows the appropriate clock signal, while our TM's still don't know these, yet. Better yet would be some sort of sequence which incorporated the appropriate test sequences as subsequences. Perhaps some sort of De Bruijn sequence, which could quickly be indexed upon receipt to figure out when it was sent. At 06:38 PM 10/31/2018, Mike Beeler wrote:
The movie "Contact" (1997) deals with this, plus lots of drama to make it commercially viable entertainment.
The first step is that the signal is bursts of "noise", clustered in groups of 1, 3, 5, 7, 11, 13, Â 137(?) bursts, then repeating.
The sequence convinces the team that it's not a natural phenomenon.
Then they discover an old signal from earth embedded, like your idea of playing back part of the other entityâs identifier.
Then discovery of how some more images are coded, then how the images go together, etc.
Not a lot of math, butÂ
Bassed on a story "Contact" (1985) by Carl Sagan and Ann Druyan.
 Mike
On 31 Oct 2018 at 7:32, Henry Baker wrrote:
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 ?
Hans Freudenthat in 1960 wrote a book to describe such a language: See https://en.wikipedia.org/wiki/Lincos_(artificial_language) On Wed, Oct 31, 2018 at 10:32 AM, Henry Baker <hbaker1@pipeline.com> wrote:
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?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Bernie Cosell -
Henry Baker -
Mike Beeler -
W. Edwin Clark