How many rules are there?
 gameoflifemaniac
 Posts: 1099
 Joined: January 22nd, 2017, 11:17 am
 Location: There too
How many rules are there?
Since yesterday I have been wondering: how many different rules are possible?
There are three following rules:
1. The number of states cannot exceed 256.
2. Every cell cannot have more than 8 neighbouring cells (Larger than Life rules are not allowed).
3. Hexagonal, triangular etc. rules are not allowed (but those rules emulated on a square grid are allowed).
For those who are interested in this question post a comment in this topic with a approximation of this number. Bonus: when you want you can post me the number of rules with not only different rules, but also with different state colors.
There are three following rules:
1. The number of states cannot exceed 256.
2. Every cell cannot have more than 8 neighbouring cells (Larger than Life rules are not allowed).
3. Hexagonal, triangular etc. rules are not allowed (but those rules emulated on a square grid are allowed).
For those who are interested in this question post a comment in this topic with a approximation of this number. Bonus: when you want you can post me the number of rules with not only different rules, but also with different state colors.
I was so socially awkward in the past and it will haunt me for my entire life.

 Posts: 1115
 Joined: July 1st, 2016, 3:58 pm
Re: How many rules are there?
2^256^10, or 10^(3.63*10^23), is my guess, because there are 10 numbers in a transition table, and with 256 states, with repeats, they have 256^10 different transitions. Of those transitions, it is a choice to have them on or off, so just raise 2 to the number of transitions, and there is the number.
The number simulatable by Golly 2.8 is actually 2^257^10, because it can hold 257 states.
The number simulatable by Golly 2.8 is actually 2^257^10, because it can hold 257 states.
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Nontotalistic rules.
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
Re: How many rules are there?
How many of these rules are apgsearchable, and how many of them allow for spaceships?
Bored of using the Moore neighbourhood for everything? Introducing the Range2 von Neumann isotropic nontotalistic rulespace!
 gameoflifemaniac
 Posts: 1099
 Joined: January 22nd, 2017, 11:17 am
 Location: There too
Re: How many rules are there?
Why 257? When I tried to type in the rule 12/34/257, it showed: 'The new rule is not valid in any algorithm.'AforAmpere wrote:2^256^10, or 10^(3.63*10^23), is my guess, because there are 10 numbers in a transition table, and with 256 states, with repeats, they have 256^10 different transitions. Of those transitions, it is a choice to have them on or off, so just raise 2 to the number of transitions, and there is the number.
The number simulatable by Golly 2.8 is actually 2^257^10, because it can hold 257 states.
Maybe with your method some rules may be omitted? And have you counted only the 256state rules without the rules with less than 256 states?
I was so socially awkward in the past and it will haunt me for my entire life.

 Posts: 1115
 Joined: July 1st, 2016, 3:58 pm
Re: How many rules are there?
You are right about 256, sorry, but 256 state rules can emulate all others, so it is equivalent, another estimate would be if you counted all others, so 2^256^10+2^255^10...+2^2^10. I am not sure what that would be, but it is very, very close to the estimate I gave, in terms of power towers, try it with Hypercalc
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Nontotalistic rules.
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
 gameoflifemaniac
 Posts: 1099
 Joined: January 22nd, 2017, 11:17 am
 Location: There too
