Dover edition of The Recursive Universe (2013)

For general discussion about Conway's Game of Life.
Post Reply
User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 24th, 2019, 5:48 pm

I only noticed recently, but Dover reissued The Recursive Universe with a new afterword by author William Poundstone. It came out in 2013. I wonder how well it has sold. It was one of the books that got me excited about Life when it first came out in the 80s with beautiful pictures of patterns like the p46 glider gun, which I painstakingly entered into an ancient microcomputer by hand. Has anyone else bought it in hardcopy or ebook?

The afterword is quite knowledgeable in summarizing work since the original publication. I am uncertain if Poundstone talked to anyone in the community or just did his own research online. Anyone know?

I thought the above might be of general interest. What follows is personal and rambling, so feel free to stop here.

I was also surprised to see (right above the spacefiller) a 1x39 pattern of 28 cells that grows infinitely. Google books has the page in question. https://books.google.com/books?id=0FHqb ... &q&f=false

I vaguely remembered searching for this pattern (described here) to answer a question posed on the Life mailing list:

Code: Select all

x = 39, y = 1, rule = B3/S23
8ob5o3b3o6b7ob5o!
I gave little thought to this pattern since then, but seeing it by surprise in a Dover publication has made me appreciate it more. I wonder if any other infinite growth patterns are as easy to memorize (at least for those who have trouble memorizing pictures). This one can be summarized as a 9-digit number 815336715, as RLE with the understanding that runs of live and dead cells alternate (and it starts with live cells, naturally). 8 live, gap of 1, 5 live, gap of 3, etc.

For those who want to "amaze your friends" with about as much effort as learning a phone number, you can memorize this and enter it into Golly or other viewer by hand. Or maybe it would work as a bar bet... whoa! infinite growth from one line; challenge anyone else to duplicate the feat. (Sorry that was the rambling part; I used to be able to enter the p30 glider gun by hand fairly fast, but this is an easier trick to teach.)

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Dover edition of The Recursive Universe (2013)

Post by Macbi » January 24th, 2019, 6:07 pm

This 5 by 5 infinite growth is also quite easy to remember:

Code: Select all

x = 5, y = 5, rule = B3/S23
3obo$o$3b2o$b2obo$obobo!

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 24th, 2019, 6:24 pm

Macbi wrote:This 5 by 5 infinite growth is also quite easy to remember:

Code: Select all

x = 5, y = 5, rule = B3/S23
3obo$o$3b2o$b2obo$obobo!
True, the step pattern at the bottom is nice. I am not quite sure how to explain how to memorize it though. Of course, you could serialize it in digits as well once you remember it fits in a 5x5 box.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Dover edition of The Recursive Universe (2013)

Post by Macbi » January 24th, 2019, 6:49 pm

pcallahan wrote:
Macbi wrote:This 5 by 5 infinite growth is also quite easy to remember:

Code: Select all

x = 5, y = 5, rule = B3/S23
3obo$o$3b2o$b2obo$obobo!
True, the step pattern at the bottom is nice. I am not quite sure how to explain how to memorize it though. Of course, you could serialize it in digits as well once you remember it fits in a 5x5 box.
Here's one where you only have to remember six digits rather than nine!

Code: Select all

x = 21, y = 5, rule = B3/S23
ob3obobob3ob3ob3o$obo3bobo3bobobobobo$ob3ob3ob3ob3ob3o$o3bo3bobo5bo3bo
$ob3o3bob3ob3ob3o!
(Due, I think, to Dean Hickerson.)

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 24th, 2019, 6:56 pm

Macbi wrote: Here's one where you only have to remember six digits rather than nine!
Cool! I have never seen that one before.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 24th, 2019, 7:34 pm

Another thought. 815336715 may not be (is probably not) the smallest integer that can be converted into a 1-cell-width pattern that grows infinitely by alternating live and dead cells the same way. I wonder what is.

Any number like this has an odd number of digits and no zeros. It should be pretty easy to do the search, though I don't have any of my old software handy for it.

Oh, and the odd-position digits (counting from 1 and representing live cells) must be >=3 or they can be omitted. This is a silly question, but now I'm a little curious.

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Dover edition of The Recursive Universe (2013)

Post by praosylen » January 24th, 2019, 11:27 pm

pcallahan wrote:Another thought. 815336715 may not be (is probably not) the smallest integer that can be converted into a 1-cell-width pattern that grows infinitely by alternating live and dead cells the same way. I wonder what is.
Well, for starters, 517633518 is a fair amount smaller than its reverse...
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 25th, 2019, 3:50 am

