Reverse rule-finding

For discussion of other cellular automata.
Post Reply
hpstricker
Posts: 5
Joined: April 25th, 2014, 12:43 pm

Reverse rule-finding

Post by hpstricker » April 27th, 2014, 9:08 am

There are 2^18 life-like cellular automata. Let's call such an automaton a "universe", governed by and identified with its rule.

For each (finite) sequence X of patterns (of active cells) there is the set OSCILLATOR(X) of universes in which X is an oscillator (of period |X|).

For each universe A there are minimal sets D of sequences X such that A is in SL(X) and no other universe B is in SL(X) for all X in D.

Such a set D defines the universe A.

It's interesting to find for each universe A a smallest set D of sequences that defines it, "smallest" with respect to

a) the number of sequences
b) the (overall) length of the sequences
c) the (overall) number of active cells involved.

My bunch of questions include:
  • What is the smallest set that defines Conway's Game of Life, i.e. B3/S2,3?
  • Where do I find a discussion of this topic which I'd like to call "reverse rule-finding" (reflecting terms like reverse engineering or reverse mathematics)?
  • Did Conway mention how he found his specific rule (= universe)? Driven by what? (Maybe by some small set of still-lifes and oscillators?)
  • What would/could be gained when going further, e.g. from oscillators to spaceships (= moving oscillators)?

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

Re: Reverse rule-finding

Post by dvgrn » May 2nd, 2014, 1:59 pm

hpstricker wrote:What is the smallest set that defines Conway's Game of Life, i.e. B3/S2,3?
This p9 oscillator might do for a start, though no doubt there's something a little smaller:

Code: Select all

x = 20, y = 11, rule = B3/S23
2o16b2o$bo16bo$bobo12bobo$2b2o12b2o$7bo4bo$5b2ob4ob2o$7bo4bo$2b2o12b2o
$bobo12bobo$bo16bo$2o16b2o!

You're limiting the set of possible universes to only Life-like CAs, so the problem seems to be to find the smallest oscillator that includes all eighteen different neighborhoods by neighbor count -- zero through eight neighbors, for ON cells and for OFF cells. Maybe there are two small oscillators that can combine to give you a defining set, with fewer cells than any single oscillator... but I doubt it: you need a certain minimal size and period to be able to test eight-neighbor birth and survival.

A plain pentadecathlon comes pretty close to meeting your criteria, but there happen not to be any isolated sparks, so you'd have to add another oscillator to distinguish B3/S23 from B3/S023. A HW emulator is also a near miss, but it doesn't test eight-neighbor births, and maybe a few other cases.
hpstricker wrote:Where do I find a discussion of this topic which I'd like to call "reverse rule-finding" (reflecting terms like reverse engineering or reverse mathematics)?
Right here might be about the best you can do...!
hpstricker wrote:Did Conway mention how he found his specific rule (= universe)? Driven by what? (Maybe by some small set of still-lifes and oscillators?)
I don't think Conway did much reverse rule-finding. Standard practice, if there was such a thing, seemed to be to test the behavior of small ominoes in various rules, and see what looked the most promising, according to plausible but fairly arbitrary criteria. From the inaugural Mathematical Games article:
Conway chose his rules carefully, after a long period of experimentation, to meet three desiderata:
  • There should be no initial pattern for which there is a simple proof that the population can grow without limit.
  • There should be initial patterns that apparently do grow without limit.
  • There should be simple initial patterns that grow and change for a considerable period of time before coming to end in three possible ways: fading away completely (from overcrowding or becoming too sparse), settling into a stable configuration that remains unchanged thereafter, or entering an oscillating phase in which they repeat an endless cycle of two or more periods.
In brief, the rules should be such as to make the behavior of the population unpredictable.
hpstricker wrote:What would/could be gained when going further, e.g. from oscillators to spaceships (= moving oscillators)?
Here again you need a certain minimum size and period to test all eighteen neighbor counts. Looks as if any Cordership will serve as a defining set for B3/S23, for example -- whereas even an HWSS is too small (tests S8 but not B8).

User avatar
simsim314
Posts: 1731
Joined: February 10th, 2014, 1:27 pm

Re: Reverse rule-finding

Post by simsim314 » May 4th, 2014, 7:40 am

dvgrn wrote:This p9 oscillator might do for a start, though no doubt there's something a little smaller:
Here is something bigger, but with period 4:

Code: Select all

