The transducer itself can be implemented in a variety of ways, including by duplicating a window of 3 consecutive gliders and applying logic to implement rule 110. However, the following pattern uses something that just happens to work for rule 110 and might have a very simple implementation in Life (better, I hope, than the solution below).
Define a counter with two inputs. The first is "reset to 0" and the other is "increment." For present purposes, we only need to be able to count to 2, and are prevented from counting any higher by the logic before resetting to 0.
Define the following boolean variables:
Code: Select all
c0 counter=0
c1 counter=1
c2 counter=2
x next input bit
res reset counter to 0
inc increment counter
y output
Then we can use the following logic (there are other ways, but this works well in Life collisions).
Code: Select all
res=not c0 and not x # next bit is 0 and counter is not already 0
inc=not c2 and x # next bit is 1 and counter is not already 2
y=(x and c0) or c1 or (not x and c2) # output is x for 00x, 10x, 1 for 01x, and not x for 11x
Code: Select all
#C [[ STEP 50 ]]
x = 4797, y = 4874, rule = B3/S23
4729b2o$4729b2o4$4730bo$4729b3o$4728bo3bo$4727bob3obo$4728b5o6$4729bo
2b2o$4729bobo$4728b2o$4727b2o29b2o$4727b2obo27b2o16b2o$4728b3o45b2o2$
4757b3o$4729b2o3b2o21b3o$4732bo35b2o$4729bo5bo31bobo6b3o$4721bobo6b2ob
2o31b3o7b3o$4721b2o8bobo21b2o3b2o4b2o7bo3bo$4722bo9bo23b5o5b2o$4732bo
24b3o7bobo4b2o3b2o$4758bo9bo3$4715bo49b2o3b2o$4713b2o16b2o32b2o3b2o6b
3o$4714b2o15b2o42b2o$4767b3o5b2o$4759bo7b3o4b2o$4760b2o6bo6bobo$4759b
2o15b2o$4763b2o$4706bobo54b2o$4706b2o68b2o3b2o$4707bo68b2o3b2o$4753b2o
3b2o10bo$4755b3o10b2o8b3o$4754bo3bo10b2o7b3o$4755bobo21bo$4700bo55bo$
4698b2o$4699b2o2$4755b2o$4755b2o21b2o$4698b2o78b2o$4697b2o$4691bobo5bo
$4691b2o$4692bo35bo$4728b3o$4731bo$4706bo23b2o$4705b2o24b3o$4705bobo
24b2o$4732bobo2$4729bo$4727b3o16bobo$4726bo19b2o$4726b2o19bo$4740b2o$
4739b2o$4741bo4$4721bo$4720b2o26bo$4601b2o67bo28b2o19bobo24b2o$4600bob
o65b2o27bo2bo46bobo$4586bo12b3o4b2o61b2o71b2o$4586b4o8b3o4bo2b4o84bo
18bo24bo2bo$4580b2o5b4o8b3o4b2ob3o103bo$4579bo2bo4bo2bo9bobo94b2o13b2o
25bo$4579bo2bo4b4o10b2o11bo84bo28b2o$4582bo3b4o8bo13b4o111b2o11b2o13b
2o$4582bo3bo12bo6b2o3bobob2o14b2o19bo76bo12bo11b2o$4580bobo14b3o6b2o2b
o2bob3o11bo2bo19b3o41b2o3b2o53bo$4580bobo28bobob2o11bo7b5o14bo40b2o3b
2o$4581bo30b4o12bo6bo5bo12b2o41b5o3bo33b2o3b2o$4614bo13bo7b2o3bo56bobo
4b2o32b2o3b2o$4629bo2bo7bo63bobo29bo3b5o$4578b2o3b2o46b2o24bo40b3o34b
2o4bobo19bo$4578bo5bo21bo49b3o76bobo24b2o$4604bobo48bo3bo81b3o18bobo$
4579bo3bo21b2o47bob3obo$4580b3o72b5o$4701bo$4700bobo$4635b2o10b2o50bo
3bo36bo$4613bo3b3o15bobo9b2o51b3o36bobo28b2o$4614bo4bo16b3o59b2o3b2o
33bo3bo26b2o$4612b3o3bo18b2o33bo66b3o29bo$4581b2o54b2o31bobo64b2o3b2o$
4581b2o52bobo33b2o$4636bo155b2o$4792b2o$4610b2o44b2o120bo$4609bobo21b
2o3b2o16b2o119b2o$4611bo21b2o3b2o137bobo2$4635b3o8b5o$4635b3o7bob3obo
49b2o$4636bo9bo3bo50b2o$4647b3o89b2o$4591b2o9b3o11b2o30bo90b2o44b2o$
4583bo7bo2bo9bo11bo167b2o$4582bo3b2o7bo7bo5bo4bobo27bo141bo4b5o$4582bo
5bo6bo12b4ob3o27b2o145bob3obo$4583b5o7bo11b2obob2o28b2o4b2o141bo3bo$
4591bo2bo11b3obo2bo27b3o4b2o142b3o$4591b2o14b2obobo5b6o6b3o9b2o4b2o
143bo$4608b4o5bo6bo18b2o146b2o$4609bo6bo8bo18bo145bobo$4617bo6bo69bo
95bobo$4618b6o71bo95bo$4693b3o2$4788b2obob2o$4788bo5bo$4789bo3bo$4790b
3o2$4712bo$4710b3o$4709bo$4709b2o3$4790b2o$4707bo82b2o$4705b2ob2o2$
4704bo5bo2$4704b2obob2o$4646b2o$4646b2o$4694bo$4692b2o$4693b2o2$4704b
2o$4705bo$4702b3o$4702bo16$4670bobo$4670b2o$4671bo4$4704b2o$4704bo$
4693b2o7bobo$4693bo2bo5b2o$4688b2o7bo$4690bo6bo$4697bo$4685b2o6bo2bo$
4684bobo6b2o$4684bo$4683b2o6$4649bo$4647b2o$4648b2o14$4607bo$4604b4o4b
o$4595bo7b4o5bo$4594bobo6bo2bo9b2o$4593bo3b2o4b4o9b2o$4582b2o9bo3b2o5b
4o$4582b2o9bo3b2o8bo102b2o$4594bobo28bobo82b2o8bo$4595bo29b2o80b2o6bo
5bo$4604bobo19bo72b2o5b3o5bo3b2obo$4605b2o78b2o12b2o6b2o6b6o$4605bo78b
obo23b2o4b4o$4683b3o24b2o$4683b2o$4683b2o32b2obob2o$4684bobo$4685bo31b
o5bo2$4718b2ob2o$4682b2o3b2o31bo$4682b2o3b2o2$4684b3o$4684b3o$4609b2o
74bo$4610bo106bo$4607b3o105b2o4b3o$4607bo108b2o2bo3bo2$4719bo5bo$4687b
o31b2o3b2o$4688b2o$4687b2o$4708bobo11bo$4682b3o23b2o6b2o3bobo$4681bo3b
o23bo6b2o3bobo$4680bo5bo36bo$4538b3o139bo5bo36bo$4540bo142bo10bobo19bo
3bo2bo$4539bo141bo3bo9b2o18b3o3b2o$4682bo12bo18bo3bo$4683bo2bo15bo13bo
$4686bo26bo5bo$4685bo13b2o12bo5bo$4680bo5b3o25bo3bo$4679b3o6bo26b3o$
4678b2ob2o$4677b3ob3o$4677b3ob3o$4677b3ob3o$4677b3ob3o$4678b2ob2o$
4679b3o$4680bo2$4714bo$4713b3o$4713b3o2$4711b2o3b2o$4711b2o3b2o$4694b
2o$4693b3o$4690bob2o9b2o9bo$4690bo2bo4bo5bo8bobo$4690bob2o5bo15b2o$
4693b3o3bo3bo11b2o$4694b2o5bo12b3o$4713bobo$4682b3o28b2o$4681bo3bo$
4680bo5bo$4680b2obob2o$4691bo$4669b2o19bobo$4669bo13bo4b2o3bo9b2o$
4670b3o9bobo3b2o3bo9b2o$4672bo9bobo3b2o3bo$4683bo6bobo$4691bo4473$23b
3o$25bo$24bo$12bo23bo$11b2o22b2o$2o8b2o4b2o5bo11bobo$2o7b3o4b2o3bobo$
10b2o4b2o2bobo$11b2o6bo2bo$12bo7bobo$21bobo8b2o$23bo8bobo8b2o$34bo7b2o
$34b2o8bo5$51bo$50b2o$50bobo6$58b2o$57b2o$59bo5$66bo$65b2o$65bobo6$73b
2o$72b2o$74bo5$81bo$80b2o$80bobo6$88b2o$87b2o$89bo5$96bo$95b2o$95bobo
6$103b2o$102b2o$104bo4$126b2o$111bo14b2o$110b2o$110bobo6$118b2o7bo$
117b2o7b3o$119bo5b5o$124b2o3b2o3$124b2o$123bo$126bo$123bo2bo$123b2ob2o
$125b2o3$122b2o3b2o$122b2o3b2o$123b5o$124bobo2$124b3o6$124b2o$124b2o!
The core of this pattern is just the following p90 glider gun that outputs two gliders and omits one every 90 generations:
Code: Select all
x = 50, y = 40, rule = B3/S23
24b2o$23b2o$3b2o20bo$3b2o$46b2o$17bo28b2o$17b2o$b2o13bobo13bo$31b2o$
31bobo10b2o3$2o3b2o$b5o3b2o$b2ob2o4b2o31b2o3b2o$b2ob2o3bo29b2o3b5o$2b
3o33b2o4b2ob2o$40bo3b2ob2o$45b3o3$4b3o$4b3o$3bo3bo35b3o$2bo5bo34b3o$3b
o3bo34bo3bo$4b3o34bo5bo$42bo3bo$43b3o8$5b2o$5b2o$43b2o$43b2o!
This is the kind of thing that could have been built (and built better) at least 30 years ago, but at that time, there was no proof of rule 110 universality.
I am curious if a much smaller rule 110 transducer can be found. For example, a "natural" counter that counter 0, 1, 2, 2, 2, 2, 2 .... each time it is hit with a glider and has a simple reset would work.
A more general question: What is the smallest stationary pattern that implements some Turing-equivalent transducer on a glider stream. I bet there is something much smaller, maybe even using stable components.