A for awesome wrote: Well, for starters, 517633518 is a fair amount smaller than its reverse...
Good point! I dug up some old code for testing patterns and found this infinite growth pattern:

Code: Select all

x = 48, y = 1, rule = B3/S23
4ob8o7b9o5b8ob5o!
418795815 is a smaller 9 digit number, but sadly I could not find anything with 7 digits, so it is not really an improvement. It is also 48 cells wide compared to 39.

I wonder if I extended the unary encoding to 2xn bounding boxes, i.e. just repeating two identical rows of cells, if I could find something with fewer digits. (A completely pointless exercise, since many of the small infinite growth patterns can be memorized with little effort.)

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 25th, 2019, 11:16 am

And here is another, 523371559 that produces infinite gliders (glider-producing mode of switch engines).

Code: Select all

x = 40, y = 1, rule = B3/S23
5o2b3o3b7ob5o5b9o!
1x40 with 29 cells, so it's a little bigger than the older result. I don't know if this is known or not. I haven't done these kind of searches in 20 years or so, so it's nice to see "bit rot" is not a real thing. My pattern testing code works and I just run it for patterns that don't stabilize population after 30000 steps. I used a short python script to generate the lines of cells:

Code: Select all

import sys

def digits(n, sofar):
   if len(sofar) == n:
     yield sofar
   else:
     for digit in range(3 if len(sofar) % 2 == 0 else 1, 10): 
       sofar.append(digit)
       for res in digits(n, sofar):
         yield res 
       sofar.pop()

for n in range(1, int(sys.argv[1]) + 1, 2):
  for sequence in digits(n, []):
    cells = [("." if i % 2 else "*") * sequence[i] for i in range(len(sequence))]
    print "".join(cells)

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 25th, 2019, 1:11 pm

Cheating a little, since I could not find a 7-digit solution. Because 0 is useless in the original encoding, let's repurpose it to mean 10. There is some precedence for this. Then we get 3508844, as easy to remember as a local phone number (US anyway), a little longer at 42 cells wide, with 25 live cells, which is less than the 29 cells of the 1-cell-width pattern from years back.

Code: Select all

x = 42, y = 1, rule = B3/S23
3o5b10o8b8o4b4o!
Numerology aside, it may be easier to memorize just because it has the repeats 8 live, 8 dead, 4 live, 4 dead.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Dover edition of The Recursive Universe (2013)

Post by dvgrn » January 25th, 2019, 4:05 pm

pcallahan wrote:
Macbi wrote: Here's one where you only have to remember six digits rather than nine!
Cool! I have never seen that one before.
I guess if you missed the brief collaboration in 2007 between Dean Hickerson and Eric Angelini, you wouldn't have run into it. Golly has a script, Lua/life-integer-gun.lua, to write out a 740-digit number in that font that produces a Gosper glider gun, with no leftover junk. See also life-integer-constructions.rle in Golly's Life/Syntheses folder.

The font is just the minimal 5x3 "calculator digits", so there's not a lot of additional memorization work there. But for any of this to work as a bar bet, you'd have to find a bar with a much higher density of Lifenthusiasts among the patrons than I seem to be able to find around here.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 25th, 2019, 4:38 pm

dvgrn wrote:But for any of this to work as a bar bet, you'd have to find a bar with a much higher density of Lifenthusiasts among the patrons than I seem to be able to find around here.
True enough. This is probably not my ticket to fast bucks. The calculator font patterns, though remarkable, have the disadvantage that you'd have to find patrons enthusiastic enough to wait for you to enter in all the cells.