x = 106, y = 1726, rule = LifeHistory
90.D$97.A$2.2A.A16.2A.A71.A$2.A.2A16.A.2A70.3A$2A4.2A12.2A4.2A$A5.A
13.A5.A$.A5.A13.A5.A$2A4.2A12.2A4.2A67.5A$A5.A13.A5.A67.A.3A.A$.A5.A
13.A5.A66.A.A.A.A$2A4.2A12.2A4.2A65.2A.A.A.2A$A5.A13.A5.A65.A2.2A.2A
2.A$.A5.A13.A5.A64.2A7.2A$2A4.2A12.2A4.2A$2.2A.A16.2A.A$2.A.2A16.A.2A
4$98.A$93.2A.A3.A.2A$93.A9.A$94.2A5.2A$91.3A2.5A2.3A$91.A2.A7.A2.A$
92.2A9.2A76$97.A$2.2A.A15.2A74.A$2.A.2A16.A73.3A$2A4.2A13.A$A5.A14.2A
$.A5.A$2A4.2A13.2A72.5A$A5.A15.A71.A.3A.A$.A5.A13.A72.A.A.A.A$2A4.2A
13.2A70.2A.A.A.2A$A5.A85.A2.2A.2A2.A$.A5.A13.2A69.2A7.2A$2A4.2A14.A$
2.2A.A15.A$2.A.2A15.2A4$98.A$93.2A.A3.A.2A$93.A9.A$90.D3.2A5.2A$91.3A
2.5A2.3A$91.A2.A7.A2.A$92.2A9.2A76$97.A$2.2A.A16.2A.A71.A$2.A.2A16.A.
2A70.3A$2A4.2A18.2A$A5.A19.A$.A5.A19.A$2A4.2A18.2A67.5A$A5.A15.2A.A
68.A.3A.A$.A5.A14.A.2A68.A.A.A.A$2A4.2A12.2A71.2A.A.A.2A$A5.A13.A71.A
2.2A.2A2.A$.A5.A13.A70.2A7.2A$2A4.2A12.2A$2.2A.A16.2A.A$2.A.2A16.A.2A
4$98.A$93.2A.A3.A.2A$93.A9.A$94.2A5.2A$90.D3A2.5A2.3A$91.A2.A7.A2.A$
92.2A9.2A76$97.A$2.2A.A14.2A.A73.A$2.A.2A14.A.2A72.3A$2A4.2A16.2A$A5.
A17.A$.A5.A17.A70.D$2A4.2A16.2A69.5A$A5.A13.2A.A70.A.3A.A$.A5.A12.A.
2A70.A.A.A.A$2A4.2A16.2A67.2A.A.A.2A$A5.A17.A67.A2.2A.2A2.A$.A5.A17.A
66.2A7.2A$2A4.2A16.2A$2.2A.A14.2A.A$2.A.2A14.A.2A4$98.A$93.2A.A3.A.2A
$93.A9.A$94.2A5.2A$91.3A2.5A2.3A$91.A2.A7.A2.A$92.2A9.2A76$97.A$2.2A.
A14.2A3.2A70.A$2.A.2A14.2A3.2A69.3A$2A4.2A$A5.A13.2A3.2A$.A5.A12.A.A.
A.A$2A4.2A14.A.A70.5A$A5.A14.2A.A69.A.3A.A$.A5.A17.2A67.A.A.A.A$2A4.
2A18.A66.2A.A.A.2A$A5.A18.A66.A2.2A.2A2.A$.A5.A17.2A65.2A7.2A$2A4.2A
18.A$2.2A.A19.A$2.A.2A19.2A4$98.A$93.2A.A3.A.2A$93.A9.A$92.D.2A5.2A$
91.3A2.5A2.3A$91.A2.A7.A2.A$92.2A9.2A76$97.A$2.2A.A16.2A.A71.A$2.A.2A
16.A.2A70.3A$2A4.2A12.2A$A5.A13.A$.A5.A13.A$2A4.2A12.2A73.5A$A5.A15.
2A.A68.A.3A.A$.A5.A14.A.2A68.A.A.A.A$2A4.2A18.2A65.2A.A.A.2A$A5.A19.A
65.AD.2A.2A2.A$.A5.A19.A64.2A7.2A$2A4.2A18.2A$2.2A.A16.2A.A$2.A.2A16.
A.2A4$98.A$93.2A.A3.A.2A$93.A9.A$94.2A5.2A$91.3A2.5A2.3A$91.A2.A7.A2.
A$92.2A9.2A76$97.A$2.2A.A16.2A.A71.A$2.A.2A16.A.2A70.3A$2A4.2A12.2A$A
5.A13.A$.A5.A13.A$2A4.2A12.2A73.5A$A5.A15.2A.A68.A.3A.A$.A5.A14.A.2A
68.A.A.A.A$2A4.2A12.2A4.2A65.2A.A.A.2A$A5.A13.A5.A65.A2.2A.2A2.A$.A5.
A13.A5.A64.2A7.2A$2A4.2A12.2A4.2A$2.2A.A16.2A.A$2.A.2A16.A.2A4$98.A$
93.2A.A3.A.2A$93.A9.A$94.2A5.2A$91.3A2.5A2.3A$91.AD.A7.A2.A$92.2A9.2A
76$97.A$2.2A.A14.A.2A73.A$2.A.2A14.2A.A72.3A$2A4.2A16.2A$A5.A18.A$.A
5.A16.A$2A4.2A16.2A69.5A$A5.A15.2A70.A.3A.A$.A5.A15.A70.A.ADA.A$2A4.
2A14.A70.2A.A.A.2A$A5.A15.2A68.A2.2A.2A2.A$.A5.A12.2A70.2A7.2A$2A4.2A
13.A$2.2A.A14.A$2.A.2A14.2A4$98.A$93.2A.A3.A.2A$93.A9.A$94.2A5.2A$91.
3A2.5A2.3A$91.A2.A7.A2.A$92.2A9.2A77$2.2A.A16.2A.A71.A$2.A.2A16.A.2A
70.3A$2A4.2A12.2A4.2A68.3A$A5.A13.A5.A69.ADA$.A5.A13.A5.A68.3A$2A4.2A
12.2A4.2A67.5A$A5.A15.2A.A68.A5.A$.A5.A14.A.2A68.A5.A$2A4.2A12.2A4.2A
65.2A.A.A.2A$A5.A13.A5.A65.A2.2A.2A2.A$.A5.A13.A5.A64.2A7.2A$2A4.2A
12.2A4.2A$2.2A.A16.2A.A$2.A.2A16.A.2A5$93.2A7.2A$93.A2.5A2.A$94.2A5.
2A$91.3A9.3A$91.A2.A.A3.A.A2.A$92.2A4.A4.2A76$97.A$.2A19.2A.A71.A$2.A
19.A.2A70.3A$.A18.2A4.2A$.2A17.A5.A$21.A5.A$.2A17.2A4.2A67.5A$2.A17.A
5.A67.A.3A.A$.A19.A5.A66.A.A.A.A$.2A17.2A4.2A65.2A.A.A.2A$20.A5.A65.A
2.2A.2A2.A$.2A18.A5.A64.2A7.2A$2.A17.2A4.2A$.A20.2A.A$.2A19.A.2A4$98.
A$93.2A.C3.A.2A$93.A9.A$94.2A5.2A$91.3A2.5A2.3A$91.A2.A7.A2.A$92.2A9.
2A76$97.C$.2A18.2A74.A$2.A19.A73.3A$.A19.A$.2A18.2A2$.2A18.2A72.5A$2.
A19.A71.A.3A.A$.A19.A72.A.A.A.A$.2A18.2A70.2A.A.A.2A$92.A2.2A.2A2.A$.
2A18.2A69.2A7.2A$2.A19.A$.A19.A$.2A18.2A4$98.A$93.2A.A3.A.2A$93.A9.A$
94.2A5.2A$91.3A2.5A2.3A$91.A2.A7.A2.A$92.2A9.2A76$97.A$.2A19.2A.A71.A
$2.A19.A.2A70.3A$.A24.2A$.2A23.A$27.A$.2A23.2A67.5A$2.A19.2A.A68.A.3A
.A$.A20.A.2A68.A.A.A.A$.2A17.2A71.2A.A.A.2A$20.A71.A2.2A.2A2.A$.2A18.
A70.2A7.2A$2.A17.2A$.A20.2A.A$.2A19.A.2A4$98.A$93.2A.A3.A.2A$93.A9.A$
94.2A5.2A$91.C2A2.5A2.3A$91.A2.A7.A2.A$92.2A9.2A76$97.A$.2A17.2A.A73.
A$2.A17.A.2A72.3A$.A22.2A$.2A21.A$25.A$.2A21.2A69.5A$2.A17.2A.A70.A.
3A.A$.A18.A.2A70.A.A.A.A$.2A21.2A67.2A.A.A.2A$24.A67.A2.2A.2A2.A$.2A
22.A66.2A7.2A$2.A21.2A$.A18.2A.A$.2A17.A.2A4$98.A$93.2A.A3.A.2A$93.A
9.A$94.2A5.2A$91.3A2.5A2.3A$91.C2.A7.A2.A$92.2A9.2A76$97.A$.2A17.2A3.
2A70.A$2.A17.2A3.2A69.3A$.A$.2A17.2A3.2A$20.A.A.A.A$.2A19.A.A70.AC3A$
2.A18.2A.A69.A.3A.A$.A23.2A67.A.A.A.A$.2A23.A66.2A.A.A.2A$25.A66.A2.
2A.2A2.A$.2A22.2A65.2A7.2A$2.A23.A$.A23.A$.2A22.2A4$98.A$93.2A.A3.A.
2A$93.A9.A$94.2A5.2A$91.3A2.5A2.3A$91.A2.A7.A2.A$92.2A9.2A76$97.A$.2A
19.2A.A71.A$2.A19.A.2A70.3A$.A18.2A$.2A17.A$21.A$.2A17.2A73.5A$2.A19.
2A.A68.A.C2A.A$.A20.A.2A68.A.A.A.A$.2A23.2A65.2A.A.A.2A$26.A65.A2.2A.
2A2.A$.2A24.A64.2A7.2A$2.A23.2A$.A20.2A.A$.2A19.A.2A4$98.A$93.2A.A3.A
.2A$93.A9.A$94.2A5.2A$91.3A2.5A2.3A$91.A2.A7.A2.A$92.2A9.2A77$.2A19.
2A.A71.A$2.A19.A.2A70.ACA$.A18.2A74.3A$.2A17.A75.A.A$21.A74.3A$.2A17.
2A73.5A$2.A19.2A.A68.A5.A$.A20.A.2A68.A5.A$.2A17.2A4.2A65.2A.A.A.2A$
20.A5.A65.A2.2A.2A2.A$.2A18.A5.A64.2A7.2A$2.A17.2A4.2A$.A20.2A.A$.2A
19.A.2A5$93.2A7.2A$93.A2.5A2.A$94.2A5.2A$91.3A9.3A$91.A2.A.A3.A.A2.A$
92.2A4.A4.2A76$97.A$.2A17.A.2A73.A$2.A17.2A.A72.3A$.A22.2A$.2A22.A$
24.A$.2A21.2A69.5A$2.A19.2A70.A.ACA.A$.A21.A70.A.A.A.A$.2A19.A70.2A.A
.A.2A$22.2A68.A2.2A.2A2.A$.2A17.2A70.2A7.2A$2.A18.A$.A18.A$.2A17.2A4$
98.A$93.2A.A3.A.2A$93.A9.A$94.2A5.2A$91.3A2.5A2.3A$91.A2.A7.A2.A$92.
2A9.2A77$.2A19.2A.A$2.A19.A.2A70.3A$.A18.2A4.2A69.A$.2A17.A5.A$21.A5.
A68.3A$.2A17.2A4.2A67.A3.A$2.A19.2A.A68.A5.A$.A20.A.2A68.A.A.A.A$.2A
17.2A4.2A65.2A.A.A.2A$20.A5.A65.A2.2A.2A2.A$.2A18.A5.A64.2A7.2A$2.A
17.2A4.2A$.A20.2A.A$.2A19.A.2A5$93.2A7.2A$93.A9.A$94.9A$91.3A2.2AC2A
2.3A$91.A2.A2.3A2.A2.A$92.2A9.2A!

