Pseudorandom number generator

[137ben]

I am interested in a life pattern with a pseudorandom number generating algorithm. It seems like it should be possible to program such an algorithm into a universal constructor. That may not even be the only way.
In the pattern

Code: Select all

x = 38, y = 53, rule = B3/S23
34b4o$33bo3bo$37bo$36bo3$34bo$35bo$35bo$34b2o$28bo4bo$27b2o3$34b4o$33b
o3bo$37bo$36bo25$11bo$10b2o5$bo8bo4bo$o5bo2bo4bo$o6b3o4bo$o2bo10bo2bo$
3o11b3o!

An expanding feed-back loop generates a recursive sequence of gliders that could function as a pseudorandom binary string. Some additional components would be needed to duplicate the glider stream, and another mechanism would be necessary to generate non-binary values. Unfortunately, in this case, the glider duplicator would have to travel with the stream, which would require a knight-ship. On top of that, it would have to accept gliders at generations which are multiples of 50, and no period 50 knight-ship is currently known. Also, the fact that this pattern exhibits infinite growth would make it difficult to use.

While this particular pattern is not very useful, it does suggest that pseudorandom number generators are possible in life. Of course, life is probably not the easiest rule to use, and I would expect it would be possible to define a rule in which a pseudorandom number generator would be trivial (though it may have a very large number of states).

[PM 2Ring]

RANDGUN.LIF
Pseudorandom number generator with p46 logic
A glider stream is emitted representing a pseudorandom binary
sequence satisfying the recursion a[n] = a[n-1] XOR a[n-12].
(By spreading out the pattern, the 12 can be changed.) The
sequence has period 3255, so the gun has period 46*3255 = 149730.
Built by Bill Gosper, October 1989 or earlier
(Header by Dean Hickerson, 4/11/93)

Code: Select all

x = 100, y = 133, rule = B3/S23
28bo$27b2o$13b2o11b3obo9b2o$13b2o10b2o13b2o$26b2o$27bo2$27bo10bo$26b2o
8b2obo$25b2o8b2ob3o$26b3obo5bo2bo$27b2o8b2o$28bo6$2b2o$2b2o9$52bo$51b
2o$50b2o4bo$51b2o4b2o$2b2o5b2o$bo2bo3bo2bo$4b2ob2o$3bobobobo41b2o4b2o$
3bobobobo9b2o20b2o7b2o4bo11b2o$bo9bo7b2o20b2o8b2o15b2o$o11bo39bo2$4b2o
b2o$2bo2bobo2bo$2b2ob3obob2o$4b5ob4o$5bob2ob2obo$4b2o7b2o$4b2o7b2o$4b
3o5b3o$6b3ob3o$8bobo$5bo2bobo2bo$4bo2bo3bo2bo$5b2o5b2o4b3o5b3o$17b2ob
2o3b2ob2o$17b2obobobobob2o$18bo3bobo3bo$18bo2bo3bo2bo$19b3o3b3o3$98b2o
$98b2o$98b2o$19b2o70b3o3b3o$19b2o70bobo3bobo$5b2o84bo2bobo2bo$5b2o86b
2ob2o3$21b2o$21b2o$91b2o5b2o$91b2obobob2o$91bo2bobo2bo$91b3o3b3o10$20b
3o5b3o$20b3o5b3o$21b2o5b2o$23bo3bo70b2o$21bo2bobo2bo68b2o$20bo3bobo3bo
$21bo2bobo2bo$21b3o3b3o5$21b2o$21b2o22$18b2o$17bobo$16b2obo$17b2o26b2o
$18bo25b2ob2o$45bo2bo$18bo26bo2bo$17b2o27b2o$8b2o6b2obo$8b2o7bobo26b2o
$18b2o25bo2bo$45bo2bo6b2o$44b2ob2o6b2o$45b2o!

RANDGUN2.LIF
Pseudorandom number generator with p120 logic
A glider stream is emitted representing a pseudorandom binary
sequence satisfying the recursion a[n] = a[n-1] XOR a[n-11].
(By spreading out the pattern, the 11 can be changed.) The
sequence has period 1533, so the gun has period 120*1533 = 183960.
Dean Hickerson, dean@ucdmath.ucdavis.edu 3/21/92

Code: Select all

