The F-pentomino works, but it is VERY slow because gliders fly away and this increases the number of cells a lot O(generation) space and O(generation^2) time.
> Oh, and I think %3 should be %4, %3 is somewhere between 1 and 2 bits and you really need two bits.
Hmm. Two cells that are next to each other can never be more than 1 generation apart, right? For example if we have cells AB then if A is in generation 10 then B can be in generation 9, 10 or 11. This happens when we call update on A:
- if B is in generation 9 we do nothing
- if B is in generation 10 we use its current value
- if B is in generation 11 we use its previous value
So really you only need to remember 2 generations (current and previous). So that would be gen%2 instead of gen%3 or gen%4...what am I missing?
When two adjacent cells are only 1 generation apart that can lead to a cell being created that is two generations away from a neighbour. It took me a while to clue in to what was happening there.
So you are correct in that you only need the two states stored, that is fine.
But the generation counter needs to have at least two full bits. 1.5 bits isn't a value to begin with in electronics, and when two populations that are synchronized via some tenuous link meet you need to guarantee that there will not be a mis interpretation of the states. For instance (not sure if this will come out ok):
3 3 0 0
3 3 3 3 1 1
2 2 2 2 2 2 2 2
Is consistent. Now if an empty cell is created between the topmost 3 and 0 it would depend on which cell caused the creation how it would interpret the value of its neigbour.
In a 'true' fabric this would not occur (because all the dead cells would exist at all times), so in this case it is an artifact of the creation of cells.
But in logic there would be no way to know who is 'ahead' when counting from 0 to 2 only, that's why you need the third possibility (modulo 3 counting), which when you make it simple hardware automatically becomes modulo 4 (otherwise you get a whole pile of gates more to use less state!).
So the generation counters would end up being 2 bits each, or two bits with a 'reset' happing at the fourth state, effectively making them 3 positions, each output from the two bit counters would go in to a 1 selected output for 4 bits input (so 16 outputs, or in your 1.5 bits case 1 out of 9) demultiplexer which would select the right combination of previous/current generation states to be used.
That's quite doable. So the effect would be completely free-running life cells that stay within one step of all their neighbours at all time.
It is very tempting to actually go and wire this up.
edit: hm, I see I'm contradicting myself here, you are right, a count of 3 should be sufficient in actual logic, it is the imperfection of the simulation that causes the problem, if all cells existed at all times 3 would be enough. But it would still require two lines for the generation to be transmitted to the neighbours.
So, in summary: two states, but 3 possibilities for the generation counter. Otherwise you can't tell who is ahead or behind, then 'different' is all you've got and you can't make the decision to wait.
Yes I think that's right. If all cells exist 2 possibilities for the generation counter is not enough, but 3 possibilities is. For example this rule works:
01 -- the 0 is behind
12 -- the 1 is behind
20 -- the 2 is behind
If you have non existing cells the generation counter needs to be able to go arbitrarily large (which is why it does in my program):
000 888
1 7
2 6
3 5
4444444
Lets go back to the situation where all cells exist.
In the game of life cells can only have 2 states (live or dead). In the asynchronous version they have 6 states: 2 for dead/alive * 3 for the generation counter. You could view the asynchronous version as another cellular automaton (with more possible states and different update rules).
I think you can write a procedure that takes the rules of a synchronous cellular automaton and returns a new cellular automaton that is the asynchronous version of the original.
So you could structure the program like this:
1) A function to convert an automaton to its asynchronous version
2) An asynchronous cellular automaton simulator. Instead of updating all cells in sync it updates randomly.
Edit: it's not hard actually. If the original has n states then the new one has 3n^2 states. The update rules are straightforward, but you get a huge number of them. E.g. for the game of life the original automaton has 2^9 rules (one for every possible 3x3 grid), and the asynchronous version has 12^9 rules.
Comments
The F-pentomino works, but it is VERY slow because gliders fly away and this increases the number of cells a lot O(generation) space and O(generation^2) time.
> Oh, and I think %3 should be %4, %3 is somewhere between 1 and 2 bits and you really need two bits.
Hmm. Two cells that are next to each other can never be more than 1 generation apart, right? For example if we have cells AB then if A is in generation 10 then B can be in generation 9, 10 or 11. This happens when we call update on A:
- if B is in generation 9 we do nothing
- if B is in generation 10 we use its current value
- if B is in generation 11 we use its previous value
So really you only need to remember 2 generations (current and previous). So that would be gen%2 instead of gen%3 or gen%4...what am I missing?
When two adjacent cells are only 1 generation apart that can lead to a cell being created that is two generations away from a neighbour. It took me a while to clue in to what was happening there.
So you are correct in that you only need the two states stored, that is fine.
But the generation counter needs to have at least two full bits. 1.5 bits isn't a value to begin with in electronics, and when two populations that are synchronized via some tenuous link meet you need to guarantee that there will not be a mis interpretation of the states. For instance (not sure if this will come out ok):
Is consistent. Now if an empty cell is created between the topmost 3 and 0 it would depend on which cell caused the creation how it would interpret the value of its neigbour.In a 'true' fabric this would not occur (because all the dead cells would exist at all times), so in this case it is an artifact of the creation of cells.
But in logic there would be no way to know who is 'ahead' when counting from 0 to 2 only, that's why you need the third possibility (modulo 3 counting), which when you make it simple hardware automatically becomes modulo 4 (otherwise you get a whole pile of gates more to use less state!).
So the generation counters would end up being 2 bits each, or two bits with a 'reset' happing at the fourth state, effectively making them 3 positions, each output from the two bit counters would go in to a 1 selected output for 4 bits input (so 16 outputs, or in your 1.5 bits case 1 out of 9) demultiplexer which would select the right combination of previous/current generation states to be used.
That's quite doable. So the effect would be completely free-running life cells that stay within one step of all their neighbours at all time.
It is very tempting to actually go and wire this up.
edit: hm, I see I'm contradicting myself here, you are right, a count of 3 should be sufficient in actual logic, it is the imperfection of the simulation that causes the problem, if all cells existed at all times 3 would be enough. But it would still require two lines for the generation to be transmitted to the neighbours.
So, in summary: two states, but 3 possibilities for the generation counter. Otherwise you can't tell who is ahead or behind, then 'different' is all you've got and you can't make the decision to wait.
Correct ?
thanks!
Yes I think that's right. If all cells exist 2 possibilities for the generation counter is not enough, but 3 possibilities is. For example this rule works:
If you have non existing cells the generation counter needs to be able to go arbitrarily large (which is why it does in my program): Lets go back to the situation where all cells exist.In the game of life cells can only have 2 states (live or dead). In the asynchronous version they have 6 states: 2 for dead/alive * 3 for the generation counter. You could view the asynchronous version as another cellular automaton (with more possible states and different update rules).
I think you can write a procedure that takes the rules of a synchronous cellular automaton and returns a new cellular automaton that is the asynchronous version of the original.
So you could structure the program like this:
1) A function to convert an automaton to its asynchronous version
2) An asynchronous cellular automaton simulator. Instead of updating all cells in sync it updates randomly.
Edit: it's not hard actually. If the original has n states then the new one has 3n^2 states. The update rules are straightforward, but you get a huge number of them. E.g. for the game of life the original automaton has 2^9 rules (one for every possible 3x3 grid), and the asynchronous version has 12^9 rules.
Super stuff.
Ok, now to go and design the thing, you game ?
If so drop me an email. It's been a long long time since I've done gate level logic but this is a very interesting little project.
Do you mean with real hardware? I have never done any hardware stuff, but I'd like to learn. Where do I start? :)
Can you send me an email please, j@ww.com
This thread is getting overlong and is about to go out of sight for me, it's already on one of the last pages of my comment history.