I also wrote a script that generates report of all the existing "totalistic states" of an oscillator.

Code: Select all

import golly as g 
from glife.text import *

iters = int(g.getstring("Insert number of Generations"))

def GetType(x, y):
	c = g.getcell(x, y)
	
	total = 0 
	
	for i in xrange(-1, 2):
		for j in xrange(-1, 2):
			total += g.getcell(x + i, y + j)
		
	if c == 0:
		return total
	else: 
		return total + 8
	
def GetAllTypes():
	global curTypes
	global curData
	
	rect = g.getrect()
	minx = rect[0] - 1
	maxx = rect[0] + rect[2] + 1
	
	miny = rect[1] - 1
	maxy = rect[1] + rect[3] + 1
	
	for x in xrange(minx, maxx + 1):
		for y in xrange(miny, maxy + 1):
			if not GetType(x, y) in curTypes:
				curTypes.append(GetType(x, y))
				curData.append([GetType(x, y), (x, y), g.getcells(rect)])
				
curTypes = []
curData = []

for i in xrange(0, iters): 
	GetAllTypes()
	
	if len(curTypes) == 18: 
		break

	g.run(1)
				
idx = 0 


g.new("")
g.setrule("LifeHistory")

curData = sorted(curData, key=lambda d: d[0]) 

for d in curData: 

	if d[0] < 9: 
		onCell = make_text("0")
		val = make_text(str(d[0]))
	else:
		onCell = make_text("1")
		val = make_text(str(d[0] - 9))
	
	
	g.putcells(onCell, -90, idx * 100 + 15)
	g.putcells(val, -70, idx * 100 + 15)
	
	g.putcells(d[2], 0, idx * 100)
	
	if d[0] < 9: 
		g.setcell(d[1][0], d[1][1] + idx * 100, 4)
	else:
		g.setcell(d[1][0], d[1][1] + idx * 100, 3)
	
	idx += 1
The initial pattern should be in Life rule, and in the start you enter the number of generation you want to check (the period). Then you get an output in LifeHistory rule.

EDIT Here is something that looks a bit smaller than the previous p9. although it's not obviously smaller, because the "size" of an oscillator is ill defined.

Code: Select all