x = 188, y = 186, rule = B3/S23
37b2o$37bo2bo$32b2o7bo9bobo$2o23bo5bo2bo6bo7bo3bo$bo23bobo4b2o7bo7bo$b
obo4b2o18b2o7bo2bo7bo14bo$2b2o6bo17b2o7b2o10bo12b2o$11bo16b2o19bo3bo$
11bo8bo4bobo23bobo$11bo9bo3bo$10bo8b3o$8b2o7$42b2obo$42bob2o3$47b2o$
48bo3$47b3o$48b2o$45b2o$45b3o$46bobo$47b2o3$6b2o$6bo4$6bo$5b3o$4bo3bo
14bo$3bob3obo13b3o$4b5o17bo$25b2o4$9b3o$11bo$10bo14bo5bo$25b2o3b2o2$
21b3o3b3o$21bo5b3o$22bo5bo2$7b3o$6bo3bo$5bo5bo$5b2obob2o$25b3o$25b3o$
24bo3bo2$23b2o3b2o3$9bo$8b2o6$26bo$26b2o69$181b2o$181bo6$182bo$181b3o$
181b3o2$179b2o3b2o$179bo5bo4$183bo$182bo$182b3o4$181bo5bo$181bo5bo$
175bo6bo3bo$175bobo5b3o$175b2o6$175b2o$173bo3bo$164bo7bo5bo$164bobo4b
2obo3bo$153bo13b2o3bo5bo$153b2o12b2o4bo3bo$167b2o6b2o$164bobo$164bo!

RANDLWSS.LIF
Pseudorandom LWSS generator with p46 logic
A lightweight spaceship stream is emitted representing a
pseudorandom binary sequence satisfying the recursion
a[n] = a[n-1] XOR a[n-19]. (By spreading out the pattern,
the 19 can be changed.) The sequence has period 413385,
so the gun has period 46*413385 = 19015710.
Built by Bill Gosper, October 1989 or earlier
(Header by Dean Hickerson, 4/11/93)

Code: Select all

x = 167, y = 139, rule = B3/S23
77b2o7b2o$77b2o6bo2b2o$76bo2bo4b6o$77b2obo5b4o$77b2obo2$77b2obo$77b2ob
o5b4o$74b2ob3o4b6o11b2o$74bobobo6bo2b2o11b2o$75b4o7b2o$76b2o40$22b2o$
22b2o5$157b2o$157b2o5$23b2o3b2o5$21b2obo3bob2o$21bo2bo3bo2bo$22b3o3b3o
126b2o5b2o$156bobo5bobo$156bo2bo3bo2bo$157b2o5b2o5$22b2o$22b2o5$157b2o
$157b2o9$2b2o$2b2o6$2b3o3b3o$bo2bo3bo2bo$bo3bobo3bo$2obobobobob2o$2ob
2o3b2ob2o69b2o$b3o5b3o69bo2b2o$49b2o30bo3bo$48bo2bo30bo2bo$48bo2bo30b
3o$49b3o$82b3o$9bo72bo2bo$8bobo58b2o10bo3bo10b2o$7bo3bo37b3o17b2o10bo
2b2o10b2o$7b5o24b2o10bo2bo11b2o17b2o$6bobobobo23b2o10bo2bo11b2o$7bo3bo
37b2o2$7bo3bo$6bobobobo$2b2o3b5o76b2o$2b2o3bo3bo75bobo$8bobo75b2obo$9b
o38b3o3bo32b2o26b2o$46b5o2bobo32bo25b2ob2o$41bo3b2o3b2o3bo59bo2bo$36bo
3bo4b3o3bo2bo33bo26bo2bo$35bo8bob2o3b3o33b2o27b2o$35bo2b2o5bo32b2o6b2o
bo$36b2o5bo2b2o3b3o24b2o7bobo26b2o$37b3o3b5o3bo2bo33b2o25bo2bo$45b2o3b
2o3bo12b2o45bo2bo6b2o$37b3o3b8o2bobo12b2o44b2ob2o6b2o$36b2o5bo2bob3o3b
o60b2o$21b2o12bo2b2o5bo$21b2o12bo8b2o$36bo3bo$41bo!

[137ben]

I see a considerable amount of work has already been done in this area. This does raise a related question: is it possible to create an "expanding feedback loop" that does not move--
or, more specifically, that has one corner which does not move. This would allow the gliders in the expanding loop to be duplicated into a stream which would function as a pseudorandom number generator that is not periodical. This *might* be possible by replacing the reflectors in a psedorandom glider loop with spaceships, moving outward, that would allow the glider loop to expand indefinitely, and thus could be aperiodic.

[calcyman]

