How many rules are there?

For discussion of other cellular automata.
User avatar
blah
Posts: 313
Joined: April 9th, 2016, 7:22 pm

Re: How many rules are there?

Post by blah » July 1st, 2017, 9:07 am

gameoflifemaniac wrote:What does Lt mean?
blah wrote:... We can then define another number, Lt (with a lowercase t), the amount of LtL rules which cannot be simulated by Ruleloader. This would follow the same equation as above, but with the summations starting from R=2 instead of R=1.
gameoflifemaniac wrote:So waht is the real formula for the number of von Neumann and Larger than Life rules, counting also these that aren't simulateable in Golly?
I'm not sure what you mean. Golly can simulate the entire family of LtL rules as defined by MCell. It can actually simulate more, because R goes up to 50 right now. What rules can it not simulate?
gameoflifemaniac wrote:And in the formula sum (n=1 to 256) n^n^9 include for example JvN29?
Yes. Rules with (range 1) Von Neumann or hexagonal neighbourhoods are technically subsets of the n^n^9 thing.
Gamedziner wrote:I didn't realize that was in a base 10 logarithm; never mind! :oops:

However, that also means the number of rules (10^1.1372591694895837×10^22) can be simplified to (10^23.1372591694895837).
I'm not entirely sure where you got that from. 256^256^9 alone is 256^4722366482869645213696. That's obviously a lot bigger than 10^23. Did you mean 10^23*1372591694895837? Even if you meant that, the amount of digits is still small enough to fit somewhere. In fact:
10^23*1372591694895837 = 137259169489583700000000000000000000000
Clearly 256^256^9 could not be a number small enough to put all the digits on a screen like that.
succ

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: How many rules are there?

Post by gameoflifemaniac » July 4th, 2017, 4:06 am

So what's the number of ALL rules (without symbols like Lt or LT)?
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
blah
Posts: 313
Joined: April 9th, 2016, 7:22 pm

Re: How many rules are there?

Post by blah » July 4th, 2017, 8:48 am

gameoflifemaniac wrote:So what's the number of ALL rules (without symbols like Lt or LT)?
Do you mean you want the actual numeric value of G0 or something? If so, it's very close (proportionally) to 256^256^9, which can be computed here. Any more precision would make essentially no difference other than to change the last few digits.
succ

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: How many rules are there?

Post by gameoflifemaniac » July 4th, 2017, 12:21 pm

blah wrote:
gameoflifemaniac wrote:So what's the number of ALL rules (without symbols like Lt or LT)?
Do you mean you want the actual numeric value of G0 or something? If so, it's very close (proportionally) to 256^256^9, which can be computed here. Any more precision would make essentially no difference other than to change the last few digits.
I meant ALL rules including Ltl rules!
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
blah
Posts: 313
Joined: April 9th, 2016, 7:22 pm

Re: How many rules are there?

Post by blah » July 4th, 2017, 1:50 pm

gameoflifemaniac wrote:I meant ALL rules including Ltl rules!
G0 does include LtL rules. As I said, the LtL rules are basically nothing compared to the rest of the equation. Are you saying you want a full equation that technically gives the result? I provided that here, albeit broken up into smaller parts.
succ

User avatar
calcyman
Moderator
Posts: 2964
Joined: June 1st, 2009, 4:32 pm

Re: How many rules are there?

Post by calcyman » July 4th, 2017, 3:17 pm

gameoflifemaniac wrote:
blah wrote:
gameoflifemaniac wrote:So what's the number of ALL rules (without symbols like Lt or LT)?
Do you mean you want the actual numeric value of G0 or something? If so, it's very close (proportionally) to 256^256^9, which can be computed here. Any more precision would make essentially no difference other than to change the last few digits.
I meant ALL rules including Ltl rules!
Countably infinite.

Just as an example of a cellular automaton which you haven't taken into account, I've made a GPU implementation of a 2^64-state automaton on a 13-element partitioning scheme on a hexagonal lattice (analogous to how the Margolus neighbourhood is a 4-element partitioning scheme on a square lattice). Here's a screenshot to whet your appetite:
Snapshot of the hex13 cellular automaton, showing a DNA strand which has replicated in the presence of enzymes (dark green).
Snapshot of the hex13 cellular automaton, showing a DNA strand which has replicated in the presence of enzymes (dark green).
browser.png (42.9 KiB) Viewed 6438 times
It's largely inspired by several papers by Tim Hutton (of Hutton32 fame), but with a few additional insights of my own, and is an attempt to simulate open-ended evolution in a computational system.

You could argue: "hex13 can't be simulated in Golly"

But then I would respond: "you could create a metacell in another rule (e.g. B3/S23) to emulate hex13"

Why you would even attempt to do this is another matter entirely, since it would be impractically slow compared with the GPU implementation. It might be satisfying as a justification that evolution is possible in a simple cellular automaton as opposed to a very complex one.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
blah
Posts: 313
Joined: April 9th, 2016, 7:22 pm