x = 104, y = 1715, rule = LifeHistory
2.2A.A16.2A.A$2.A.2A16.A.2A63.D$2A4.2A12.2A4.2A64.2A6.2A$A5.A13.A5.A
64.A2.A4.A2.A$.A5.A13.A5.A62.6A2.6A$2A4.2A12.2A4.2A63.A2.A4.A2.A$A5.A
13.A5.A65.2A6.2A$.A5.A13.A5.A$2A4.2A12.2A4.2A$A5.A13.A5.A74.2A$.A5.A
13.A5.A72.A.A$2A4.2A12.2A4.2A$2.2A.A16.2A.A72.A.A$2.A.2A16.A.2A71.A$
97.2A86$2.2A.A15.2A$2.A.2A16.A$2A4.2A13.A70.2A6.2A$A5.A14.2A66.D.A2.A
4.A2.A$.A5.A82.6A2.6A$2A4.2A13.2A68.A2.A4.A2.A$A5.A15.A69.2A6.2A$.A5.
A13.A$2A4.2A13.2A$A5.A94.2A$.A5.A13.2A77.A.A$2A4.2A14.A$2.2A.A15.A76.
A.A$2.A.2A15.2A74.A$97.2A86$2.2A.A16.2A.A$2.A.2A16.A.2A$2A4.2A18.2A
63.D2A6.2A$A5.A19.A64.A2.A4.A2.A$.A5.A19.A62.6A2.6A$2A4.2A18.2A63.A2.
A4.A2.A$A5.A15.2A.A66.2A6.2A$.A5.A14.A.2A$2A4.2A12.2A$A5.A13.A80.2A$.
A5.A13.A78.A.A$2A4.2A12.2A$2.2A.A16.2A.A72.A.A$2.A.2A16.A.2A71.A$97.
2A86$2.2A.A14.2A.A$2.A.2A14.A.2A$2A4.2A16.2A66.2A6.2A$A5.A17.A65.DA2.
A4.A2.A$.A5.A17.A64.6A2.6A$2A4.2A16.2A65.A2.A4.A2.A$A5.A13.2A.A68.2A
6.2A$.A5.A12.A.2A$2A4.2A16.2A$A5.A17.A76.2A$.A5.A17.A74.A.A$2A4.2A16.
2A$2.2A.A14.2A.A74.A.A$2.A.2A14.A.2A73.A$97.2A86$2.2A.A14.2A3.2A$2.A.
2A14.2A3.2A$2A4.2A84.2A6.2A$A5.A13.2A3.2A64.A2.A4.A2.A$.A5.A12.A.A.A.
A63.6A2.6A$2A4.2A14.A.A66.A2.A4.A2.A$A5.A14.2A.A67.2A6.2A$.A5.A17.2A$
2A4.2A18.A$A5.A18.A75.2A$.A5.A17.2A73.A.A$2A4.2A18.A$2.2A.A19.A72.A.A
$2.A.2A19.2A70.AD$97.2A86$2.2A.A16.2A.A$2.A.2A16.A.2A$2A4.2A12.2A$A5.
A13.A70.A2.A.2A.A2.A$.A5.A13.A68.2A2.AD3.A2.2A$2A4.2A12.2A69.A2.A.2A.
A2.A$A5.A15.2A.A$.A5.A14.A.2A$2A4.2A18.2A$A5.A19.A74.2A$.A5.A19.A72.A
.A$2A4.2A18.2A$2.2A.A16.2A.A72.A.A$2.A.2A16.A.2A71.A$97.2A86$2.2A.A
16.2A.A$2.A.2A16.A.2A$2A4.2A12.2A70.2A6.2A$A5.A13.A70.AD.A4.A2.A$.A5.
A13.A68.6A2.6A$2A4.2A12.2A69.A2.A4.A2.A$A5.A15.2A.A66.2A6.2A$.A5.A14.
A.2A$2A4.2A12.2A4.2A$A5.A13.A5.A74.2A$.A5.A13.A5.A72.A.A$2A4.2A12.2A
4.2A$2.2A.A16.2A.A72.A.A$2.A.2A16.A.2A71.A$97.2A86$2.2A.A14.A.2A$2.A.
2A14.2A.A71.4A$2A4.2A16.2A68.6A$A5.A18.A67.8A$.A5.A16.A67.2AD5.2A$2A
4.2A16.2A67.8A$A5.A15.2A70.6A$.A5.A15.A71.4A$2A4.2A14.A$A5.A15.2A77.
2A$.A5.A12.2A80.A$2A4.2A13.A77.A.A$2.2A.A14.A$2.A.2A14.2A75.A.A$97.2A
86$2.2A.A16.2A.A$2.A.2A16.A.2A$2A4.2A12.2A4.2A$A5.A13.A5.A66.8A$.A5.A
13.A5.A65.AD4A.A$2A4.2A12.2A4.2A65.8A$A5.A15.2A.A$.A5.A14.A.2A$2A4.2A
12.2A4.2A$A5.A13.A5.A74.2A$.A5.A13.A5.A74.A$2A4.2A12.2A4.2A71.A.A$2.
2A.A16.2A.A$2.A.2A16.A.2A71.A.A$97.2A86$.2A19.2A.A$2.A19.A.2A$.A18.2A
4.2A64.2A6.2A$.2A17.A5.A64.A2.A4.A2.A$21.A5.A62.6A2.6A$.2A17.2A4.2A
63.A2.A4.A2.A$2.A17.A5.A65.2A6.2A$.A19.A5.A$.2A17.2A4.2A$20.A5.A74.2A
$.2A18.A5.A72.A.A$2.A17.2A4.2A$.A20.2A.A72.A.C$.2A19.A.2A71.A$97.2A
86$.2A18.2A$2.A19.A$.A19.A70.2A6.2A$.2A18.2A68.A2.A4.A2.A$90.6A2.6A$.
2A18.2A68.A2.A4.A2.A$2.A19.A69.2A6.2A$.A19.A$.2A18.2A$101.2A$.2A18.2A
77.A.A$2.A19.A$.A19.A76.C.A$.2A18.2A74.A$97.2A86$.2A19.2A.A$2.A19.A.
2A$.A24.2A64.CA6.2A$.2A23.A64.A2.A4.A2.A$27.A62.6A2.6A$.2A23.2A63.A2.
A4.A2.A$2.A19.2A.A66.2A6.2A$.A20.A.2A$.2A17.2A$20.A80.2A$.2A18.A78.A.
A$2.A17.2A$.A20.2A.A72.A.A$.2A19.A.2A71.A$97.2A86$.2A17.2A.A$2.A17.A.
2A$.A22.2A66.2A6.2A$.2A21.A66.A2.A4.A2.A$25.A64.C5A2.6A$.2A21.2A65.A
2.A4.A2.A$2.A17.2A.A68.2A6.2A$.A18.A.2A$.2A21.2A$24.A76.2A$.2A22.A74.
A.A$2.A21.2A$.A18.2A.A74.A.A$.2A17.A.2A73.A$97.2A86$.2A17.2A3.2A$2.A
17.2A3.2A$.A90.2A6.2A$.2A17.2A3.2A64.C2.A4.A2.A$20.A.A.A.A63.6A2.6A$.
2A19.A.A66.A2.A4.A2.A$2.A18.2A.A67.2A6.2A$.A23.2A$.2A23.A$25.A75.2A$.
2A22.2A73.A.A$2.A23.A$.A23.A72.A.A$.2A22.2A70.A$97.2A86$.2A19.2A.A$2.
A19.A.2A$.A18.2A$.2A17.A70.A2.A.2A.A2.A$21.A69.4A.CA.4A$.2A17.2A69.A
2.A.2A.A2.A$2.A19.2A.A$.A20.A.2A$.2A23.2A$26.A74.2A$.2A24.A74.A$2.A
23.2A71.A.A$.A20.2A.A$.2A19.A.2A71.A.A$97.2A86$.2A19.2A.A$2.A19.A.2A$
.A18.2A$.2A17.A69.2A3.A2.A3.2A$21.A68.AC3A4.5A$.2A17.2A68.2A3.A2.A3.
2A$2.A19.2A.A$.A20.A.2A$.2A17.2A4.2A$20.A5.A74.2A$.2A18.A5.A74.A$2.A
17.2A4.2A71.A.A$.A20.2A.A$.2A19.A.2A71.A.A$97.2A86$.2A17.A.2A$2.A17.
2A.A$.A22.2A$.2A22.A67.8A$24.A68.A.C3A.A$.2A21.2A67.8A$2.A19.2A$.A21.
A$.2A19.A$22.2A77.2A$.2A17.2A80.A$2.A18.A77.A.A$.A18.A$.2A17.2A75.A.A
$97.2A86$.2A19.2A.A$2.A19.A.2A$.A18.2A4.2A$.2A17.A5.A66.8A$21.A5.A65.
A.AC2A.A$.2A17.2A4.2A65.8A$2.A19.2A.A$.A20.A.2A$.2A17.2A4.2A$20.A5.A
74.2A$.2A18.A5.A74.A$2.A17.2A4.2A71.A.A$.A20.2A.A$.2A19.A.2A71.A.A$
97.2A!

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

Re: Reverse rule-finding

Post by dvgrn » May 5th, 2014, 2:24 am