is it possible to create an "expanding feedback loop" that does not move

Yes, Helmut Postl has made a Thue-like gun (1997).

Code: Select all

x = 132, y = 146, rule = S23/B3
71bo$71b4o$$55b3o$$55boo12bobo$55boo13bo$54bobbo13boo$47boo8bo11bobbo$
47boo7b3o10booboo12bo$57boo19bo7bo$54boo22b3o5bo$53bobbo23bobo3boo$78b
obbo$57boo19boobbo$55bobbo$39boo14b3o$39boo$$68bo6b3o$67bobo3bo4bo$68b
o3boo4bo$71bo6bo$68bobobbob3o$31boo36b5o$31boo6bo28bo$38b3o56bo$37bobb
oo55b4o$37boobboo$40boo$36b5o$35boo58bobo$35bobbo57bo$36boo59boo$95bo
bbo$95booboo$58bobo$58bo$58bobbo$61bo4$57bo$56b3o$55booboo$55bo3boo32b
oo$53bobobobo33boo$52bobboboo$52boboo$53boo$65bo$64b3o$63bobboo$63boo
bboo16boo$66boo17boo$48boo12b5o$48bobo10boo$48bo12bobbo$62boo3$77boo$
77boo5$61bo$59boo$60boo$$64boo$64bobo$64bo5$48bo34bo$48b3o30b3o$51bo
28bo$32bo17boo28boo17bo$20bo11b3o20boo40b3o11bo$18b3o14bo20boo38bo14b
3o$bbo14bo16boo19bo40boo16bo14bo$bb3o12boo42boo6boo42boo12b3o$5bo7boo
46bobbo4boo7bo30bo16bo$4boo7bo63b3o25bo20boo$20bo20bobbo16bobbo11bobb
oo15b4o4bo3bobo$14boo5bo19bo3bo14bobbo4b3o5bo3bo14boobbo3boo5bo$5boo
14boo17bo4bo14bobo5boo7boobo13boobbo4boo20boo$5boo7boo4boobboo14bo4bo
15bo9boo6boo14bobbo7bo10b3o5boo$20bo3boo14bo3bo25b3o23boo5booboo9bobo$
15bo25bobo17boo6bobo3bobo26bobo10bo3bo$61boo6boo3bobbo37bobboobo$74bo
3bo38bo3bo$74bobo41boo$78boo33bo$21boo36boo10bo7bo29boobbo5bo$21bo19b
oo16bobo8boboobobbo10boo19bo3bo4bo$23bo16bobo18bo8bo5b3o10bobo16bo5b3o
$22boo16bo13bo6boo6boo20bo16boo$18boo19boo4boo6boo30boo4boo19boo$18bo
24bobbo5bobbo29bobbo24bo$19b3o21boo7bobo32boo21b3o9bobo$8b3o10bo31boo
23boo30bo12boo$7bobbo67boo43bo$11bo$7boo$bboo3boo3bo115boo$bobo8bo115b
obo$bo8bo119bo$oo6b3o119boo$8boo52boo4boo$8bo53bo6bo$11bo48bobo6bobo
50bo$7b6o47boo8boo49b3o$6b5o109bobboo$6bo3bo113bo$7b3obo110b3o$7bob3o
30bo46bo30booboo$11bo7boo21b3o42b3o21boo5boobo$6b3o8bobbo24bo6boo23b3o
6bo24bobbo3bobboo$17boo4boo19boo5bobo23bo8boo19boo4boo4boo$boo20bo16b
oo11bo22b3o11boo16bo20boo$bbo18bobo16bo8bo41bo16bobo18bo$bbobo16boo19b
o5bo40bo19boo16bobo$3boo36boo5bobboo36boo36boo$49b3o$9boo3boo24bo9bo$
8bobobbobo23boboo69boo$8bo4bo24boo3bo66b3oboo$8bobbobbo19boo3bo70bobob
oo$9b3o23boobbo3bo46bo17boobo$32boobo3bo17boo14boo15boo$32bo6bo17boo
14boo14boo16bo$25bo6bobo$26bo6boo4bobo$9boo13b3o13bo17boo12boo47boo$5b
oobboo47bo14bo47boobboo$4bobo38boo12b3o8b3o12boo38bobo$4bo23boo16bo14b
o8bo14bo16boo23bo$3boo23bo14b3o40b3o14bo23boo$29b3o11bo44bo11b3o$31bo
68bo!

It's not pseudorandom, though; the sequence, whilst being aperiodic, is very predictable.