Minos wrote:... could you tell me [how] complicated the algorithms to search patterns (that's the point I'm the most interested in) are, and if you think it is possible for a programming novice to manage to write one simple, basic one ? And what is the most suitable language ?

If you're interested in "simple and basic", and you're working with Golly, then the language of choice is probably Python. Some programmers prefer Perl, but from my experience there's a steeper learning curve there for a beginner. A Python script won't win any prizes for speed, but depending on what you're looking for that may not be a problem.

Here's an example of a search problem that came up for me a few weeks back: the conjecture was that "no 2xN pattern, for finite n, can 'touch' every cell in the plane if left to run indefinitely".

I wrote a Python script to find the pieces I needed for a counterexample -- see below. Maybe you can judge from this whether Golly scripting is something you want to tackle. The short summary is that there are certainly still new results that are within easy reach of simple searches, if you pick your topic carefully.

For the counterexample, I wanted to show that it was possible to glider-construct something like Dean Hickerson's total-periodic or total-aperiodic pattern (see Golly's Patterns/Hashlife/totalperiodic.mc) by crashing together pairs of gliders that were generated indirectly from a 2xN starting pattern.

Hickerson's Life-integer investigations showed that it's possible to construct arbitrarily complex objects from a one-dimensional line of spaceships -- see Golly's Scripts/Python/life-integer-gun30.py . So the first thing to find out was whether 2xN patterns can actually create clean spaceships.

If multiple types and/or phases of spaceships were available, they could probably be crashed together to make as many gliders as might be needed. It's very convenient, though possibly not strictly necessary, to be able to generate gliders with at least two different phases. I didn't make any attempt to come up with the actual glider collisions needed to build Hickerson's total-aperiodic or some equivalent -- that's a fairly minor engineering problem, just very time-consuming.

So I just got to where I could see that a 2xN pattern can construct anything that a Gemini replicator unit can construct... But that's all getting a bit too far from this topic, I think! I stopped running the script when it had produced the following:

`x = 165, y = 2, rule = Life`

o6b3obo5bo5b3obo5bo4b3obo20b2ob8o2b2ob8o16bo4b3obo3bo4b3obo7bob3o4bo

11b8ob2o$b6ob3o7b5ob3o7b4ob3o23b2o3b2o6b2o3b2o19b4ob3o5b4ob3o9b3ob4o

14b2o3b2o!

There were a few more finds -- clean lightweight spaceships at 436729, 436731, 456361, 612087, and 980649, before the odd-phase ones finally showed up at 1496565 and 1562085. A clean MWSS output showed up at 1526447. There were also quite a few false positives, like the "dirty" LWSS outputs at 1378651 and 1504623.

The 2xN MWSS and HWSS recipes shown at left in the above pattern were not found by searching -- I just tried extending the original LWSS recipe by one cell, and it worked...!

Here's what the script looked like by the time it found what I needed:

`import golly as g`

c=1 # edit this number to restart a search after stopping the script --

# I didn't search much past 1562085

g.setrule("Life")

while c:

g.new("test")

x,y,d=0,-1,c

while 1:

y+=1

if y>1:

x+=1

y=0

if d:

state=d%2

d=(d-state)/2 # convert integer d to binary,

g.setcell(x,y,state) # and turn on its ON bits in a two-cell-high strip

else:

break

g.run(1024)

p=int(g.getpop())

if p>0 and p<100: # has to be something there after 1024 ticks, but not too much

r=g.getrect()

g.run(4)

s=g.getrect() # see if the pattern is still moving

if r[1]==s[1] and r[3]==s[3]: # no change in location or width in y direction

if r[0]!=s[0] or r[2]!=s[2]: # change in location or absolute width in x direction

g.fit()

g.update()

g.note(str(c) +": Next?")

c+=2 # only look at every other pattern

# (eventually a reflected/rotated copy of every skipped pattern will be tested)

if c%100==1:

g.show(str(c))

g.update()

I also copied the first part of the code into a separate short script to translate input integers into 2xN patterns. That way I could just write down interesting results as they went by without stopping the search script, and regenerate the patterns later:

`import golly as g`

s=g.getstring("Enter integer to see its equivalent 2xN pattern:")

c=int(s)

g.setrule("LifeHistory")

g.new("test")

x,y,d=0,-1,c

while 1:

y+=1

if y>1:

x+=1

y=0

if d:

state=d%2

d=(d-state)/2

g.setcell(x,y,state)

else:

break

It would have been much more elegant to dump the results to a file, or output them to a new layer in Golly, or in general do everything in a more user-friendly way. But that wasn't the point. I got the search results that I needed, not very efficiently in terms of CPU time but with very minimal programming effort.

I don't think I used any code that would be beyond the reach of a novice... but let me know if you have any questions!