simsim314 wrote:EDIT Here is something that looks a bit smaller than the previous p9. although it's not obviously smaller, because the "size" of an oscillator is ill defined.
Seems pretty clear that this is two separate objects, pentadecathlon and barberpole, with the barberpole only needed to take care of the (1 0) case -- the pentadecathlon can do the rest. So does a one-object "B3S23-sufficient" set beat a two-object set, or is the lowest total number of ON cells the winner, or what? This game needs clearer rules...!

Here are slightly larger B3S23-sufficient composite oscillators, period 15 and 60, that are unambiguously one object -- there's at least one cell that doesn't turn on if you remove one of the component oscillators:

Code: Select all

#C three singleton B3S23-sufficient oscillators
#C 25, 26 and 29 ON cells minimum
x = 95, y = 14, rule = LifeHistory
4.2A$3.A2.A26.2A$.A2.A.A25.A2.A$A4.A27.A.A$A30.2A.A$2.3A26.3A$31.2A$
4.D29.D52.A4.A$76.2A7.2A.4A.2A$77.2A8.A4.A$76.A$2.A4.A24.A4.A24.A4.A$
2A.4A.2A20.2A.4A.2A20.2A.4A.2A$2.A4.A24.A4.A24.A4.A!
Probably an exhaustive search through H. Koenig's object database would turn up various B3S23-sufficient oscillators with shorter periods, or smaller bounding boxes, or lower minimum populations -- but I don't know about all three at once.

User avatar
simsim314
Posts: 1731
Joined: February 10th, 2014, 1:27 pm

Re: Reverse rule-finding

Post by simsim314 » May 5th, 2014, 4:04 am

dvgrn wrote: or is the lowest total number of ON cells the winner, or what? This game needs clearer rules...!
I was also thinking of "largest bounding box", or LifeHistory "trace" ON cells, or LifeHistory trace bounding box, while the size of bounding box is also ill defined. Also number of ON cells in the whole oscillation counting each generation separately (obviously p4 oscillators will be larger because they have less "options" then p60 oscillator).

Anyway this problem is not so "critical", so I don't think it's worth so intense investigation.

I was also thinking of other interpretation: what is the state with the smallest number of ON cells, which next generation will define uniquely one of 2^18 possibilities of totalistic rules. I.e. a single state that has all the 18 options inside it in single generation.

Here is 25 cells example:

Code: Select all

x = 88, y = 1716, rule = LifeHistory
79.D$86.A$2.2A.A16.2A.A54.5A$2.A.2A16.A.2A54.A.5A$2A4.2A12.2A4.2A52.
5A.2A$A5.A13.A5.A57.2A$.A5.A13.A5.A56.4A$2A4.2A12.2A4.2A$A5.A13.A5.A$
.A5.A13.A5.A$2A4.2A12.2A4.2A$A5.A13.A5.A$.A5.A13.A5.A$2A4.2A12.2A4.2A
$2.2A.A16.2A.A$2.A.2A16.A.2A86$79.D6.A$2.2A.A15.2A57.5A$2.A.2A16.A57.
A.5A$2A4.2A13.A58.5A.2A$A5.A14.2A61.2A$.A5.A76.4A$2A4.2A13.2A$A5.A15.
A$.A5.A13.A$2A4.2A13.2A$A5.A$.A5.A13.2A$2A4.2A14.A$2.2A.A15.A$2.A.2A
15.2A86$86.A$2.2A.A16.2A.A53.D5A$2.A.2A16.A.2A54.A.5A$2A4.2A18.2A52.
5A.2A$A5.A19.A57.2A$.A5.A19.A56.4A$2A4.2A18.2A$A5.A15.2A.A$.A5.A14.A.
2A$2A4.2A12.2A$A5.A13.A$.A5.A13.A$2A4.2A12.2A$2.2A.A16.2A.A$2.A.2A16.
A.2A86$86.A$2.2A.A14.2A.A56.5A$2.A.2A14.A.2A55.DA.5A$2A4.2A16.2A54.5A
.2A$A5.A17.A59.2A$.A5.A17.A58.4A$2A4.2A16.2A$A5.A13.2A.A$.A5.A12.A.2A
$2A4.2A16.2A$A5.A17.A$.A5.A17.A$2A4.2A16.2A$2.2A.A14.2A.A$2.A.2A14.A.
2A86$86.A$2.2A.A14.2A3.2A53.5A$2.A.2A14.2A3.2A53.A.5A$2A4.2A72.5A.2A$
A5.A13.2A3.2A57.2A.D$.A5.A12.A.A.A.A57.4A$2A4.2A14.A.A$A5.A14.2A.A$.A
5.A17.2A$2A4.2A18.A$A5.A18.A$.A5.A17.2A$2A4.2A18.A$2.2A.A19.A$2.A.2A
19.2A86$86.A$2.2A.A16.2A.A54.5A$2.A.2A16.A.2A54.A.5A$2A4.2A12.2A58.5A
.2A$A5.A13.A62.D2A$.A5.A13.A62.4A$2A4.2A12.2A$A5.A15.2A.A$.A5.A14.A.
2A$2A4.2A18.2A$A5.A19.A$.A5.A19.A$2A4.2A18.2A$2.2A.A16.2A.A$2.A.2A16.
A.2A86$86.A$2.2A.A16.2A.A54.5A$2.A.2A16.A.2A54.A.5A$2A4.2A12.2A58.5A.
2A$A5.A13.A63.2AD$.A5.A13.A62.4A$2A4.2A12.2A$A5.A15.2A.A$.A5.A14.A.2A
$2A4.2A12.2A4.2A$A5.A13.A5.A$.A5.A13.A5.A$2A4.2A12.2A4.2A$2.2A.A16.2A
.A$2.A.2A16.A.2A86$86.A$2.2A.A14.A.2A56.5A$2.A.2A14.2A.A56.A.5A$2A4.
2A16.2A54.5AD2A$A5.A18.A58.2A$.A5.A16.A59.4A$2A4.2A16.2A$A5.A15.2A$.A
5.A15.A$2A4.2A14.A$A5.A15.2A$.A5.A12.2A$2A4.2A13.A$2.2A.A14.A$2.A.2A
14.2A86$86.A$2.2A.A16.2A.A54.5A$2.A.2A16.A.2A54.AD5A$2A4.2A12.2A4.2A
52.5A.2A$A5.A13.A5.A57.2A$.A5.A13.A5.A56.4A$2A4.2A12.2A4.2A$A5.A15.2A
.A$.A5.A14.A.2A$2A4.2A12.2A4.2A$A5.A13.A5.A$.A5.A13.A5.A$2A4.2A12.2A
4.2A$2.2A.A16.2A.A$2.A.2A16.A.2A86$86.C$.2A19.2A.A54.5A$2.A19.A.2A54.
A.5A$.A18.2A4.2A52.5A.2A$.2A17.A5.A57.2A$21.A5.A56.4A$.2A17.2A4.2A$2.
A17.A5.A$.A19.A5.A$.2A17.2A4.2A$20.A5.A$.2A18.A5.A$2.A17.2A4.2A$.A20.
2A.A$.2A19.A.2A86$86.A$.2A18.2A57.5A$2.A19.A57.A.5A$.A19.A58.5A.2A$.
2A18.2A61.2A$84.3AC$.2A18.2A$2.A19.A$.A19.A$.2A18.2A2$.2A18.2A$2.A19.
A$.A19.A$.2A18.2A86$86.A$.2A19.2A.A54.C4A$2.A19.A.2A54.A.5A$.A24.2A
52.5A.2A$.2A23.A57.2A$27.A56.4A$.2A23.2A$2.A19.2A.A$.A20.A.2A$.2A17.
2A$20.A$.2A18.A$2.A17.2A$.A20.2A.A$.2A19.A.2A86$86.A$.2A17.2A.A56.5A$
2.A17.A.2A56.A.5A$.A22.2A54.5A.2A$.2A21.A59.2A$25.A58.C3A$.2A21.2A$2.
A17.2A.A$.A18.A.2A$.2A21.2A$24.A$.2A22.A$2.A21.2A$.A18.2A.A$.2A17.A.
2A86$86.A$.2A17.2A3.2A53.5A$2.A17.2A3.2A53.C.5A$.A78.5A.2A$.2A17.2A3.
2A57.2A$20.A.A.A.A57.4A$.2A19.A.A$2.A18.2A.A$.A23.2A$.2A23.A$25.A$.2A
22.2A$2.A23.A$.A23.A$.2A22.2A86$86.A$.2A19.2A.A54.3ACA$2.A19.A.2A54.A
.5A$.A18.2A58.5A.2A$.2A17.A63.2A$21.A62.4A$.2A17.2A$2.A19.2A.A$.A20.A
.2A$.2A23.2A$26.A$.2A24.A$2.A23.2A$.A20.2A.A$.2A19.A.2A86$86.A$.2A19.
2A.A54.5A$2.A19.A.2A54.A.5A$.A18.2A58.3ACA.2A$.2A17.A63.2A$21.A62.4A$
.2A17.2A$2.A19.2A.A$.A20.A.2A$.2A17.2A4.2A$20.A5.A$.2A18.A5.A$2.A17.
2A4.2A$.A20.2A.A$.2A19.A.2A86$86.A$.2A17.A.2A56.5A$2.A17.2A.A56.A.C4A
$.A22.2A54.5A.2A$.2A22.A58.2A$24.A59.4A$.2A21.2A$2.A19.2A$.A21.A$.2A
19.A$22.2A$.2A17.2A$2.A18.A$.A18.A$.2A17.2A86$86.A$.2A19.2A.A54.5A$2.
A19.A.2A54.A.AC3A$.A18.2A4.2A52.5A.2A$.2A17.A5.A57.2A$21.A5.A56.4A$.
2A17.2A4.2A$2.A19.2A.A$.A20.A.2A$.2A17.2A4.2A$20.A5.A$.2A18.A5.A$2.A
17.2A4.2A$.A20.2A.A$.2A19.A.2A!
It's nice to run it one generation and see 0-3 becomes active, 1-2/3 remain active and everyone else dies.