(On second thought, Dean's 154299 has only 60 cells making it reasonably competitive with other small populations.)

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Dover edition of The Recursive Universe (2013)

Post by dvgrn » January 25th, 2019, 5:18 pm

pcallahan wrote:(On second thought, Dean's 154299 has only 60 cells making it reasonably competitive with other small populations.)
Yeah, anything under half a minute should be fine. I got 154299 done in 25 seconds -- draw a 9, copy and paste five times, add and subtract a few cells and you're done.

I don't seem to have a very good spatial memory, so usually I don't try to draw anything freehand more complicated than a figure eight. At one point I did make a point to learn how to draw a loafer from memory, but that was about the limit and I keep forgetting and having to re-learn it.

Words are much easier to store in long-term memory somehow. A big enough incentive would make it possible to write and memorize some horrible piece of rhyming doggerel, where the first letters somehow encode the ON and OFF cells of something big and impressive, like Sir Robin maybe. If you ever strike gold at the Lifenthusiasts' Watering Hole, let me know where it is and I'll come try my luck.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 25th, 2019, 6:29 pm

Hmm... a script to convert any Life pattern to horrible rhyming doggerel. That sounds like a rabbit hole best avoided, but it might be doable.

I find the 5x5 infinite growth pattern easy to remember visually now that Macbi brought it up. http://www.conwaylife.com/patterns/5x5i ... growth.rle It is like a minimalist landscape scene with a mountain on the bottom, sun upper right, and clouds upper left. The 10 cell infinite growth pattern http://www.conwaylife.com/patterns/10ce ... growth.rle seems trickier to me since I tend to shift the spacing between parts (but not too hard).

154299 wins hands down on showmanship (but I kept failing just now because I was omitting the bottom segment from the 9s).

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 25th, 2019, 7:44 pm

One more entry in this fairly pointless contest. 694339 entered as a "square wave" of cells in two rows. It is now down to six digits but still larger than 154299.

Code: Select all

x = 34, y = 2, rule = B3/S23
6o9b4o3b3o$6b9o4b3o3b9o!

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 26th, 2019, 2:01 pm

Another concise infinite-growth (infinite gliders) pattern serializable as digits:

Code: Select all

x = 17, y = 2, rule = B3/S23
5ob2o2b3o$17o!
I would memorize this as 512234, alternating live and dead cells on the top row and filling in the bottom row with all live cells.

It doesn't set any records for population or bounding box, but I wonder if there is a shorter RLE string with infinite growth? "5ob2o2b3o$17o!" is just 14 characters.

I have some more thoughts about "easy to memorize" patterns but I want to do a little more work before I summarize in a new thread.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 26th, 2019, 11:58 pm

I wrote my own script to do 7-segment display patterns and soon found that this has infinite growth:

Code: Select all

x = 21, y = 5, rule = B3/S23
obobob3ob3ob3ob3o$obobobobo3bo3bo3bo$ob3obobo3bob3ob3o$o3bobobo3bo3bob
o$o3bob3o3bob3ob3o!
That is based on 140732, which is smaller than 154299. I wondered if I had the font subtlety wrong (there is the whole question of whether 9 has a bottom segment), but this result from 2009 is reported here.

321928 also has infinite growth.

Code: Select all

x = 23, y = 5, rule = B3/S23
3ob3o3bob3ob3ob3o$2bo3bo3bobobo3bobobo$3ob3o3bob3ob3ob3o$2bobo5bo3bobo
3bobo$3ob3o3bob3ob3ob3o!
As well as 979374.

Code: Select all

x = 23, y = 5, rule = B3/S23
3ob3ob3ob3ob3obobo$obo3bobobo3bo3bobobo$3o3bob3ob3o3bob3o$2bo3bo3bo3bo
3bo3bo$3o3bob3ob3o3bo3bo!

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Dover edition of The Recursive Universe (2013)

Post by pcallahan » January 27th, 2019, 2:15 am

Back when 7-segment displays were standard on calculators, you could get some (expensive special purpose ones) that dealt with hexadecimal numbers and displayed digits a-f, but with lowercase for b and d.

Based on that, we can extend numeric Life patterns to hex and get some five-hex-digit infinite growth patterns:

20Ab1

Code: Select all

x = 19, y = 5, rule = B3/S23
3ob3ob3obo5bo$2bobobobobobo5bo$3obobob3ob3o3bo$o3bobobobobobo3bo$3ob3o
bobob3o3bo!
99bC8

Code: Select all

x = 19, y = 5, rule = B3/S23
3ob3obo3b3ob3o$obobobobo3bo3bobo$3ob3ob3obo3b3o$2bo3bobobobo3bobo$3ob
3ob3ob3ob3o!
b0bCd

Code: Select all

x = 19, y = 5, rule = B3/S23
o3b3obo3b3o3bo$o3bobobo3bo5bo$3obobob3obo3b3o$obobobobobobo3bobo$3ob3o
b3ob3ob3o!
F7663

Code: Select all

x = 19, y = 5, rule = B3/S23
3ob3ob3ob3ob3o$o5bobo3bo5bo$3o3bob3ob3ob3o$o5bobobobobo3bo$o5bob3ob3ob
3o!
The smallest one 20Ab1 is problematic in that you need to leave a 3-column gap before the 1, since it's fixed width, which is how you'd see it on an old calculator. But it might not be the first way you would think of writing it.

My favorite, though it is not the smallest, is b0bCd. Bob CD. Pretty easy to remember and write.

Post Reply