A good test for 'correctness' is to run the F-pentomino both in some known good program and your own.
It looks like this:
xx
xx
x
I's a really interesting little pattern that will expand quite a bit before stabilizing, it also fires off a bunch of gliders.
edit: I've looked a bit more at your code, and it is almost correct for free-running instances of 'cell'.
The problem is with the generation counter, you only have 1 bit for the generation.
In a synchronous environment that would work, and because you propagate the 'update' signal from the first cell that is hit outward you will (probably) observe correct behaviour.
But that is not the same as having cells completely independent.
The connecting cells are all triggered from the first cell that gets hit. If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong.
I figure the absolute minimum number of bits in the generation counter is 2, because then you have one 'dead' state in between the 3 possibilities that are current.
A neighbour can be 'ahead', at the same generation or it can be 'behind' and what a cell does should be governed by the states of the neighbours.
In your program you can never get in to the 'behind' state, but in a free-running hardware solution that is a definite possibility.
I hope that's all clear :)
Think of it this way, effectively you've made your cells globally clocked again.
You also can't delete dead cells, two populations that were connected at some point in the past should stay connected or they will drift away from each other.
If a 'cell' is run by a completely independent thread which runs at some arbitrary speed the whole thing should still work.
Simulating asynchronous devices on synchronous devices is quite tricky!
> If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong.
Say we have two cells next to each other. It would go wrong if one cell is triggered twice in a row without the other cell being triggered in the meantime.
So I think I didn't understand the goal. So the goal is to have the system still behave correctly with any sequence op c.update() calls? E.g. if I choose do do cells[(0,0)].update() 10 times in a row it should still work.
This fix took 5 minutes. I actually used a gen counter and self.state[self.gen%2] before, so changing that to %3 wasn't much work :)
The other change was:
if any(cells[n].gen < self.gen for n in neighbors if n in cells):
return
And I removed the code do delete empty cells. I thought about removing empty cells and obviously you can remove them in some cases. But in general it's undecidable I think because life is turing complete and you don't know if some group of cells is going to shoot a glider to another group, so to be safe you have to keep them in sync.
Is this version correct now? I'm not sure...it seems to execute the examples correctly but maybe it will go wrong if you call update in just the right pattern.
I can't get it to work though, because of the swing stuff.
I tried running it under jython but that gives me a syntax error, and in regular python the I get an import error. ('No module named javax').
I can't verify if it is correct without being able to run it, but you can try that F pentomino and then use 'hashlife' or 'golly' to verify that it works properly.
The F pentomino is complex enough in its output that I think that if it does that it will work on arbitrary patterns.
As for deletions, since this is only a simulation it is an optimization, in an actual fabric you would not be deleting cells.
The trick to deletions I think is that you can only delete a cell if the neighbours around it are not going to be disconnected by the deletion.
Now you have a problem though, which needs supervision or abtration. This is because if two cells delete themselves at the same time that could cause two populations to become disconnected.
That's exactly the kind of issue I tried to resolve by scheduling the instructions so carefully.
So, I'm curious if it really works for more complex structures.
All you'd need to do is change the default set and let it run for 1116 generations , then it should be stable.
Oh, and I think %3 should be %4, %3 is somewhere between 1 and 2 bits and you really need two bits.
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.
The end state of golly and this seem to match up but I only eyeballed it (it seems highly unlikely that the end state would be this similar but not exactly the same).
Comments
Neat !
A good test for 'correctness' is to run the F-pentomino both in some known good program and your own.
It looks like this:
I's a really interesting little pattern that will expand quite a bit before stabilizing, it also fires off a bunch of gliders.edit: I've looked a bit more at your code, and it is almost correct for free-running instances of 'cell'.
The problem is with the generation counter, you only have 1 bit for the generation.
In a synchronous environment that would work, and because you propagate the 'update' signal from the first cell that is hit outward you will (probably) observe correct behaviour.
But that is not the same as having cells completely independent.
The connecting cells are all triggered from the first cell that gets hit. If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong.
I figure the absolute minimum number of bits in the generation counter is 2, because then you have one 'dead' state in between the 3 possibilities that are current.
A neighbour can be 'ahead', at the same generation or it can be 'behind' and what a cell does should be governed by the states of the neighbours.
In your program you can never get in to the 'behind' state, but in a free-running hardware solution that is a definite possibility.
I hope that's all clear :)
Think of it this way, effectively you've made your cells globally clocked again.
You also can't delete dead cells, two populations that were connected at some point in the past should stay connected or they will drift away from each other.
If a 'cell' is run by a completely independent thread which runs at some arbitrary speed the whole thing should still work.
Simulating asynchronous devices on synchronous devices is quite tricky!
> If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong.
Say we have two cells next to each other. It would go wrong if one cell is triggered twice in a row without the other cell being triggered in the meantime.
So I think I didn't understand the goal. So the goal is to have the system still behave correctly with any sequence op c.update() calls? E.g. if I choose do do cells[(0,0)].update() 10 times in a row it should still work.
Here's the updated version: http://pastebin.com/f72c576d3
This fix took 5 minutes. I actually used a gen counter and self.state[self.gen%2] before, so changing that to %3 wasn't much work :)
The other change was:
And I removed the code do delete empty cells. I thought about removing empty cells and obviously you can remove them in some cases. But in general it's undecidable I think because life is turing complete and you don't know if some group of cells is going to shoot a glider to another group, so to be safe you have to keep them in sync.Is this version correct now? I'm not sure...it seems to execute the examples correctly but maybe it will go wrong if you call update in just the right pattern.
BTW does the code run on your computer?
That looks better like that.
I can't get it to work though, because of the swing stuff.
I tried running it under jython but that gives me a syntax error, and in regular python the I get an import error. ('No module named javax').
I can't verify if it is correct without being able to run it, but you can try that F pentomino and then use 'hashlife' or 'golly' to verify that it works properly.
The F pentomino is complex enough in its output that I think that if it does that it will work on arbitrary patterns.
As for deletions, since this is only a simulation it is an optimization, in an actual fabric you would not be deleting cells.
The trick to deletions I think is that you can only delete a cell if the neighbours around it are not going to be disconnected by the deletion.
Now you have a problem though, which needs supervision or abtration. This is because if two cells delete themselves at the same time that could cause two populations to become disconnected.
That's exactly the kind of issue I tried to resolve by scheduling the instructions so carefully.
So, I'm curious if it really works for more complex structures.
All you'd need to do is change the default set and let it run for 1116 generations , then it should be stable.
Oh, and I think %3 should be %4, %3 is somewhere between 1 and 2 bits and you really need two bits.
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.
Here's a screenshot: http://img715.imageshack.us/img715/2976/asynclife.png
The end state of golly and this seem to match up but I only eyeballed it (it seems highly unlikely that the end state would be this similar but not exactly the same).