P.s. I don't think that p2s or p3s are capable to cover all the states. because having the 1-8 state can't exist in p2-3. But it's just a guess.

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

Re: Reverse rule-finding

Post by dvgrn » May 5th, 2014, 8:11 am

simsim314 wrote:I was also thinking of other interpretation: what is the state with the smallest number of ON cells, which next generation will define uniquely one of 2^18 possibilities of totalistic rules. I.e. a single state that has all the 18 options inside it in single generation.

Here is 25 cells example:...
Twenty cells is enough:

Code: Select all

x = 96, y = 1715, rule = LifeHistory
90.5A$2.2A.A16.2A.A64.3A.A$2.A.2A16.A.2A64.5A$2A4.2A12.2A4.2A62.A$A5.
A13.A5.A63.4A.A$.A5.A13.A5.A$2A4.2A12.2A4.2A61.D$A5.A13.A5.A$.A5.A13.
A5.A$2A4.2A12.2A4.2A$A5.A13.A5.A$.A5.A13.A5.A$2A4.2A12.2A4.2A$2.2A.A
16.2A.A$2.A.2A16.A.2A85$89.D$90.5A$2.2A.A15.2A67.3A.A$2.A.2A16.A67.5A
$2A4.2A13.A68.A$A5.A14.2A67.4A.A$.A5.A$2A4.2A13.2A$A5.A15.A$.A5.A13.A
$2A4.2A13.2A$A5.A$.A5.A13.2A$2A4.2A14.A$2.2A.A15.A$2.A.2A15.2A86$89.D
5A$2.2A.A16.2A.A64.3A.A$2.A.2A16.A.2A64.5A$2A4.2A18.2A62.A$A5.A19.A
63.4A.A$.A5.A19.A$2A4.2A18.2A$A5.A15.2A.A$.A5.A14.A.2A$2A4.2A12.2A$A
5.A13.A$.A5.A13.A$2A4.2A12.2A$2.2A.A16.2A.A$2.A.2A16.A.2A86$90.5A$2.
2A.A14.2A.A65.D3A.A$2.A.2A14.A.2A66.5A$2A4.2A16.2A64.A$A5.A17.A65.4A.
A$.A5.A17.A$2A4.2A16.2A$A5.A13.2A.A$.A5.A12.A.2A$2A4.2A16.2A$A5.A17.A
$.A5.A17.A$2A4.2A16.2A$2.2A.A14.2A.A$2.A.2A14.A.2A86$90.5A$2.2A.A14.
2A3.2A63.3A.A$2.A.2A14.2A3.2A63.5A$2A4.2A82.A3.D$A5.A13.2A3.2A63.4A.A
$.A5.A12.A.A.A.A$2A4.2A14.A.A$A5.A14.2A.A$.A5.A17.2A$2A4.2A18.A$A5.A
18.A$.A5.A17.2A$2A4.2A18.A$2.2A.A19.A$2.A.2A19.2A86$90.5A$2.2A.A16.2A
.A64.3A.A$2.A.2A16.A.2A64.5A$2A4.2A12.2A68.A2.D$A5.A13.A69.4A.A$.A5.A
13.A$2A4.2A12.2A$A5.A15.2A.A$.A5.A14.A.2A$2A4.2A18.2A$A5.A19.A$.A5.A
19.A$2A4.2A18.2A$2.2A.A16.2A.A$2.A.2A16.A.2A86$90.5A$2.2A.A16.2A.A64.
3A.A$2.A.2A16.A.2A64.5A$2A4.2A12.2A68.A.D$A5.A13.A69.4A.A$.A5.A13.A$
2A4.2A12.2A$A5.A15.2A.A$.A5.A14.A.2A$2A4.2A12.2A4.2A$A5.A13.A5.A$.A5.
A13.A5.A$2A4.2A12.2A4.2A$2.2A.A16.2A.A$2.A.2A16.A.2A86$90.5A$2.2A.A
14.A.2A66.3A.A$2.A.2A14.2A.A66.5A$2A4.2A16.2A64.AD$A5.A18.A64.4A.A$.A
5.A16.A$2A4.2A16.2A$A5.A15.2A$.A5.A15.A$2A4.2A14.A$A5.A15.2A$.A5.A12.
2A$2A4.2A13.A$2.2A.A14.A$2.A.2A14.2A86$90.5A$2.2A.A16.2A.A64.3ADA$2.A
.2A16.A.2A64.5A$2A4.2A12.2A4.2A62.A$A5.A13.A5.A63.4A.A$.A5.A13.A5.A$
2A4.2A12.2A4.2A$A5.A15.2A.A$.A5.A14.A.2A$2A4.2A12.2A4.2A$A5.A13.A5.A$
.A5.A13.A5.A$2A4.2A12.2A4.2A$2.2A.A16.2A.A$2.A.2A16.A.2A86$90.5A$.2A
19.2A.A64.3A.A$2.A19.A.2A64.5A$.A18.2A4.2A62.A$.2A17.A5.A63.4A.C$21.A
5.A$.2A17.2A4.2A$2.A17.A5.A$.A19.A5.A$.2A17.2A4.2A$20.A5.A$.2A18.A5.A
$2.A17.2A4.2A$.A20.2A.A$.2A19.A.2A86$90.5A$.2A18.2A67.3A.A$2.A19.A67.
5A$.A19.A68.A$.2A18.2A67.3AC.A2$.2A18.2A$2.A19.A$.A19.A$.2A18.2A2$.2A
18.2A$2.A19.A$.A19.A$.2A18.2A86$90.5A$.2A19.2A.A64.3A.A$2.A19.A.2A64.
5A$.A24.2A62.A$.2A23.A63.C3A.A$27.A$.2A23.2A$2.A19.2A.A$.A20.A.2A$.2A
17.2A$20.A$.2A18.A$2.A17.2A$.A20.2A.A$.2A19.A.2A86$90.C4A$.2A17.2A.A
66.3A.A$2.A17.A.2A66.5A$.A22.2A64.A$.2A21.A65.4A.A$25.A$.2A21.2A$2.A
17.2A.A$.A18.A.2A$.2A21.2A$24.A$.2A22.A$2.A21.2A$.A18.2A.A$.2A17.A.2A
86$90.5A$.2A17.2A3.2A63.3A.A$2.A17.2A3.2A63.C4A$.A88.A$.2A17.2A3.2A
63.4A.A$20.A.A.A.A$.2A19.A.A$2.A18.2A.A$.A23.2A$.2A23.A$25.A$.2A22.2A
$2.A23.A$.A23.A$.2A22.2A86$90.5A$.2A19.2A.A64.C2A.A$2.A19.A.2A64.5A$.
A18.2A68.A$.2A17.A69.4A.A$21.A$.2A17.2A$2.A19.2A.A$.A20.A.2A$.2A23.2A
$26.A$.2A24.A$2.A23.2A$.A20.2A.A$.2A19.A.2A86$90.5A$.2A19.2A.A64.3A.A
$2.A19.A.2A64.AC3A$.A18.2A68.A$.2A17.A69.4A.A$21.A$.2A17.2A$2.A19.2A.
A$.A20.A.2A$.2A17.2A4.2A$20.A5.A$.2A18.A5.A$2.A17.2A4.2A$.A20.2A.A$.
2A19.A.2A86$90.5A$.2A17.A.2A66.2AC.A$2.A17.2A.A66.5A$.A22.2A64.A$.2A
22.A64.4A.A$24.A$.2A21.2A$2.A19.2A$.A21.A$.2A19.A$22.2A$.2A17.2A$2.A
18.A$.A18.A$.2A17.2A86$90.5A$.2A19.2A.A64.ACA.A$2.A19.A.2A64.5A$.A18.
2A4.2A62.A$.2A17.A5.A63.4A.A$21.A5.A$.2A17.2A4.2A$2.A19.2A.A$.A20.A.
2A$.2A17.2A4.2A$20.A5.A$.2A18.A5.A$2.A17.2A4.2A$.A20.2A.A$.2A19.A.2A!
Unfortunately this looks like a problem that's small enough that a boring brute-force search would eventually grind out the absolute smallest possible answer. Might be able to shave off another cell or two, I suppose...

