Life object having a bounded population with an unknown fate
Posted: December 10th, 2017, 3:19 am
Here is a Life object having a bounded population whose fate is unknown.
In particular, it is not known whether this object ever becomes stable, becomes a large period oscillator, or has a bounding box which grows erratically.
The circuit as shown emulates the Collatz 5N+1 algorithm with a starting value of 7. The algorithm is this:
For a particular number, if it is even, divide it by 2. Otherwise if it is odd, multiply it by 5 and add 1. Then iterate indefinitely.
For example, starting with 5, the algorithm produces the values 5, 26, 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, and at this point a cycle is reached.
Starting with 3, the algorithm produces the values 3, 16, 8, 4, 2, 1, 6, 3, and at this point a cycle is reached which includes 1.
Starting with 7, the algorithm produces the values 7, 36, 18, 9, 46, 23, 116, 58, 29, 146, 73, 366, 183, 916, 458, 229, 1146, and so on.
It is not currently known whether or not the algorithm starting with 7 ever enters a cycle.
Because of this, the same is true of the circuit.
The circuit uses two sliding block memories, called N and T. The N lane is on the left, and holds the current number. The T land is on the right, and holds one or two temporary numbers.
Salvos are sent on both lanes to manipulate the memories, with some salvos returning gliders indicating when a step is complete before proceeding to the next. In this way the population is guaranteed to remain bounded no matter how far away the blocks in the lanes get.
The salvo shooters are labeled to help understand the operation. The ones marked with a plus sign send back return gliders.
The algorithm starts with copying the block in lane N into lane T, and then splitting the block in lane T into two temporary blocks.
Then a parity test loop pulls down one of the temporary blocks in lane T two cells at a time, while using several nested kickback reactions to detect which of two lanes the block might have been pulled into.
After parity detection, a switch is set to remember which part of the algorithm is being calculated. Then a loop moves the N and T blocks simultaneously, until the remaining block in the T lane reaches position zero, in which case the cycle is restarted. Waiting is only needed for the N lane, since that lane is always longer then the T lane.
In the even case, N is pulled 1 cell while T is pulled 2 cells. In the odd case, N is pushed by 1 cell, and then N is pushed 4 cells while T is pulled 1 cell.
Note that to multiply a value by 5, the circuit pushes a block by 4 cells at a time, since the starting block already has one of the needed values (5N = 4N + N).
If the value 1 is ever reached, the object becomes stable since a glider collides with the block in lane N. If the test is removed then the small cycle starting with 1 is entered. Alternatively, it is easy to modify the circuit to emit a glider (without destroying the block) when the value 1 is detected. In this case, it would be unknown whether the pattern's population remains bounded or grows forever.
The position of the block in the N lane is marked using long boats every 10 cells for a while. Move the block diagonally to the upper left or lower right by a number of cells to run the pattern with other starting values, such as the two examples above.
Thanks to Dave Greene for his encouragement and ideas about some elements of the construction, especially for his wide boat maker.
The object could be tightened up and the glider paths adjusted a bit. But I wanted to send it out just as it was when it first worked.
BCNU,
-dbell
In particular, it is not known whether this object ever becomes stable, becomes a large period oscillator, or has a bounding box which grows erratically.
The circuit as shown emulates the Collatz 5N+1 algorithm with a starting value of 7. The algorithm is this:
For a particular number, if it is even, divide it by 2. Otherwise if it is odd, multiply it by 5 and add 1. Then iterate indefinitely.
For example, starting with 5, the algorithm produces the values 5, 26, 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, and at this point a cycle is reached.
Starting with 3, the algorithm produces the values 3, 16, 8, 4, 2, 1, 6, 3, and at this point a cycle is reached which includes 1.
Starting with 7, the algorithm produces the values 7, 36, 18, 9, 46, 23, 116, 58, 29, 146, 73, 366, 183, 916, 458, 229, 1146, and so on.
It is not currently known whether or not the algorithm starting with 7 ever enters a cycle.
Because of this, the same is true of the circuit.
The circuit uses two sliding block memories, called N and T. The N lane is on the left, and holds the current number. The T land is on the right, and holds one or two temporary numbers.
Salvos are sent on both lanes to manipulate the memories, with some salvos returning gliders indicating when a step is complete before proceeding to the next. In this way the population is guaranteed to remain bounded no matter how far away the blocks in the lanes get.
The salvo shooters are labeled to help understand the operation. The ones marked with a plus sign send back return gliders.
The algorithm starts with copying the block in lane N into lane T, and then splitting the block in lane T into two temporary blocks.
Then a parity test loop pulls down one of the temporary blocks in lane T two cells at a time, while using several nested kickback reactions to detect which of two lanes the block might have been pulled into.
After parity detection, a switch is set to remember which part of the algorithm is being calculated. Then a loop moves the N and T blocks simultaneously, until the remaining block in the T lane reaches position zero, in which case the cycle is restarted. Waiting is only needed for the N lane, since that lane is always longer then the T lane.
In the even case, N is pulled 1 cell while T is pulled 2 cells. In the odd case, N is pushed by 1 cell, and then N is pushed 4 cells while T is pulled 1 cell.
Note that to multiply a value by 5, the circuit pushes a block by 4 cells at a time, since the starting block already has one of the needed values (5N = 4N + N).
If the value 1 is ever reached, the object becomes stable since a glider collides with the block in lane N. If the test is removed then the small cycle starting with 1 is entered. Alternatively, it is easy to modify the circuit to emit a glider (without destroying the block) when the value 1 is detected. In this case, it would be unknown whether the pattern's population remains bounded or grows forever.
The position of the block in the N lane is marked using long boats every 10 cells for a while. Move the block diagonally to the upper left or lower right by a number of cells to run the pattern with other starting values, such as the two examples above.
Thanks to Dave Greene for his encouragement and ideas about some elements of the construction, especially for his wide boat maker.
The object could be tightened up and the glider paths adjusted a bit. But I wanted to send it out just as it was when it first worked.
BCNU,
-dbell