Re: How many rules are there?
This was a post that I wanted to delete, but I couldn't because it was already replied. Sorry!
Last edited by gameoflifemaniac on June 28th, 2017, 1:40 pm, edited 3 times in total.
I was so socially awkward in the past and it will haunt me for my entire life.
Re: How many rules are there?
There are n^n^9 nstate moore neighbourhood rules on square grids.
In the moore neighbourhood, you have 9 digits in base n for each condition. This means there are n^9 conditions, and each one has an integer <=n and >0 as its outcome. Each outcome is essentially a digit in a large string containing all possible outcomes for each condition, so we raise the base to the number of conditions. So we get n^n^9.
There are 255 possible values n can hold, from 1 to 256 (I'm counting the single 1state CA, not that an error margin of 1 matters here). As such, the number of possible n<256 state moore neighbourhood cellular automata is equal to the neat equation: If you can find any problems in my reasoning, please point them out.
Edit: With 2^256^10, you're making two mistakes. First off, you're assuming each outcome can be either on or off, when in reality there are more than two outcomes depending on the number of states. That, and you're using 10 instead of 9, even though you should be counting the outcome as part of the 'rulestring'.
In the moore neighbourhood, you have 9 digits in base n for each condition. This means there are n^9 conditions, and each one has an integer <=n and >0 as its outcome. Each outcome is essentially a digit in a large string containing all possible outcomes for each condition, so we raise the base to the number of conditions. So we get n^n^9.
There are 255 possible values n can hold, from 1 to 256 (I'm counting the single 1state CA, not that an error margin of 1 matters here). As such, the number of possible n<256 state moore neighbourhood cellular automata is equal to the neat equation: If you can find any problems in my reasoning, please point them out.
Edit: With 2^256^10, you're making two mistakes. First off, you're assuming each outcome can be either on or off, when in reality there are more than two outcomes depending on the number of states. That, and you're using 10 instead of 9, even though you should be counting the outcome as part of the 'rulestring'.
succ
 gameoflifemaniac
 Posts: 1099
 Joined: January 22nd, 2017, 11:17 am
 Location: There too
Re: How many rules are there?
So the number of rules is 10^1.1372591694895835×10^22, but I also mentioned about state colors. There are 256^3=16777216 different RGB values, so we have to raise the number of rules to the power of 16777216. This's approximately (256^256^9)^(256^3)=10^1.9080042734507352×10^29. The 255^255^9+254^254^9... bit is redundant because those compared to 256^256^9 are like a Planck volume compared to the Universe.blah wrote:There are n^n^9 nstate moore neighbourhood rules on square grids.
In the moore neighbourhood, you have 9 digits in base n for each condition. This means there are n^9 conditions, and each one has an integer <=n and >0 as its outcome. Each outcome is essentially a digit in a large string containing all possible outcomes for each condition, so we raise the base to the number of conditions. So we get n^n^9.
There are 255 possible values n can hold, from 1 to 256 (I'm counting the single 1state CA, not that an error margin of 1 matters here). As such, the number of possible n<256 state moore neighbourhood cellular automata is equal to the neat equation: If you can find any problems in my reasoning, please point them out.
Edit: With 2^256^10, you're making two mistakes. First off, you're assuming each outcome can be either on or off, when in reality there are more than two outcomes depending on the number of states. That, and you're using 10 instead of 9, even though you should be counting the outcome as part of the 'rulestring'.
I was so socially awkward in the past and it will haunt me for my entire life.
Re: How many rules are there?
I'm pretty sure that raising it to the power of 16777216 doesn't work. I think it would be my previous equation, but instead of n^n^9 it would be (n^n^9)*2^(n*24).
Each rule with n states has 24 bits for each state representing colour information. As such, there are 2^(n*24) possible colour combinations, which will be multiplied by the number of actual rules.
Overall, that gives us this thing: I'd like to know the details of the Larger than Life rulespace, so I could add that to the equation. That would be fun.
Each rule with n states has 24 bits for each state representing colour information. As such, there are 2^(n*24) possible colour combinations, which will be multiplied by the number of actual rules.
Overall, that gives us this thing: I'd like to know the details of the Larger than Life rulespace, so I could add that to the equation. That would be fun.
succ

 Posts: 1115
 Joined: July 1st, 2016, 3:58 pm
Re: How many rules are there?
How are either of those mistakes? 2,2,2,3,0,0,0,0,0,5 is one transition, with 10 numbers, each number can have 256 different states, from 0,0,0,0,0,0,0,0,0,0 to 255,255,255,255,255,255,255,255,255,255. Each transition in these 256^10 transitions can be used or not, so 2^256^10, how does this not work, each transition can only be used or not, there is no inbetween.
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Nontotalistic rules.
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
Re: How many rules are there?
First off, it is not true that each transition can be either 'on' or 'off'. There are a number of cases (conditions of the neighbourhood), and each case has an outcome. in a 3state CA, an outcome can be one of 3 states, not 2, so using 2 as the base for the whole thing doesn't make sense. There can't be no outcome, it has to be something.AforAmpere wrote:How are either of those mistakes?
Secondly, a transition in a ruletable consists of a list of 10 states, but look at it this way: you have, say, 2 states, so n=2. There are 2^9=512 cases, and each one has an outcome. So each outcome is a bit. As such, the amount of possibilities for those bits is 2^512, which is 2^2^9. The tenth state, the outcome, is accounted for later on in my equation, and I believe yours fails to properly account for it.
n^9 is the amount of cases, but n^10 is not.
succ

 Posts: 1115
 Joined: July 1st, 2016, 3:58 pm
Re: How many rules are there?
I get it, so you are essentially trying to get closer to the number of distinct rules. Am I right that you are trying to eliminate stuff like this?
0,1,2,0,2,1,1,0,1,1
0,1,2,0,2,1,1,0,1,2
That was a dumb mistake on my part. However, I think the number of distinct rules can be reduced further, by eliminating transitions that start and end with the same state, because each state will stay in its state anyway, without a transition, how would that factor in?
0,1,2,0,2,1,1,0,1,1
0,1,2,0,2,1,1,0,1,2
That was a dumb mistake on my part. However, I think the number of distinct rules can be reduced further, by eliminating transitions that start and end with the same state, because each state will stay in its state anyway, without a transition, how would that factor in?
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Nontotalistic rules.
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
Re: How many rules are there?
Yeah, I didn't even think of that but I guess that was a problem with your equation. Also, cases where a state does not change are still cases, with outcomes. You're thinking of the RuleLoader algorithm, and how it implicitly assumes cells stay the same unless stated otherwise. But I'm thinking of the mathematical description of all these rules, and how each case must have its own predetermined outcome. I'm not trying to get closer to the number of rules, by the way, I already have the exact number.AforAmpere wrote:I get it, so you are essentially trying to get closer to the number of distinct rules. Am I right that you are trying to eliminate stuff like this?
0,1,2,0,2,1,1,0,1,1
0,1,2,0,2,1,1,0,1,2
That was a dumb mistake on my part. However, I think the number of distinct rules can be reduced further, by eliminating transitions that start and end with the same state, because each state will stay in its state anyway, without a transition, how would that factor in?
Anyway, I've come up with a way to factor in Golly's support for icons into my equation, to make the number even bigger and the equation even more pointlessly complicated. Going off of Golly's documentation:
There are 3 icon resolutions: 7x7, 15x15 and 31x31.
There are no icons for state 0.
And I'm guessing each pixel has 24bit colour.
As such, each state other than 0 has 7^2+15^2+31^2=1235 pixels. Multiplied by 24 that's 29640 bits. So to the equation, we'll add 2^((n1)*29640)
So, uhh... The 1 at the end is to account for the case of n=1, because 2^0=1, not 0.
"An idiot admires complexity, a genius admires simplicity"  Terry A. Davis (probably paraphrased) (I'm an idiot is what I'm saying)
I should sleep
EDIT: That image is wrong. It has two errors, although technically they cancel each other out:
2. It starts at 1 instead of 2
3. It has a 1 at the end, because I didn't realise the case of n=1 was actually multiplying the rest of the equation by 1, thus doing nothing
And so it's actually correct, by accident
Last edited by blah on June 29th, 2017, 8:27 pm, edited 1 time in total.
succ
Re: How many rules are there?
Wait, I've just noticed RuleLoader doesn't actually let you make a rule with 1 state. I'll fix my equations tomorrow.
succ
 gameoflifemaniac
 Posts: 1099
 Joined: January 22nd, 2017, 11:17 am
 Location: There too
Re: How many rules are there?
I have found something (I can't find a adjective to describe this.). With only state colours the number of rules is 10^1.1372591694895835×10^22, but with icons it's 10^1.1372591694895837×10^22. This change is so slight!
I was so socially awkward in the past and it will haunt me for my entire life.

 Posts: 795
 Joined: May 30th, 2016, 8:47 pm
 Location: Milky Way Galaxy: Planet Earth
Re: How many rules are there?
That's about 70,000.gameoflifemaniac wrote:I have found something (I can't find a adjective to describe this.). With only state colours the number of rules is 10^1.1372591694895835×10^22, but with icons it's 10^1.1372591694895837×10^22. This change is so slight!
Code: Select all
x = 81, y = 96, rule = LifeHistory
58.2A$58.2A3$59.2A17.2A$59.2A17.2A3$79.2A$79.2A2$57.A$56.A$56.3A4$27.
A$27.A.A$27.2A21$3.2A$3.2A2.2A$7.2A18$7.2A$7.2A2.2A$11.2A11$2A$2A2.2A
$4.2A18$4.2A$4.2A2.2A$8.2A!
 gameoflifemaniac
 Posts: 1099
 Joined: January 22nd, 2017, 11:17 am
 Location: There too
Re: How many rules are there?
70000 more or 70000 times more?Gamedziner wrote:That's about 70,000.gameoflifemaniac wrote:I have found something (I can't find a adjective to describe this.). With only state colours the number of rules is 10^1.1372591694895835×10^22, but with icons it's 10^1.1372591694895837×10^22. This change is so slight!
I was so socially awkward in the past and it will haunt me for my entire life.
Re: How many rules are there?
How are you even calculating that? Anyway, adding the icons increases the binary logarithm by thousands, which in turn means the actual number is unimaginably bigger.
succ
Re: How many rules are there?
How many LtL (Larger than Life) rules are there?
We have some dimensions given here, elaborated on here
R: Range, which must be between 1 and 10 inclusive.
C: State count, which must be between 2 and 25. I'm assuming this has no other effect in terms of the combinatorics.
M: Whether or not the central cell is included in the neighbour count. M1 if so, M0 if not.
We'll assume M1, so the central cell is included. The size of the neighbourhood is (2R+1)^2, and the amount of possible conditions (totalistic) is (2R+1)^2+1, to account for B0. We'll call this value P, for the possibilities.
S, B: The survival and birth outcomes. Each one consists of a pair of integers >=0 and <P.
The amount of possible combinations of two numbers like that would be P^2. This leaves you with redundant pairs, like S2..3 and S3..2. There are P nonredundant cases, where both numbers are equal. This means that collectively, the S and B cases have P^2+P possible values. We can use summation, and then we have all the possibilities of the S, B, and R conditions, but we have to account for M first.
We must do S and B again, but not counting the center. This time, P=P1, so that part of the equation is repeated with this different P equation. We'll call the amount of LtL rules "LT":
We then multiply this by 24 to account for C. However, we then need to account for another variable.
N: The neighbourhood type, which can be either Moore or Von Neumann.
We've only got half of the equation. Now, we simply need a different way to figure out P with the Von Neumann neighbourhood. I'll assume it works like this:
It looks like two square grids at 45 degrees, overlaid on each other in a checkered pattern. I'll use (R^2+(R+1)^2+1) for M1.
In conclusion, In order, the four segments are the following cases: M1,NM  M0,NM  M1,NN  M0,NN
I'd be surprised if there turn out to be no mistakes anywhere in that reasoning.
This equation also doesn't account for how If "M1" is present, there can be no S0 condition, nor does it account for general redundancies. As such, it's a bit of a parker square, but I've already spent enough time on this.
We have some dimensions given here, elaborated on here
R: Range, which must be between 1 and 10 inclusive.
C: State count, which must be between 2 and 25. I'm assuming this has no other effect in terms of the combinatorics.
M: Whether or not the central cell is included in the neighbour count. M1 if so, M0 if not.
We'll assume M1, so the central cell is included. The size of the neighbourhood is (2R+1)^2, and the amount of possible conditions (totalistic) is (2R+1)^2+1, to account for B0. We'll call this value P, for the possibilities.
S, B: The survival and birth outcomes. Each one consists of a pair of integers >=0 and <P.
The amount of possible combinations of two numbers like that would be P^2. This leaves you with redundant pairs, like S2..3 and S3..2. There are P nonredundant cases, where both numbers are equal. This means that collectively, the S and B cases have P^2+P possible values. We can use summation, and then we have all the possibilities of the S, B, and R conditions, but we have to account for M first.
We must do S and B again, but not counting the center. This time, P=P1, so that part of the equation is repeated with this different P equation. We'll call the amount of LtL rules "LT":
We then multiply this by 24 to account for C. However, we then need to account for another variable.
N: The neighbourhood type, which can be either Moore or Von Neumann.
We've only got half of the equation. Now, we simply need a different way to figure out P with the Von Neumann neighbourhood. I'll assume it works like this:
Code: Select all
R=1
. . . . .
. . # . .
. # o # .
. . # . .
. . . . .
R=2
. . # . .
. # # # .
# # o # #
. # # # .
. . # . .
In conclusion, In order, the four segments are the following cases: M1,NM  M0,NM  M1,NN  M0,NN
I'd be surprised if there turn out to be no mistakes anywhere in that reasoning.
This equation also doesn't account for how If "M1" is present, there can be no S0 condition, nor does it account for general redundancies. As such, it's a bit of a parker square, but I've already spent enough time on this.
succ
Re: How many rules are there?
The recently released Golly 3.0b1 allows the range to go up to 50. (Not sure whether that will be so in the final 3.0 release  patterns with large ranges tend to run very slowly, especially when near a grid edge.)blah wrote:R: Range, which must be between 1 and 10 inclusive.
I'm pretty sure that 25 is a typo by Mirek. MCell (and Golly 3.0b1) allows C to go up to 255. (Actually, I don't see any reason why it couldn't go up to 256 but I decided to stick with MCell's limit for now.)C: State count, which must be between 2 and 25.

 Posts: 795
 Joined: May 30th, 2016, 8:47 pm
 Location: Milky Way Galaxy: Planet Earth
Re: How many rules are there?
70000 more.gameoflifemaniac wrote: 70000 more or 70000 times more?
Code: Select all
x = 81, y = 96, rule = LifeHistory
58.2A$58.2A3$59.2A17.2A$59.2A17.2A3$79.2A$79.2A2$57.A$56.A$56.3A4$27.
A$27.A.A$27.2A21$3.2A$3.2A2.2A$7.2A18$7.2A$7.2A2.2A$11.2A11$2A$2A2.2A
$4.2A18$4.2A$4.2A2.2A$8.2A!
Re: How many rules are there?
Last I checked, 2^7558200 > 70,000. Also, the entire value gets multiplied by that, so adding the icons is not even remotely equivalent to adding 70,000. Unless you mean it's added to the base 10 logarithm, but even then I'm not sure.Gamedziner wrote:70000 more.gameoflifemaniac wrote: 70000 more or 70000 times more?
succ
Re: How many rules are there?
I will now make further adjustments to my LT equation.
I believe that two CA can be considered different if one or both of these conditions is met:
1. For at least one possible initial configuration, the two rules will produce different results.
2. The rules have different amounts of possible states.
By this standard, we have to rethink stuff. M is completely redundant; the S and B conditions already know the state of the center cell, and can add or subtract that from their conditions. Therefore, M need not be part of the equation.
M also introduced the problem of M1,S0 and the equal opposite with M1,Bx, x being the highest possible neighbour count. These cases are nonexistent. We can solve this problem by simply removing the center cell from the combinatorics. For convenience, we will then define functions for the number of possible cases in Von Neumann and Moore neighbourhoods of range R:
I think that's the proper equation for LT. 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. As such, we may define the amount of rules golly can now simulate (with corrections from my older equations, see edit on this post):
G0 is the amount of unique rules Golly can simulate (counting reflections and rotations as different rules).
G1 adds the different possible colour schemes.
G2 also includes the different possible icons.
If you can, please point out any mistakes. I hope nobody else has already done the maths before me...
EDIT: I've noticed a mistake in the LT equation, which is also present in my older LT equations. I wrote v(R) with a minus instead of a plus. I have corrected this in my image (LT4.png).
I believe that two CA can be considered different if one or both of these conditions is met:
1. For at least one possible initial configuration, the two rules will produce different results.
2. The rules have different amounts of possible states.
By this standard, we have to rethink stuff. M is completely redundant; the S and B conditions already know the state of the center cell, and can add or subtract that from their conditions. Therefore, M need not be part of the equation.
M also introduced the problem of M1,S0 and the equal opposite with M1,Bx, x being the highest possible neighbour count. These cases are nonexistent. We can solve this problem by simply removing the center cell from the combinatorics. For convenience, we will then define functions for the number of possible cases in Von Neumann and Moore neighbourhoods of range R:
I think that's the proper equation for LT. 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. As such, we may define the amount of rules golly can now simulate (with corrections from my older equations, see edit on this post):
G0 is the amount of unique rules Golly can simulate (counting reflections and rotations as different rules).
G1 adds the different possible colour schemes.
G2 also includes the different possible icons.
If you can, please point out any mistakes. I hope nobody else has already done the maths before me...
EDIT: I've noticed a mistake in the LT equation, which is also present in my older LT equations. I wrote v(R) with a minus instead of a plus. I have corrected this in my image (LT4.png).
Last edited by blah on July 1st, 2017, 11:39 am, edited 1 time in total.
succ
 gameoflifemaniac
 Posts: 1099
 Joined: January 22nd, 2017, 11:17 am
 Location: There too
Re: How many rules are there?
What does Lt mean?
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? And in the formula sum (n=1 to 256) n^n^9 include for example JvN29?
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? And in the formula sum (n=1 to 256) n^n^9 include for example JvN29?
I was so socially awkward in the past and it will haunt me for my entire life.

 Posts: 795
 Joined: May 30th, 2016, 8:47 pm
 Location: Milky Way Galaxy: Planet Earth
Re: How many rules are there?
I didn't realize that was in a base 10 logarithm; never mind!blah wrote:Last I checked, 2^7558200 > 70,000. Also, the entire value gets multiplied by that, so adding the icons is not even remotely equivalent to adding 70,000. Unless you mean it's added to the base 10 logarithm, but even then I'm not sure.Gamedziner wrote:70000 more.gameoflifemaniac wrote: 70000 more or 70000 times more?
However, that also means the number of rules (10^1.1372591694895837×10^22) can be simplified to (10^23.1372591694895837).
Code: Select all
x = 81, y = 96, rule = LifeHistory
58.2A$58.2A3$59.2A17.2A$59.2A17.2A3$79.2A$79.2A2$57.A$56.A$56.3A4$27.
A$27.A.A$27.2A21$3.2A$3.2A2.2A$7.2A18$7.2A$7.2A2.2A$11.2A11$2A$2A2.2A
$4.2A18$4.2A$4.2A2.2A$8.2A!