User avatar
simsim314
Posts: 1731
Joined: February 10th, 2014, 1:27 pm

Re: Reverse rule-finding

Post by simsim314 » May 5th, 2014, 4:44 pm

Wow! twenty is probably the optimum.

I was trying to prove 20 is the minimum.

19 is required, for placing the four patterns:

Code: Select all

x = 7, y = 7, rule = B3/S23
3ob3o$obob3o$3ob3o2$3o$o4bo$3o!
For example:

Code: Select all

x = 5, y = 5, rule = B3/S23
5o$obo$5o$2b3o$ob3o!
Now I don't have mathematical proof that the three large patterns will take 18 cells at least, but I've tried many, and I can guess the proof is not that complex.

Now with 19 I've tried many as well. There is always some 0-5 or 0-6 missing. Because a large corner is 0-5 and using the single cell it can become 0-6 but then there would be no 0-5.

So no "real" proof yet, but I'm convinced 20 is the best.

Here is another example with 20:

Code: Select all

x = 86, y = 1715, rule = LifeHistory
80.A.3A$2.2A.A16.2A.A56.A$2.A.2A16.A.2A54.6A$2A4.2A12.2A4.2A52.A.3A$A
5.A13.A5.A53.5A$.A5.A13.A5.A$2A4.2A12.2A4.2A51.D$A5.A13.A5.A$.A5.A13.
A5.A$2A4.2A12.2A4.2A$A5.A13.A5.A$.A5.A13.A5.A$2A4.2A12.2A4.2A$2.2A.A
16.2A.A$2.A.2A16.A.2A85$79.D$80.A.3A$2.2A.A15.2A59.A$2.A.2A16.A57.6A$
2A4.2A13.A58.A.3A$A5.A14.2A57.5A$.A5.A$2A4.2A13.2A$A5.A15.A$.A5.A13.A
$2A4.2A13.2A$A5.A$.A5.A13.2A$2A4.2A14.A$2.2A.A15.A$2.A.2A15.2A86$80.A
.3A$2.2A.A16.2A.A53.D2.A$2.A.2A16.A.2A54.6A$2A4.2A18.2A52.A.3A$A5.A
19.A53.5A$.A5.A19.A$2A4.2A18.2A$A5.A15.2A.A$.A5.A14.A.2A$2A4.2A12.2A$
A5.A13.A$.A5.A13.A$2A4.2A12.2A$2.2A.A16.2A.A$2.A.2A16.A.2A86$80.A.3A$
2.2A.A14.2A.A58.A$2.A.2A14.A.2A56.6A$2A4.2A16.2A53.DA.3A$A5.A17.A55.
5A$.A5.A17.A$2A4.2A16.2A$A5.A13.2A.A$.A5.A12.A.2A$2A4.2A16.2A$A5.A17.
A$.A5.A17.A$2A4.2A16.2A$2.2A.A14.2A.A$2.A.2A14.A.2A86$80.A.3A$2.2A.A
14.2A3.2A55.A$2.A.2A14.2A3.2A53.6A$2A4.2A72.A.3AD$A5.A13.2A3.2A53.5A$
.A5.A12.A.A.A.A$2A4.2A14.A.A$A5.A14.2A.A$.A5.A17.2A$2A4.2A18.A$A5.A
18.A$.A5.A17.2A$2A4.2A18.A$2.2A.A19.A$2.A.2A19.2A86$80.A.3A$2.2A.A16.
2A.A56.A.D$2.A.2A16.A.2A54.6A$2A4.2A12.2A58.A.3A$A5.A13.A59.5A$.A5.A
13.A$2A4.2A12.2A$A5.A15.2A.A$.A5.A14.A.2A$2A4.2A18.2A$A5.A19.A$.A5.A
19.A$2A4.2A18.2A$2.2A.A16.2A.A$2.A.2A16.A.2A86$80.A.3A$2.2A.A16.2A.A
55.DA$2.A.2A16.A.2A54.6A$2A4.2A12.2A58.A.3A$A5.A13.A59.5A$.A5.A13.A$
2A4.2A12.2A$A5.A15.2A.A$.A5.A14.A.2A$2A4.2A12.2A4.2A$A5.A13.A5.A$.A5.
A13.A5.A$2A4.2A12.2A4.2A$2.2A.A16.2A.A$2.A.2A16.A.2A86$80.A.3A$2.2A.A
14.A.2A58.AD$2.A.2A14.2A.A56.6A$2A4.2A16.2A54.A.3A$A5.A18.A54.5A$.A5.
A16.A$2A4.2A16.2A$A5.A15.2A$.A5.A15.A$2A4.2A14.A$A5.A15.2A$.A5.A12.2A
$2A4.2A13.A$2.2A.A14.A$2.A.2A14.2A86$80.A.3A$2.2A.A16.2A.A56.A$2.A.2A
16.A.2A54.6A$2A4.2A12.2A4.2A52.AD3A$A5.A13.A5.A53.5A$.A5.A13.A5.A$2A
4.2A12.2A4.2A$A5.A15.2A.A$.A5.A14.A.2A$2A4.2A12.2A4.2A$A5.A13.A5.A$.A
5.A13.A5.A$2A4.2A12.2A4.2A$2.2A.A16.2A.A$2.A.2A16.A.2A86$80.C.3A$.2A
19.2A.A56.A$2.A19.A.2A54.6A$.A18.2A4.2A52.A.3A$.2A17.A5.A53.5A$21.A5.
A$.2A17.2A4.2A$2.A17.A5.A$.A19.A5.A$.2A17.2A4.2A$20.A5.A$.2A18.A5.A$
2.A17.2A4.2A$.A20.2A.A$.2A19.A.2A86$80.A.2AC$.2A18.2A59.A$2.A19.A57.
6A$.A19.A58.A.3A$.2A18.2A57.5A2$.2A18.2A$2.A19.A$.A19.A$.2A18.2A2$.2A
18.2A$2.A19.A$.A19.A$.2A18.2A86$80.A.3A$.2A19.2A.A56.A$2.A19.A.2A54.C
5A$.A24.2A52.A.3A$.2A23.A53.5A$27.A$.2A23.2A$2.A19.2A.A$.A20.A.2A$.2A
17.2A$20.A$.2A18.A$2.A17.2A$.A20.2A.A$.2A19.A.2A86$80.A.ACA$.2A17.2A.
A58.A$2.A17.A.2A56.6A$.A22.2A54.A.3A$.2A21.A55.5A$25.A$.2A21.2A$2.A
17.2A.A$.A18.A.2A$.2A21.2A$24.A$.2A22.A$2.A21.2A$.A18.2A.A$.2A17.A.2A
86$80.A.3A$.2A17.2A3.2A55.A$2.A17.2A3.2A53.6A$.A78.C.3A$.2A17.2A3.2A
53.5A$20.A.A.A.A$.2A19.A.A$2.A18.2A.A$.A23.2A$.2A23.A$25.A$.2A22.2A$
2.A23.A$.A23.A$.2A22.2A86$80.A.3A$.2A19.2A.A56.A$2.A19.A.2A54.AC4A$.A
18.2A58.A.3A$.2A17.A59.5A$21.A$.2A17.2A$2.A19.2A.A$.A20.A.2A$.2A23.2A
$26.A$.2A24.A$2.A23.2A$.A20.2A.A$.2A19.A.2A86$80.A.3A$.2A19.2A.A56.A$
2.A19.A.2A54.3AC2A$.A18.2A58.A.3A$.2A17.A59.5A$21.A$.2A17.2A$2.A19.2A
.A$.A20.A.2A$.2A17.2A4.2A$20.A5.A$.2A18.A5.A$2.A17.2A4.2A$.A20.2A.A$.
2A19.A.2A86$80.A.3A$.2A17.A.2A58.A$2.A17.2A.A56.6A$.A22.2A54.A.C2A$.
2A22.A54.5A$24.A$.2A21.2A$2.A19.2A$.A21.A$.2A19.A$22.2A$.2A17.2A$2.A
18.A$.A18.A$.2A17.2A86$80.A.3A$.2A19.2A.A56.A$2.A19.A.2A54.6A$.A18.2A
4.2A52.A.ACA$.2A17.A5.A53.5A$21.A5.A$.2A17.2A4.2A$2.A19.2A.A$.A20.A.
2A$.2A17.2A4.2A$20.A5.A$.2A18.A5.A$2.A17.2A4.2A$.A20.2A.A$.2A19.A.2A!

