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)

Examples of half adder’s use:

   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

Additive identity and commutivity:

   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

(What is this leading “.”?) (Leading M, that is…)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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s