Life object having a bounded population with an unknown fate
Life object having a bounded population with an unknown fate
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
- gameoflifemaniac
- Posts: 1242
- Joined: January 22nd, 2017, 11:17 am
- Location: There too
Re: Life object having a bounded population with an unknown fate
Amazing!
By the way, how about a stable pattern that generates the 3n+1 sequence? I know that its fate will be known, but the Collatz sequence generator from triller's p30 thread is bounded. This new pattern would be unbounded.
By the way, how about a stable pattern that generates the 3n+1 sequence? I know that its fate will be known, but the Collatz sequence generator from triller's p30 thread is bounded. This new pattern would be unbounded.
I was so socially awkward in the past and it will haunt me for the rest of my life.
Code: Select all
b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!
Re: Life object having a bounded population with an unknown fate
In mathematics, there are some cases when it is proven that a question cannot be answered. I do not know if this Collatz-like sequence is looped or not, wonder if anyone else had more information about it.
Mainly offtopic, but I just realized that you must be that David Bell who published many cool CA-related stuff decades ago - sorry if you'd been decloaked earlier here . Well, join to be manipulated: how about constructing a Wolfram-110 Unit cell in Day & Night? Allegedly you have many results in that rule. I am not too lazy to create such Unit cell, just not familiar with DN stuff, guns, gunless logic etc.
Mainly offtopic, but I just realized that you must be that David Bell who published many cool CA-related stuff decades ago - sorry if you'd been decloaked earlier here . Well, join to be manipulated: how about constructing a Wolfram-110 Unit cell in Day & Night? Allegedly you have many results in that rule. I am not too lazy to create such Unit cell, just not familiar with DN stuff, guns, gunless logic etc.
Re: Life object having a bounded population with an unknown fate
Ooooh, an irresistible request! -- though it's mostly only irresistible because it's so improbably easy.gameoflifemaniac wrote:By the way, how about a stable pattern that generates the 3n+1 sequence? I know that its fate will be known, but the Collatz sequence generator from triller's p30 thread is bounded. This new pattern would be unbounded.
Turns out it's possible to convert the 5n+1 Collatz sequence generator into a working 3n+1 Collatz sequence generator by adding three eaters on the correct lanes.
Technically you only need to add nine cells to the pattern at T=0, but that might be a little harder to figure out. ... Actually, probably six cells are enough, or possibly three, but that might take a custom-written search program to find -- and it would be a little messy and I'm not sure there's much point.
Anyway, nine cells is the minimum addition that I can think of offhand -- so if you can patch the pattern to get the 3n+1 Collatz sequence in eight cells or less, well, I guess you win!
The pattern is so nicely labeled that with sufficient motivation, anybody should be able to sort out where to put the eaters, at least. Anyone interested in figuring it out?
The modified sequence generator will calculate
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
at which point the block absorbs the passing test signal and the entire pattern goes stable.
Minor bonus: if you find the edge shooter (syringe + Fx77 + Fx119 inserter) and matching Snark that are responsible for doing that test for the "1" block location, you can move the edge shooter and Snark one cell diagonally southeast, and then you'll get an oscillator instead of a stable pattern -- 4 2 1 4 2 1 4 2 1 forever.
EDIT: To be specific, that (4,2,1) cycle repeats every 33,183,771 ticks. I was hoping that would happen to be a prime number, but it's three times a prime. I think it _could_ have been a prime, though -- I don't think it's significant that the cycle has a length of three. The 3n+1 step ought to take a different amount of time than the two n/2 steps. But I haven't checked to be sure.
Another side note: if you run the 5n+1 Collatz pattern with a starting value of 5 (instead of 7) you also end up with an oscillator, with a much larger period: 1,641,035,756. The cycle there is (13, 66, 33, 166, 83, 416, 208, 104, 52, 26).
Here's a little more detail about these oscillators and HashLife, from a recent offline email exchange:
dvgrn wrote:The repeat time for the N=5 case is 1641035756 ticks, which is 2 x 2 xdbell wrote:> Running it with N=5 which does cycle, my golly never managed to
> show any speedup. I might have thought that it would be able to
> cache that, and then run away.
89 x 4609651. So you'd need to store some large multiple of 410
million hashtiles (89 x 4609651) before Golly could really run away
with this version. Have to give Moore's Law a few more years for that
one, I guess.
If you thought about it for long enough, you _could_ figure out how to
put in a fixed delay of exactly the right length that would allow
HashLife to run away very easily with the N=5 case. For example, if
you added a delay of 265,393,154 ticks to every calculation cycle, I
think you'd end up with a power of two period. But of course any
small prime times a power of two would be fine, too.
- gameoflifemaniac
- Posts: 1242
- Joined: January 22nd, 2017, 11:17 am
- Location: There too
Re: Life object having a bounded population with an unknown fate
Where should I change the pattern?dvgrn wrote:Ooooh, an irresistible request! -- though it's mostly only irresistible because it's so improbably easy.gameoflifemaniac wrote:By the way, how about a stable pattern that generates the 3n+1 sequence? I know that its fate will be known, but the Collatz sequence generator from triller's p30 thread is bounded. This new pattern would be unbounded.
Turns out it's possible to convert the 5n+1 Collatz sequence generator into a working 3n+1 Collatz sequence generator by adding three eaters on the correct lanes.
Technically you only need to add nine cells to the pattern at T=0, but that might be a little harder to figure out. ... Actually, probably six cells are enough, or possibly three, but that might take a custom-written search program to find -- and it would be a little messy and I'm not sure there's much point.
Anyway, nine cells is the minimum addition that I can think of offhand -- so if you can patch the pattern to get the 3n+1 Collatz sequence in eight cells or less, well, I guess you win!
The pattern is so nicely labeled that with sufficient motivation, anybody should be able to sort out where to put the eaters, at least. Anyone interested in figuring it out?
The modified sequence generator will calculate
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
at which point the block absorbs the passing test signal and the entire pattern goes stable.
Minor bonus: if you find the edge shooter (syringe + Fx77 + Fx119 inserter) and matching Snark that are responsible for doing that test for the "1" block location, you can move the edge shooter and Snark one cell diagonally southeast, and then you'll get an oscillator instead of a stable pattern -- 4 2 1 4 2 1 4 2 1 forever.
EDIT: To be specific, that (4,2,1) cycle repeats every 33,183,771 ticks. I was hoping that would happen to be a prime number, but it's three times a prime. I think it _could_ have been a prime, though -- I don't think it's significant that the cycle has a length of three. The 3n+1 step ought to take a different amount of time than the two n/2 steps. But I haven't checked to be sure.
Another side note: if you run the 5n+1 Collatz pattern with a starting value of 5 (instead of 7) you also end up with an oscillator, with a much larger period: 1,641,035,756. The cycle there is (13, 66, 33, 166, 83, 416, 208, 104, 52, 26).
Here's a little more detail about these oscillators and HashLife, from a recent offline email exchange:
dvgrn wrote:The repeat time for the N=5 case is 1641035756 ticks, which is 2 x 2 xdbell wrote:> Running it with N=5 which does cycle, my golly never managed to
> show any speedup. I might have thought that it would be able to
> cache that, and then run away.
89 x 4609651. So you'd need to store some large multiple of 410
million hashtiles (89 x 4609651) before Golly could really run away
with this version. Have to give Moore's Law a few more years for that
one, I guess.
If you thought about it for long enough, you _could_ figure out how to
put in a fixed delay of exactly the right length that would allow
HashLife to run away very easily with the N=5 case. For example, if
you added a delay of 265,393,154 ticks to every calculation cycle, I
think you'd end up with a power of two period. But of course any
small prime times a power of two would be fine, too.
I was so socially awkward in the past and it will haunt me for the rest of my life.
Code: Select all
b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!
Re: Life object having a bounded population with an unknown fate
Ow! Don't quote an entire post to ask a one-line question -- it makes everyone have to scroll too much, and reminds me that I use way too many words.gameoflifemaniac wrote:Where should I change the pattern?dvgrn wrote:HUGE LONG QUOTE
The challenge is to figure out how to patch the pattern yourself. It may not seem like it, but the information that it can be done with three eaters -- i.e., by blocking off three signal paths so that the inputs don't get there -- is potentially a very useful clue.
Most places, if you block off even one signal, the pattern simply goes stable and stops working at all. Where are the exceptions to that? And also, which part of the circuitry is doing the multiplying by five? You can figure that out just by watching what part of the circuitry is active when a block is being pushed out to its new 5n+1 location.
So how do you want that circuit to work a little differently, to change that 5n+1 multiplication into a 3n+1 multiplication? And how can that be done just by blocking off three input signals in that circuit?
Re: Life object having a bounded population with an unknown fate
Credit where credit is due (I'm HUGE on provenance).
While my handle is evoked, the originator of the collatz generator is PM 2RING. See here.
viewtopic.php?f=2&t=81&p=2103&hilit=collatz#p2103.
triller
While my handle is evoked, the originator of the collatz generator is PM 2RING. See here.
viewtopic.php?f=2&t=81&p=2103&hilit=collatz#p2103.
triller
The most exciting phrase to hear in science, the one that heralds new
discoveries, is not "Eureka!" (I found it!) but "That's funny ..."
-- Isaac Asimov
discoveries, is not "Eureka!" (I found it!) but "That's funny ..."
-- Isaac Asimov
Re: Life object having a bounded population with an unknown fate
Here are a few more details about my Collatz 5N+1 simulator.
The zero test and the parity detection units of the pattern both use the following reaction of three gliders, which is just two 180-degree kickbacks in succession.
The block at the left is too far away and so the two kickbacks proceed normally creating an output glider to the left.
The block at the right is just within range and therefore deletes both itself and the first kickback, allowing the remaining glider to become an output to the right.
The zero detection unit in addition contains a 'glider snatcher' to extract the glider if comes out of the detector to the left. The snatcher is needed so that a glider travelling from lane N to lane T to create a block during the COPY operation doesn't run into anything. The glider snatcher was described in a previous posting.
The parity detection unit performs two of the block detection reactions in sequence one diagonal cell apart, with the lower test tried first. The lower test is for the odd parity case, and the upper test is for the even parity case. The even test unit is placed in the middle of the odd test unit. When a test block is pulled down two cells at a time into range, the appropriate detection will take place.
The complexity of the parity circuit is due to the disentangling of the multiple input and output gliders which are on very close paths. A couple of other kickbacks are used in the parity unit to extract the output gliders in the left and right sides of the first of the two tests.
The switch used in the simulator was essentially presented in a previous posting, but here it is shown as it is actually used. It is located a little left of the parity detection unit. It accepts four input gliders, labelled here by 1 to 4 tubs. Note that they actually only arrive one at a time in the correct order. The default state for the switch is for the odd case.
Glider 1 arrives when the parity detector detects an even value. It moves an internal block to set the switch to the even case.
Glider 2 arrives when the zero test unit doesn't detect a block. It triggers the switch to emit the appropriate output glider. When the switch is set for the odd case, an output glider goes to the lower right. When the switch is set for the even case, an output glider goes to the lower left.
Glider 3 arrives when the parity detector detects an odd value. It creates a boat to indicate that the switch is set for the odd state.
Glider 4 arrives when the zero test detects a block indicating that looping is done. It resets the switch to its default odd state, by either deleting a boat or moving the internal block in the switch.
It is possible to shrink the simulator if you want. Most of the salvo shooters can be shifted to the upper left as far as possible, with the appropriate routing of the gliders. The only tricky one is the parity detection unit, which can only be moved by multiples of two cells. (If it was moved by an odd amount, the parity check would be backwards.)
The two sides can be moved closer together too. The block produced by the COPY operation is still made correctly by any such change.
Finally, my original idea many years ago was to built a Collatz 3N+1 simulator as my unknown fate object. That would have required a third sliding block memory lane and another COPY operation, so that it could test every number in sequence to see whether they all iterate down to 1.
Dean Hickerson suggested that I used the Collatz 5N+1 algorithm instead since it was simpler. Thanks, Dean, for that suggestion.
BCNU,
-dbell
The zero test and the parity detection units of the pattern both use the following reaction of three gliders, which is just two 180-degree kickbacks in succession.
Code: Select all
#C A reaction based on two kickbacks that can detect a block.
#C Two copies of the reaction are shown with the right block positioned
#C one diagonal cell closer to the kickbacks than the left block.
x = 66, y = 25
13boo$13boo7bo33boo6bo$21bo34boo5bo$21b3o39b3o6$9boo40boo$8bobo39bobo$
10bo41bo11$oo40boo$boo40boo$o41bo!
The block at the right is just within range and therefore deletes both itself and the first kickback, allowing the remaining glider to become an output to the right.
The zero detection unit in addition contains a 'glider snatcher' to extract the glider if comes out of the detector to the left. The snatcher is needed so that a glider travelling from lane N to lane T to create a block during the COPY operation doesn't run into anything. The glider snatcher was described in a previous posting.
The parity detection unit performs two of the block detection reactions in sequence one diagonal cell apart, with the lower test tried first. The lower test is for the odd parity case, and the upper test is for the even parity case. The even test unit is placed in the middle of the odd test unit. When a test block is pulled down two cells at a time into range, the appropriate detection will take place.
The complexity of the parity circuit is due to the disentangling of the multiple input and output gliders which are on very close paths. A couple of other kickbacks are used in the parity unit to extract the output gliders in the left and right sides of the first of the two tests.
The switch used in the simulator was essentially presented in a previous posting, but here it is shown as it is actually used. It is located a little left of the parity detection unit. It accepts four input gliders, labelled here by 1 to 4 tubs. Note that they actually only arrive one at a time in the correct order. The default state for the switch is for the odd case.
Code: Select all
#C Switch for Collatz 5N+1 simulator showing its input gliders.
x = 217, y = 163
93boo3boo$91b3obobboo$90bo4bo$90bobboob4o$10bo78boobobobobbo$11bo78bob
obobo$9b3o78boboboo$bo89bo$obo$bo102boo$95boo7bo$95boo5bobo$102boo7$
92boo$93bo$90b3o$90bo7$120bo$102boo14b5o$103bo13bo5bo$103bobo12b3obbo$
104boo15boboo$118b4obbo27bo11boo$113boo3bo3boo27bobo10boo$113boo4b3o
21bo3boobbobo$121bo20bobobbobbooboo$78boo41boboo3boo12bobo3bobo$79bo
40booboo4bo13bob4obboboo$79bobo47bobo13bo3boboboo$80boo48boo12bo3bobo$
112boo29bo3bobo$112bo30boo3bo$113b3o6bo$115bo4b3o$119bo$106boo11boo35b
oo$106boo48boo$171boo$170bobbo$171boobo$174bo$174boo$33boo124boo$34bo
125bo$34bobo29boo13boo48boo24b3o$35boo29boo13boo11boo35boo11boo11bo$
94bo49bo$95b3o47b3o$97bo49bo$$127boo$105boo20bo$104bobo21b3o$104bo25bo
$103boo$43boo63bo11boo$43boo62bobo10boo$107bobo$105b3oboo$57boo45bo$
57bo47b3oboo$58b3o46boboo$60bo$47boo$48bo49boo$45b3o51bo$45bo53bobo$
100boo$112boo$112boo$127boo$126bobbo$127boobo$130bo$130boo79bo3bo$115b
oo93bobobobo$116bo94bo3bo$113b3o85b3o$113bo87bo$202bo21$162bo3bo3bo$
161bobobobobobo$162bo3bo3bo$$151b3o$151bo$152bo38$186bo3bo3bo3bo$185bo
bobobobobobobo$186bo3bo3bo3bo$$174b3o$174bo$175bo!
Glider 2 arrives when the zero test unit doesn't detect a block. It triggers the switch to emit the appropriate output glider. When the switch is set for the odd case, an output glider goes to the lower right. When the switch is set for the even case, an output glider goes to the lower left.
Glider 3 arrives when the parity detector detects an odd value. It creates a boat to indicate that the switch is set for the odd state.
Glider 4 arrives when the zero test detects a block indicating that looping is done. It resets the switch to its default odd state, by either deleting a boat or moving the internal block in the switch.
It is possible to shrink the simulator if you want. Most of the salvo shooters can be shifted to the upper left as far as possible, with the appropriate routing of the gliders. The only tricky one is the parity detection unit, which can only be moved by multiples of two cells. (If it was moved by an odd amount, the parity check would be backwards.)
The two sides can be moved closer together too. The block produced by the COPY operation is still made correctly by any such change.
Finally, my original idea many years ago was to built a Collatz 3N+1 simulator as my unknown fate object. That would have required a third sliding block memory lane and another COPY operation, so that it could test every number in sequence to see whether they all iterate down to 1.
Dean Hickerson suggested that I used the Collatz 5N+1 algorithm instead since it was simpler. Thanks, Dean, for that suggestion.
BCNU,
-dbell