User avatar
Tropylium
Posts: 406
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: Reverse rule-finding

Post by Tropylium » November 16th, 2015, 6:50 pm

OP's question, reframed:
– A Life-like CA is defined by the presence of some birth/survival conditions and the absense of others.
– Any pattern (spaceship, oscillator, etc.) in a Life-like CA will require some of these conditions to function, but not necessarily all. For example, a blinker will only require the absence of B012 and the presence of B3 (in brief: B3,A012 — A being short for "abstain"), but the higher birth conditions are irrelevant. Similarly, S2 and D1 (short for "death") are required, but all other survival conditions are irrelevant.
– The complete set of conditions a pattern requires could be called the rulespace area that a pattern is native to.
– What, then, is the smallest oscillator native to the specific rule B3,A01245678/S23,D0145678?

The LifeWiki already lists the native ranges of numerous patterns: ranging from 2^14 rules for the block, to only one for patterns such as centinal. Candidates for the answer could be fairly simple to find, if this was established as a new categorization system ("Patterns with a native range of 2 rules", "Patterns with a native range of 256 rules", etc.)

How do we define "smallest" here, though? Given the same bounding-box or average cell-count size, a longer-period oscillator will feature more transitions, and will be more likely to be native only to a smaller range than a shorter-period oscillator. At its extreme, no still life can be native to Life and only Life, since B8 vs. A8 and B7 vs. A7 never come up. Perhaps "cell count across all generations" might be a better measure of a periodic pattern's size, here?

Post Reply