Re: How many rules are there?

Post by blah » July 4th, 2017, 4:57 pm

I computed the value of LT and Lt. I wrote a c program using this optimised form of my older equation:
LT5.png
LT5.png (6.56 KiB) Viewed 6427 times

Code: Select all

/*
	LTt.c
	blah 2017

	A program to compute the number of "Larger than Life" rules that exist.
	See this thread: http://www.conwaylife.com/forums/viewtopic.php?f=11&t=2928
*/
#include <stdio.h>
#define BIG_T //Comment this line out to get Lt instead of LT
#ifdef BIG_T
	#define START 1
#else
	#define START 2
#endif
#define num unsigned long long

num S(num in){ //square function
	return in*in;
}
num m(num R){
	return S(2*R+1);
}
num v(num R){
	return S(R)+S(R+1);
}

int main(){
	num total=0;
	for(num R=START;R<=50;R++){
		total+=S(m(R))+m(R) + S(v(R))+v(R);
	}
	printf("%llu\n", total*254);
	return 0;
}
Results:
LT = 350,523,200,400
Lt = 350,523,169,920
Now we know exactly how many rules were added in Golly 3.0b1.
succ

wwei23

Re: How many rules are there?

Post by wwei23 » July 4th, 2017, 5:25 pm

And now I know how many rules I can't use because my computer says Golly 3.0b1 is unsafe when I tried to run it and it deleted it. :(

User avatar
Andrew
Moderator
Posts: 981
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: How many rules are there?

Post by Andrew » July 4th, 2017, 9:23 pm

calcyman wrote:I've made a GPU implementation of a 2^64-state automaton on a 13-element partitioning scheme on a hexagonal lattice (analogous to how the Margolus neighbourhood is a 4-element partitioning scheme on a square lattice).
Adam, you really are a terrible tease. :) Any chance us mere mortals can play with your CA? Could it be implemented in Ready? Why such a bizarre partitioning scheme? So many questions...
Use Glu to explore CA rules on non-periodic tilings: DominoLife and HatLife

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: How many rules are there?

Post by gameoflifemaniac » July 5th, 2017, 3:09 am

blah wrote:I'm not sure what you mean. Golly can simulate the entire family of LtL rules as defined by MCell. It can actually simulate more, because R goes up to 50 right now. What rules can it not simulate?
It could not simulate for example a rule where a live cell will survive if it has 2345 or 3821 neighbours. You can count all the survival positions in a range, but you cannot 'jump' from one survival condition to another. This is like getting beyond B*/S*: getting to all possible 2^512 two state rules.
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
blah
Posts: 313
Joined: April 9th, 2016, 7:22 pm

Re: How many rules are there?

Post by blah » July 5th, 2017, 11:26 am

gameoflifemaniac wrote:It could not simulate for example a rule where a live cell will survive if it has 2345 or 3821 neighbours. You can count all the survival positions in a range, but you cannot 'jump' from one survival condition to another. This is like getting beyond B*/S*: getting to all possible 2^512 two state rules.
I mean, if you want to count an extension of LtL rules that allows arbitrary B/S strings rather than the min/max system, I believe it would be this:
unrestictedbs.png
unrestictedbs.png (4.29 KiB) Viewed 6384 times
But as Calcyman stated earlier, there's no fancy equation for "every rule". There is just ∞.

EDIT: That equation is wrong. It should probably be 2^(m/v(R)*2) instead of 2^(m/v(R)+1), for example with R=1 you get the 2^18 lifelike rules, and 18 is 9*2=m(1)*2. the equation I posted suggests there are 2^10 lifelike rules, which is not true.
succ

User avatar
blah
Posts: 313
Joined: April 9th, 2016, 7:22 pm

Re: How many rules are there?

Post by blah » July 8th, 2017, 10:34 pm

I have realised that it is possible to have a Larger than Life rule with no survival and/or no birth conditions. This makes the result of my c program and the equations it's based on slightly wrong (depending on how you formally define the rulespace). I'll probably modify my equations again at some point. Either way, it seems that there's always some misrake [sic] that I haven't noticed.
succ

User avatar
blah
Posts: 313
Joined: April 9th, 2016, 7:22 pm

Re: How many rules are there?

Post by blah » July 16th, 2017, 10:22 am

I've noticed that I made another mistake. I multiplied the triangular numbers representing the amount of possibilities for a min/max combination by 2 instead of squaring them. The equation I have now is this:
LT6.png
LT6.png (5.29 KiB) Viewed 6281 times
Where Tn is the nth triangular number.

I've attempted to create a proof that this equation is accurate, although it has a few leaps of logic in it. That proof is attached as a .pdf file, except I had to change the file extension to txt because this forum doesn't allow pdf files to be attached for some reason.
Attachments
Rulespaces.txt
(69.65 KiB) Downloaded 239 times
succ

Post Reply