How many rules are there?

[gameoflifemaniac]

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.

[AforAmpere]

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.

[muzik]

How many of these rules are apgsearchable, and how many of them allow for spaceships?

[gameoflifemaniac]

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.

Why 257? When I tried to type in the rule 12/34/257, it showed: 'The new rule is not valid in any algorithm.'
Maybe with your method some rules may be omitted? And have you counted only the 256-state rules without the rules with less than 256 states?

[AforAmpere]

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

[gameoflifemaniac]

This was a post that I wanted to delete, but I couldn't because it was already replied. Sorry!

[blah]

There are n^n^9 n-state 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 1-state 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:

It took me way too long to make this image

nn9.png (3.16 KiB) Viewed 12033 times

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'.

[gameoflifemaniac]

There are n^n^9 n-state 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 1-state 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:

nn9.png

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'.

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]

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:

nn92.png (4.38 KiB) Viewed 12015 times

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.

[AforAmpere]

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 in-between.

[blah]

How are either of those mistakes?

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 3-state 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.

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.

[AforAmpere]

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?

[blah]

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?

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.

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 24-bit 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^((n-1)*29640)
So, uhh...

The amount of rules RuleLoader can support. Nobody will ever need this.

goingtoofarinequationform.png (7.9 KiB) Viewed 11992 times

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

[blah]

Wait, I've just noticed RuleLoader doesn't actually let you make a rule with 1 state. I'll fix my equations tomorrow.

[gameoflifemaniac]

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!

[Gamedziner]

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!

That's about 70,000.

[gameoflifemaniac]

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!

That's about 70,000.

70000 more or 70000 times more?

[blah]

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.

[blah]

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 non-redundant 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=P-1, so that part of the equation is repeated with this different P equation. We'll call the amount of LtL rules "LT":

LT1.png (11.16 KiB) Viewed 11934 times

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 # #
. # # # .
. . # . .

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,

LT2.png (21.46 KiB) Viewed 11934 times

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.

[Andrew]

R: Range, which must be between 1 and 10 inclusive.

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.)

C: State count, which must be between 2 and 25.

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.)

[Gamedziner]

70000 more or 70000 times more?

70000 more.

[blah]

70000 more or 70000 times more?

70000 more.

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.

[blah]

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:

Thanks Andrew for corrections on some of the variable bounds

LT4.png (12.73 KiB) Viewed 11831 times

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):

G012.png (9.88 KiB) Viewed 11878 times

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).

[gameoflifemaniac]

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?

[Gamedziner]

70000 more or 70000 times more?

70000 more.

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.

I didn't realize that was in a base 10 logarithm; never mind!

However, that also means the number of rules (10^1.1372591694895837×10^22) can be simplified to (10^23.1372591694895837).