## Solution to SETI Puzzle

Gordon Davisson (davisson@milton.u.washington.edu) posted this solution on Sept. 4, 1991. The original puzzle is here.

Here's a full (?) translation. I've reformatted the transmission somewhat for readability -- I turned the X's into line breaks (since they serve as sentence dividers) and M's to "."'s, since they mainly serve as spaces (there are exceptions, as you'll see). I've indented the original message three spaces (where lines were too long I broke them and indented the continuations six spaces). My comments are unindented, and the translations follow each original line separated by tabs.

Counting in unary:

```   ........................
..........S.............
..........SS............
..........SSS...........
..........SSSS..........
..........SSSSS.........
..........SSSSSS........
..........SSSSSSS.......
..........SSSSSSSS......
..........SSSSSSSSS.....
..........SSSSSSSSSS....
..........SSSSSSSSSSS...
..........SSSSSSSSSSSS..

```
"...." means equals or equivalence (I will translate it as "="):
```   .....S..................	0 =
.....L....S.............	1 = I
....LS....SS............	2 = II
....LL....SSS...........	3 = III
...LSS....SSSS..........	4 = IIII
...LSL....SSSSS.........	5 = IIIII
...LLS....SSSSSS........	6 = IIIIII
...LLL....SSSSSSS.......	7 = IIIIIII
..LSSS....SSSSSSSS......	8 = IIIIIIII
..LSSL....SSSSSSSSS.....	9 = IIIIIIIII
..LSLS....SSSSSSSSSS....	10 = IIIIIIIIII
..LSLL....SSSSSSSSSSS...	11 = IIIIIIIIIII
..LLSS....SSSSSSSSSSSS..	12 = IIIIIIIIIIII

```
SSx means a binary number:
```   SSS....	           0 =
SSL....S             1 = I
SSLS....SS           2 = II
SSLL....SSS          3 = III
SSLSS....SSSS        4 = IIII
SSLSL....SSSSS       etc...
SSLLS....SSSSSS
SSLLL....SSSSSSS
SSLSSS....SSSSSSSS
SSLSSL....SSSSSSSSS
SSLSLS....SSSSSSSSSS
SSLSLL....SSSSSSSSSSS
SSLLSS....SSSSSSSSSSSS

```
LLSS is a prefix operator meaning logical or ("|"):
```   LLSS.SSL.SSL....SSL		| 1 1 = 1
LLSS.SSS.SSL....SSL		| 0 1 = 1
LLSS.SSL.SSS....SSL		| 1 0 = 1
LLSS.SSS.SSS....SSS		| 0 0 = 0

```
LLSL means logical and ("&"):
```   LLSL.SSL.SSL....SSL		& 1 1 = 1
LLSL.SSS.SSL....SSS		& 0 1 = 0
LLSL.SSL.SSS....SSS		& 1 0 = 0
LLSL.SSS.SSS....SSS		& 0 0 = 0

```
LLS means logical not ("~"):
```   LLS.SSS....SSL	~ 0 = 1
LLS.SSL....SSS	~ 1 = 0

```
LS is assignment ("->"), SLx is a variable ("vx"):
```   SSS.LS.SLS		0 -> v0

```
Examples of math with variables:
```   LLSS.SLS.SSL....SSL	| v0 1 = 1
LLSS.SLS.SSS....SSS	| v0 0 = 0
LLSL.SLS.SSL....SSS	& v0 1 = 0
LLSL.SLS.SSS....SSS	& v0 0 = 0
LLS.SLS....SSL	~ v0 = 1
SLS....SSS		v0 = 0

```
Examples of assignment:
```   SSL.LS.SLS		1 -> v0
LLSS.SLS.SSL....SSL	| v0 1 = 1
LLSS.SLS.SSS....SSL	| v0 0 = 1
LLSL.SLS.SSL....SSL	& v0 1 = 1
LLSL.SLS.SSS....SSS	& v0 0 = 0
LLS.SLS....SSS	~ v0 = 0
SLS....SSL		v0 = 1

```
Equivalence applies to things besides numbers:
```   LLSS.SSL.SSL.LS.SLS....SSL.LS.SLS	| 1 1 -> v0 = 1 -> v0
LLSS.SSL.SSL.LS.SLS			| 1 1 -> v0
SLS....SSL				v0 = 1

```
LLSSS means logical nor ("~|"):
```   LLSSS.SSL.SSL....SSS		~| 1 1 = 0
LLSSS.SSS.SSL....SSS		~| 0 1 = 0
LLSSS.SSL.SSS....SSS		~| 1 0 = 0
LLSSS.SSS.SSS....SSL		~| 0 0 = 1

```
Assignment is of expressions, not values (actually, it's worse than that' as we'll see later):
```   LLSS.SLS.SLL.LS.SLLS	| v0 v1 -> v2   (they really meant LLSL, &)
LLS.SLLS.LS.SLLL	~ v2 -> v3

SSS.LS.SLS	0 -> v0
SSS.LS.SLL	0 -> v1
SLLS....SSS	v2 = 0
SLLL....SSL	v3 = 1

SSL.LS.SLS	1 -> v0
SLLS....SSS	v2 = 0
SLLL....SSL	v3 = 1

SSS.LS.SLS	0 -> v0
SSL.LS.SLL	1 -> v1
SLLS....SSS	v2 = 0
SLLL....SSL	v3 = 1

SSL.LS.SLS	1 -> v0
SLLS....SSL	v2 = 1
SLLL....SSS	v3 = 0

```
Assignment with no antecedent (clear?) (I don't get this):
```   .LS.SLS	-> v0
.LS.SLL	-> v1

```
Another way of defining nor (in terms of previous defn's of v2 and v3):
```   LLSSS.SLS.SLL....SLLL	~| v0 v1 = v3

```
Here's that defining again, all on one line. ".." is some sort of subsentence divider (I'll use ",") and "..." is some sort of result indicator (I'll use "::"):
```   LLSS.SLS.SLL.LS.SLLS..LLS.SLS.LS.SLLL....LLSSS.SLS.SLL...SLLL
| v0 v1 -> v2 , ~ v0 -> v3 = ~| v0 v1 :: v3

```
And an analogous definition of LLSLS as nand ("~&"):
```   LLSL.SLS.SLL.LS.SLLS..LLS.SLS.LS.SLLL....LLSLS.SLS.SLL...SLLL
& v0 v1 -> v2 , ~ v0 -> v3 = ~& v0 v1 :: v3

```
Truth table for LLSLS (error: the middle two entries are wrong):
```   LLSLS.SSL.SSL....SSS		~& 1 1 = 0
LLSLS.SSL.SSS....SSS		~& 1 0 = 0
LLSLS.SSS.SSL....SSS		~& 0 1 = 0
LLSLS.SSS.SSS....SSL		~& 0 0 = 1

```
LLSSL is exclusive or (defined 2 ways) ("^"):
```   LLSS.SLS.SLL.LS.SLLS..LLSLS.SLS.SLL.LS.SLLL..LLSL.SLLS.SLLL.LS.SLLSS....
LLSSL.SLS.SLL...SLLSS
| v0 v1 -> v2 , ~& v0 v1 -> v3 , & v2 v3 -> v4 =
^ v0 v1 :: v4
LLS.SLS.LS.SLLS..LLS.SLL.LS.SLLL..LLSL.SLS.SLLL.LS.SLLSS..
LLSL.SLL.SLLS.LS.SLLSL..LLSS.SLLSS.SLLSL.LS.SLLLS....
LLSSL.SLS.SLL...SLLLS
~ v0 -> v2 , ~ v1 -> v3 , & v0 v3 -> v4 ,
& v1 v2 -> v5 , | v4 v5 -> v6 =
^ v0 v1 :: v6

```
LLLS is half adder ("^&") -- outputs sum (mod 2) and carry of 2 bits:
```   LLSSL.SLS.SLL.LS.SLLS..LLSL.SLS.SLL.SLLL....LLLS.SLS.SLL...SLLS.SLLL
^ v0 v1 -> v2 , & v0 v1 v3 = ^& v0 v1 :: v2 v3
(error: missing -> between v1 and v3)

```
```   LLLS.SSL.SSL....SSS.SSL	^& 1 1 = 0 1
LLLS.SSS.SSL....SSL.SSS	^& 0 1 = 1 0
LLLS.SSL.SSS....SSL.SSS	^& 1 0 = 1 0
LLLS.SSS.SSS....SSS.SSS	^& 0 0 = 0 0

```
LLLL is a full adder ("#") (# x y cin = z cout):
```   LLLS.SLS.SLL.LS.SLLL.SLLSS..LLLS.SLLS.SLLL.LS.SLLSL.SLLLS..
LLSS.SLLSS.SLLLS.LS.SLLLL....LLLL.SLS.SLL.SLLS...SLLSL.SLLLL
^& v0 v1 -> v3 v4 , ^& v2 v3 -> v5 v6 ,
| v4 v6 -> v7 = # v0 v1 v2 :: v5 v7

```
LLLL can also add 3-bit numbers (# x2 x1 x0 y2 y1 y0 cin = z2 z1 z0 cout):
```   LLLL.SLLS.SLLSL.SLLLS.LS.SLLSSL.SLLSLL..
LLLL.SLL.SLLSS.SLLSLL.LS.SLLSSS.SLLLSS..
LLLL.SLS.SLLL.SLLLSS.LS.SLLLL.SLLSLS....
LLLL.SLS.SLL.SLLS.SLLL.SLLSS.SLLSL.SLLLS...SLLLL.SLLSSS.SLLSSL.SLLSLS
# v2 v5 v6 -> v9 v11 ,
# v1 v4 v11 -> v8 v12 ,
# v0 v3 v12 -> v7 v10 =
# v0 v1 v2 v3 v4 v5 v6 :: v7 v8 v9 v10

```
Example of use on 3-bit numbers:
```   LLLL.SSS.SSL.SSS.SSL.SSL.SSS.SSL....SSS.SSS.SSL.SSL
# 0 1 0 1 1 0 1 = 0 0 1 1
(2 + 6 + carry1 = 1 + carry8)

```
And 4-bit numbers:
```   LLLL.SSL.SSS.SSL.SSS.SSS.SSS.SSL.SSS.SSS....SSL.SSL.SSS.SSS.SSS
# 1 0 1 0 0 0 1 0 0 = 1 1 0 0 0
(10 + 2 + carry0 = 12 + carry0)

```
LLL is an RS flip-flop ("\$") (I *said* it was worse than assignment -- there's state information being stored in there!):
```   LLSSS.SLS.SLLL.LS.SLLS..LLSSS.SLLS.SLL.LS.SLLL....LLL.SLS.SLL...SLLS.SLLL
~| v0 v3 -> v2 , ~| v2 v1 -> v3 = \$ v0 v1 :: v2 v3

```
Set the initial state of the flip-flop:
```   SSL.LS.SLLL	1 -> v3

```
Then demonstrate how to toggle it:
```   LLL.SSS.SSS....SSS.SSL	\$ 0 0 = 0 1
LLL.SSS.SSL....SSL.SSS	\$ 0 1 = 1 0
LLL.SSS.SSS....SSL.SSS	\$ 0 0 = 1 0
LLL.SSL.SSS....SSS.SSL	\$ 1 0 = 0 1
LLL.SSS.SSS....SSS.SSL	\$ 0 0 = 0 1

```
Here we move from logical operations to math...
```   ............

```
LSS is plus ("+") (the're switching from prefix to infix operators here):
```   SSS.LSS.SSLSL....SSLSL	0 + 5 = 5
SSS.LSS.SSLSLLS....SSLSLLS	0 + 22 = 22
SSLSLL.LSS.SSL....SSLLSS	11 + 1 = 12
SSLSSL.LSS.SSL....SSLSLS	9 + 1 = 10
SSLLSLS.LSS.SSL....SSLLSLL	26 + 1 = 27
SSL.LSS.SSLSL....SSLLS	etc...
SSLS.LSS.SSLL....SSLSL
SSLS.LSS.SSLSL....SSLLL
SSLS.LSS.SSLSLS....SSLLSS
SSLLS.LSS.SSLSLS....SSLSSSS
SSLSLL.LSS.SSLSSL....SSLSLSS
SSLSSLS.LSS.SSLSLS....SSLLLSS

```
```   SSS.LSS.SLS....SLS		0 + v0 = v0
SLS.LSS.SLL....SLL.LSS.SLS	v0 + v1 = v1 + v0

```
LSL is minus ("-") (note new use of "..."):
```   SLS.LSL.SLL...SLLS....SLL.LSS.SLLS...SLS
v0 - v1 :: v2 = v1 + v2 :: v0

```
```
```
Examples of minus:
```   .SSLLSS.LSL.SSLSLS....SSLS	12 - 10 = 2
SSLSLSS.LSL.SSLSSL....SSLSLL	20 - 9 = 11
SSLSS.LSL.SSLL....SSL	4 - 3 = 1
SSLS.LSL.SSL....SSL		2 - 1 = 1
SSL.LSL.SSL....SSS		1 - 1 = 0

```
SSSx is a negative number:
```   SSS.LSL.SSL....SSSL		0 - 1 = -1
SSSL.LSL.SSL....SSSLS	-1 - 1 = -2
SSS.LSL.SSLS....SSSLS	0 - 2 = -2
SSSLS.LSL.SSL....SSSLL	-2 - 1 = -3
SSS.LSL.SSLL....SSSLL	0 - 3 = -3
SSS.LSL.SSLSS....SSSLSS	0 - 4 = -4
SSS.LSL.SSLSL....SSSLSL	0 - 5 = -5

```
You too can be a big hero, once you've learned to count backward past zero (with apologies to T. Lehrer):
```   SSLL..SSLS..SSL..SSS..SSSL..SSSLS..SSSLL..
SSSLSS..SSSLSL..SSSLLS..SSSLLL..SSSLSSS
3 , 2 , 1 , 0 , -1 , -2 , -3 ,
-4 , -5 , -6 , -7 , -8

SSLSLL.LSS.SSSLSLL....SSS	11 + -11 = 0

```
The end!

Acknowledgements: Jim Belonis and John Whitmore started this, I just finished it, and documented our work.

Martin C. Martin:  martin at metahuman.org