f



A Prototype Programmable Universal Constructor for Conway's Life

Dave Greene and Paul Chapman wish to announce the joint construction of a
prototype programmable universal* constructor.

The attached example (in standard RLE format) converts an initial block to
an eater.

Here is a brief walkthrough.

The program is represented as a string of boats (1s) and blocks (0s).  Each
Emitter cycle, the Emitter in the SW fires a salvo to read a program
instruction bit and move the read head; an Emitter cycle is 850 ticks.

The Collector/Decoder in the centre converts sequences of PULL (0) and
TRIGGER (1) instructions into TRIGGERi instructions, as follows:

TRIGGER1 = INC
TRIGGER2 = DEC
TRIGGER3 = BLACKDEC
TRIGGER4 = WHITEDEC
TRIGGER5 = SHUTDOWN

A TRIGGERi instruction takes i Collector cycles to execute; a Collector
cycle is 754 ticks.

These instructions cause the Shoulder in the NE to emit salvos to manipulate
a construction arm in the far NE.  The arm consists of an Elbow (lower right
block) and a Hand (upper left block).  The Hand is where the actual
construction is done.

A single glider in the SE starts the constructor.  The constructor shuts
down cleanly when finished.  In this example, the constructor shuts down
after 122,221 generations.

The pattern is a prototype: shotgun synchronization has been achieved here
using a standard kit of sixteen 180-degree reflectors which give all
necessary spatiotemporal alignments.  A production version would use
customized, hand-tooled parts instead.

The pattern nevertheless uses only five different still lifes: block,
beehive, boat, tub and eater.  This is to facilitate the later construction
of a replicator.

A two-phase (construct/copy) replicator would of course have to read the
program bits nondestructively.

*The authors tentatively claim universality, but a lot of work still has to
be done to find recipes for eg eaters in close proximity.

x = 4235, y = 2765, rule = B3/S23
252bo$251bobo$252boo11$264boo$264boo11$276boo$276boo10$288bo$287bobo$
288boo10$300bo$299bobo$300boo11$312boo$312boo11$324boo$324boo10$336bo$
335bobo$336boo11$348boo$348boo11$360boo$360boo10$372bo$371bobo$372boo
10$384bo$383bobo$384boo10$396bo$395bobo$396boo11$408boo$408boo11$420b
oo$420boo11$432boo$432boo10$444bo$443bobo$444boo11$456boo$456boo10$
468bo$467bobo$468boo11$480boo$480boo6$oo$oo4$492boo$492boo11$504boo$
504boo10$516bo$515bobo$516boo10$528bo$527bobo$528boo10$540bo$539bobo$
540boo10$552bo$551bobo$552boo11$564boo$564boo11$576boo$576boo10$588bo$
587bobo$588boo11$600boo$600boo10$612bo$611bobo$612boo11$624boo$624boo
10$636bo$635bobo$636boo11$648boo$648boo11$660boo$660boo10$672bo$671bob
o$672boo11$684boo$684boo10$696bo$695bobo$696boo11$708boo$708boo10$720b
o$719bobo$720boo11$732boo$732boo10$744bo$743bobo$744boo11$756boo$756b
oo11$768boo$768boo10$780bo$779bobo$780boo10$792bo$791bobo$792boo11$
804boo$804boo11$816boo$816boo10$828bo$827bobo$828boo10$840bo$839bobo$
840boo10$852bo$851bobo$852boo10$864bo$863bobo$864boo10$876bo$875bobo$
876boo11$888boo$888boo11$900boo$900boo11$912boo$912boo10$924bo$923bobo
$924boo10$936bo$935bobo$936boo10$948bo$947bobo$948boo11$960boo$960boo
11$972boo$972boo11$984boo$984boo10$996bo$995bobo$996boo10$1008bo$1007b
obo$1008boo11$1020boo$1020boo11$1032boo$1032boo10$1044bo$1043bobo$
1044boo10$1056bo$1055bobo$1056boo2597bo$3653b3o$3652bo$3652boo6$3659b
oo$3659boo$1068boo$1068boo10$3569boo$1080boo2487boo72boo$1080boo2467bo
93boo$3537bo11b3o$3535b3o14bo$3519bo14bo16boo$3519b3o12boo$3522bo$
3521boo3$3522boo$1092bo2429boo17boo106boo$1091bobo2447boo106bobo$1092b
oo2557bo$3579boo70boo$3579boo3$3538boo$3538bo19boo$3539b3o15bobo$3541b
o15bo83boo$3535boo19boo83boo$1104bo2430bo$1103bobo2430b3o96bo$1104boo
2432bo94b3o$3632bo18boo$3632boo17boo$3661boo$3661bo$3659bobo$3544boo
113boo$3544bo$3525boo15bobo$3525boo15boo$1116bo2396boo$1115bobo2394bob
o$1116boo2394bo$3511boo$$3655boo$3655bobo$3657bo$3657boo3$3524boo$
1128bo2394bobo$1127bobo2393bo$1128boo2392boo116boo$3640boo$3649boo$
3649bobo$3651bo$3651boo4$3534boo$1140bo2393boo$1139bobo$1140boo$$3634b
oo$3634boo4boo$3523boo115boo$3524bo19boo$3524bobo17bo$3525boo15bobo$
3537bo4boo95boo$3536bobo96boobboo$1152bo2383bobo95bobo$1151bobo2371boo
10bo96bo12boo$1152boo2370bobo106boo11bobo$3524bo121bo$3523boo120boo$
3538boo121boo$3538bo122bo$3539b3o120b3o$3541bo122bo$3647boo$3646bobo$
3646bo538boo$3645boo60bo477boo$1164boo2539b3o$1164boo2538bo$3704boo$
3675bo34bo$3675b3o32b3o$3678bo34bo$3655boo20boo33boo$3655boo7boo56boo$
3664bo57bo$3662bobo55bobo$3662boo4boo44boo4boo$3646boo20bo44bobbo$
1176boo2469bo18bobo45boo$1176boo2469bobo16boo34boo$3648boo52boo8$3677b
oo32boo3boo$3677boo11boo20bo3bo$1188boo2500bo18b3o5b3o$1188boo2464boo
35b3o15bo9bo$3650boobboo37bo$3649bobo$3649bo23boo$3648boo23bo$3674b3o$
3676bo4$1200bo$1199bobo$1200boo9$4233boo$4233boo$1212boo$1212boo10$
1224bo$1223bobo$1224boo4$3151boo$3151boo$3131bo$3119bo11b3o$3117b3o14b
o$3101bo14bo16boo$3101b3o12boo$1236boo1866bo$1236boo1865boo3$3104boo$
3104boo17boo$3123boo$$3161boo$3161boo$$1248bo$1247bobo1870boo$1248boo
1870bo19boo$3121b3o15bobo$3123bo15bo$3117boo19boo$3117bo$3118b3o$3120b
o5$1260boo$1260boo1864boo$3126bo$3107boo15bobo$3107boo15boo$3095boo$
3094bobo$3094bo$3093boo3$1272bo2542boo$1271bobo2541boo$1272boo3$3106b
oo$3105bobo696boo$3105bo699bo$3104boo699bobo$3806boo3$3819boo$1284boo
2533bobo$1284boo2535bo$3821boo$$3116boo$3116boo3$3817boo$3817bobo$
3819bo$1296bo1808boo712boo$1295bobo1808bo19boo$1296boo1808bobo17bo$
3107boo15bobo$3119bo4boo$3118bobo680boo$3118bobo679bobo$3107boo10bo
680bo$3106bobo690boo$3106bo$3105boo$3120boo$3120bo$1308boo1811b3o$
1308boo1813bo$3809boo$3809boo$$3816bo$3816b3o$3819bo$3818boo$3798boo$
3799bo$3799bobo$1320boo2478boo$1320boo2420bo$3740b3o$3739bo74boo$3739b
oo73bobo$3724boo90bo$3725bo90boo$3725bobo$3726boo10bo$3737bobo$3737bob
o$3738bo4boo$1332boo2392boo15bobo$1332boo2391bobo17bo65boo$3725bo19boo
64bo$3724boo86b3o$3814bo$3749boo$3749bo$3747bobo$3747boo46boo$3735boo
57bobo$3735boo57bo$1344bo2448boo$1343bobo$1344boo5$3803boo$3723boo78b
oo171bo$3724bo251b3o$3724bobo83bo168bo23boo$3725boo83b3o165boo23bo$
1356bo2456bo187bobo$1355bobo2454boo145bo37boobboo$1356boo2038bo395boo
139bo9bo15b3o35boo$3394b3o396bo139b3o5b3o18bo$3393bo399bobo140bo3bo20b
oo11boo$3393boo399boo139boo3boo32boo3$3808boo$3808bobo$3810bo$3400boo
324boo15boo65boo$1368bo2031boo324boo15bobo$1367bobo2348boo25bo203boo
52boo$1368boo2349bo25boo202boo34boo16bobo$3719bobo215boo45bobo18bo$
3720boo214bobbo44bo20boo$3931boo4boo44boo4boo$3805boo123bobo55bobo$
3805bo124bo57bo$3739bo66b3o120boo56boo7boo$3737b3o68bo130boo33boo20boo
$3736bo202bo34bo$3736boo20bo181b3o32b3o$1380bo2361bo15b3o181bo34bo$
1379bobo2002boo354b3o18bo185boo$1380boo2002boo353bo20boo11boo173bo$
3739boo32boo170b3o$3945bo60boo$4006bo$4004bobo$4004boo$$3742boo37boo
21boo$3723boo17boo36bobo21boo$3723boo55bo17boo$1392bo2386boo17boo186b
oo$1391bobo2593bo$1392boo2328boo263bobo$3723bo76boo186boo$3720b3o12boo
56boo5boo$3720bo14bo16boo39boo$3736b3o14bo$3738bo11b3o20boo$3750bo22bo
$3774b3o$3382boo392bo$3382boo$1404bo$1403bobo1970bo$1404boo1968b3o$
3373bo615boo15boo$3373boo614boo15bobo$3393boo613bo$3393bo614boo$3391bo
bo$3391boo3$3377boo$1416bo1959bobo$1415bobo1958bo604boo$1416boo1957boo
605bo$3969boo11bobo$3970bo12boo$3970bobo$3971boobboo$3975boo$$3380boo$
3381bo$3378b3o595boo$1428bo1949bo591boo4boo$1427bobo2540boo$1428boo4$
2813boo556boo$2813boo557bo598boo$2793bo578bobo15boo578bobo$2781bo11b3o
577boo15boo578bo$2779b3o14bo1172boo$2763bo14bo16boo$1440bo1322b3o12boo
$1439bobo1324bo$1440boo1323boo3$2766boo$2766boo17boo$2785boo$$2823boo
566boo$2823boo566bobo$3393bo$1452bo1940boo$1451bobo1328boo$1452boo
1328bo19boo$2783b3o15bobo$2785bo15bo$2779boo19boo573boo$2779bo594bobo$
2780b3o591bo$2782bo590boo60bo$3433b3o$3432bo$3432boo$1464bo1938bo34bo$
1463bobo1937b3o32b3o$1464boo1322boo616bo34bo$2788bo594boo20boo33boo$
2769boo15bobo594boo7boo56boo$2769boo15boo604bo57bo$2757boo631bobo55bob
o$2756bobo631boo4boo44boo4boo$2756bo617boo20bo44bobbo$2755boo618bo18bo
bo45boo$3375bobo16boo34boo$3376boo52boo$1476bo$1475bobo$1476boo$$2203b
o$2202bobo563boo$2202boo563bobo$2767bo637boo32boo3boo$2766boo637boo11b
oo20bo3bo$3418bo18b3o5b3o$3382boo35b3o15bo9bo$3378boobboo37bo$1488bo
1888bobo$1487bobo1887bo23boo$1488boo1886boo23bo$3402b3o$3404bo$2778boo
$2778boo6$2767boo$1500boo1266bo19boo$1500boo1266bobo17bo$2769boo15bobo
$2781bo4boo$2780bobo$2780bobo$2769boo10bo$2768bobo$2768bo$2767boo$
2782boo$2782bo$1512boo1269b3o$1512boo1271bo793bo$3579b3o$3582bo23boo$
3581boo23bo$3604bobo$3562bo37boobboo$3536bo9bo15b3o35boo$3536b3o5b3o
18bo$3539bo3bo20boo11boo$3538boo3boo32boo$$1524boo$1524boo5$3552boo52b
oo$3552boo34boo16bobo$3540boo45bobo18bo$3539bobbo44bo20boo$3534boo4boo
44boo4boo$1536bo1996bobo55bobo$1535bobo1995bo57bo$1536boo1994boo56boo
7boo$3542boo33boo20boo$3542bo34bo$3543b3o32b3o$3545bo34bo$3550boo$
3551bo$3548b3o$3548bo60boo$3609bo$2177bo1429bobo$1548boo615bo11b3o
1427boo$1548boo613b3o14bo23boo1385bo$2147bo14bo16boo23bo1386b3o$2147b
3o12boo38bobo1389bo$2150bo47boobboo1389boo$2149boo47boo1409boo$3609bo$
3531boo74bobo11boo$2150boo1379boo74boo12bo$2150boo17boo1448bobo97bo$
2169boo1444boobboo96b3o$3615boo99bo$1560boo2154boo$1560boo1958boo127b
oo53bo$3521bo127boo53b3o$3521bobo90boo91bo$2166boo36boo1316boo90boo4b
oo84boo$2166bo19boo16bobo1413boo25boo$2167b3o15bobo18bo1440boo110boo$
2169bo15bo20boo1327boo97boo84boo11bo25bo$2163boo19boo4boo1343bobo97bo
57boo25boo11b3o21bobo$2163bo25bobo1345bo97bobo56bo41bo20boo$2164b3o22b
o1347boo97boo56bobo38boo39boo$2166bo21boo7boo1433boo61boo79boo5boo$
1572boo623boo1433boo149boo$1572boo2052boo$3626bo$2147boo1475bobo135boo
17boo$2146bobo23bo1360boo89boo137bo17boo$2146bo23b3o1360bobo189boo36bo
bo21boo$2145boo22bo63bo1301bo161boo26boo37boo21boo$2153boo14boo36boo
22b3o1301boo108boo50boo$2153boo52bo22bo1414boo29boo$2205bobo22boo1444b
oo$2205boo11bo$2218b3o$1584boo635bo1295boo146bo56boo32boo$1584boo634b
oo1294bobo145bobo55bo20boo11boo$3516bo147boo54bobo21bo$3515boo156boo
45boo19b3o44bo$2234boo11bo1358boo15boo48bo67bo44b3o$2207boo25boo11b3o
1355bobo15boo46bobo111bo$2208bo41bo23boo1329bo65boo87boo23boo$2208bobo
38boo23bo1329boo32boo121bo$2152boo55boo61bobo1363boo118b3o$2151bobo
114boobboo1484bo$2151bo116boo1255boo87bo$1596bo553boo1373boo87b3o$
1595bobo2019bo$1596boo587boo1345bo83boo$2185boo52boo1291b3o$2211boo26b
oo1294bo$2211boo1321boo218bo$3514boo238b3o35boo$2143boo45boo1323bo241b
o34boo$2144bo45boo1323bobo229boo7boo$2144bobo15boo22boo1328boo230bo$
2145boo15boo22boo48boo36boo1182bo289bobo$2236bo19boo16bobo1179b3o290b
oo36boo$2237bo17bobo18bo1178bo74boo116bo138boo$1608boo582boo42boo17bo
20boo1177boo73bobo76boo35b3o142boo$1608boo582boo60boo4boo1178boo90bo
76boo34bo145boo$2259bobo1179bo90boo111boo42boo$2259bo1181bobo245bo$
2258boo7boo1173boo10bo232bobo95boo$2267boo1184bobo158boo67boobboo56bo
23boo14boo$3453bobo158boo67boo59bobo22bo$3454bo4boo149boo133bo14boo8b
3o$3442boo15bobo148boo148bo11bo$2163boo1276bobo17bo65boo232b3o$2163bob
o1275bo19boo64bo126boo107bo$2165bo1274boo86b3o85boo36boo$1620boo543boo
110boo1251bo85boo13boo114boo$1620boo655bo1187boo163bobo113bobo$2275bob
o1187bo164bo115bo16boo$2275boo1186bobo163boo10boo102boo17bo$3086boo
375boo46boo129bo118b3o$3086boo363boo57bobo126b3o9boo36boo70bo$3107bo
343boo57bo128bo11bo19boo16bobo$2172boo931b3o11bo389boo138bobo18bobo18b
o62boo$2172bo84boo50boo793bo14b3o527boo19bo20boo61boo$2153boo15bobo85b
o49bobbo792boo16bo14bo531boo4boo$2153boo15boo86bobo48boo810boo12b3o
536bobo$2259boo873bo539bo$1632boo1500boo537boo7boo$1632boo2048boo$
3519boo$3133boo304boo78boo223boo$3114boo17boo305bo304bo$3114boo324bobo
83bo218bobo$3441boo83b3o217boo$3076boo451bo$3076boo450boo162boo$3508b
oo182bo$2152boo1355bo180bobo$2151bobo106boo855boo390bobo178boo52boo$
1644boo505bo108boo14boo819boo19bo391boo233bo$1644boo504boo100boo22bo
820bobo15b3o614boo11bobo$2253bo23b3o65boo752bo15bo617bo12boo$2253bobo
23bo66bo752boo19boo402boo207bobo$2254boo90bobo772bo402bobo145boo60boo
bboo$2347boo16bo752b3o405bo146bo64boo$2168boo193b3o752bo323boo15boo65b
oo145bobo$2168bobo191bo1079boo15bobo212boo$2170bo191boo1070boo25bo$
2109bo60boo100boo1161bo25boo276boo$2109b3o160bo1162bobo295boo4boo$
1656bo455bo157bobo1163boo295boo$1655bobo453boo157boo40boo797boo$1656b
oo448bo34bo161boo7boo798bo408boo$2031bo72b3o32b3o162bo807bobo15boo389b
o$2030bobo70bo34bo165bobo806boo15boo323bo66b3o$2031boo70boo33boo20boo
137boo4boo1146b3o68bo$2093boo56boo7boo117boo19bo20boo1129bo281boo$
2094bo57bo121boo3bobo18bobo18bo22boo1106boo20bo258bobo$2094bobo55bobo
119bo6bo19boo16bobo22boo1112bo15b3o198boo15boo39bo$2095boo4boo44boo4b
oo117bobo6boo36boo1135b3o18bo197boo15bobo37boo$2100bobbo44bo20boo101b
oo1181bo20boo11boo176boo25bo$2101boo45bobo18bo1285boo32boo177bo25boo$
2113boo34boo16bobo1498bobo$1668boo443boo52boo28boo60boo1408boo$1668boo
528bo59bobo71boo$2198bobo57bo25boo46boo$2199boo56boo25boo68boo775boo$
2354bo776bobo324boo37boo21boo166bo$2355b3o775bo305boo17boo36bobo21boo
164b3o$2357bo775boo304boo55bo17boo169bo$2262boo49boo1180boo17boo169boo
$2099boo3boo32boo123bo49boobboo$2100bo3bo20boo11boo58boo60b3o14boo38bo
bo1118boo$2097b3o5b3o18bo71boo4boo54bo16bo16boo23bo1119bo76boo$2097bo
9bo15b3o35boo41boo65bo6b3o14bo23boo1115b3o12boo56boo5boo$1680boo388bo
12bo39bo37boobboo103bobo7bo11b3o44boo6boo1087bo14bo16boo39boo$1680boo
388b3o8b3o81bobo103bo20bo47bo6bo1104b3o14bo$2073bo6bo86bo169b3o8b3o
1103bo11b3o20boo199boo$2072boo6boo85boo34boo132bo12bo770boo343bo22bo
200bo$2199boobboo916boo367b3o195bobo$2198bobo908boo381bo195boo$2198bo
12boo895bobo$2197boo11bobo895bo$2210bo896boo565boo$2090bo118boo1462bob
o$2088b3o1041boo539bo$2087bo1023boo19bo539boo$1692boo393boo1023bo17bob
o559boo$1692boo371boo1045bobo15boo561bo$2065boo144boo900boo4bo570b3o$
2210bobo905bobo569bo$2210bo907bobo$2209boo908bo10boo551boo$3130bobo
550boo$3132bo$2077boo1053boo$2077boo1038boo$3118bo$3115b3o$1704boo513b
oo894bo$1704boo513boo1452boo$2109bo1564bo$2108bobo115bo1447bobo$2108b
oo116b3o1446boo$2229bo$2228boo$2095boo111boo$2095bo113bo$2030boo64b3o
110bobo1461boo$2031bo48boo16bo111boo1462bo$2031bobo45bobo1579boo11bobo
$1716boo314boobboo37bo3bo1582bo12boo$1716boo318boo35b3obboo11bo9bo122b
oo1436bobo$2072bo18b3o5b3o122bobo1436boobboo$2059boo11boo20bo3bo127bo
1440boo$2059boo32boo3boo126boo3$3668boo$3662boo4boo$3662boo$$2170bo20b
o29boo$1728boo300boo52boo83bobo7bo11b3o27bo$1728boo299bobo16boo34boo
84bo6b3o14bo27b3o$2029bo18bobo45boo61bo16bo16boo29bo235boo$2028boo20bo
44bobbo60b3o14boo282bobo1200boo$2044boo4boo44boo4boo58bo281boo15bo
1200bobo$2044bobo55bobo56boo281boo91bo1124bo$2046bo57bo432b3o1121boo$
2037boo7boo56boo331boo101bo$2037boo20boo33boo341boo82bo17boo$2060bo34b
o60boo25boo324bo11b3o$2057b3o32b3o62bo25boo322b3o14bo$2057bo34bo64bobo
331bo14bo16boo$1740boo344boo70boo331b3o12boo$1740boo344bo407bo$2087b3o
107boo21boo271boo$2027boo60bo81boo23bobo21boo204bo11boo$2028bo142bobo
6boo14bo17boo209bobo10boo$2028bobo38bo103bo6bo14boo17boo209bobo14boo
50boo$2029boo37bobo102boo3bobo245bo15boo50boo17boo$2068boo108boo333boo
$2216boo$2158boo49boo5boo333boo$2048bo109bobo48boo340boo$2046b3o110bo
276boo$1752boo291bo123boo264bobbo$1752boo291boo122bobo264boo72boo$
2171bo338bo19boo$2171boo338b3o15bobo$2513bo15bo$2507boo19boo$2507bo$
2508b3o$2153boo355bo$2152bobo$2152bo$2025boo124boo$1764boo259boo232bo$
1764boo493b3o$2262bo14bo238boo$2261boo12b3o238bo$2180boo39bo52bo222boo
15bobo$2181bo25bo13b3o50boo221boo15boo$2161boo18bobo21b3o16bo260boo$
2161boo7boo10boo20bo18boo259bobo$2170bo33boo67boo209bo$2040boo126bobo
83boo17boo208boo$2040boo126boo4boo78boo121bo9bo$2152boo20bo202b3o5b3o
27bo$1776boo375bo18bobo192boo11bo3bo30b3o$1776boo375bobo16boo192bobo
10boo3boo32bo14bo$2154boo210bo50boo12b3o$2214boo149boo63bo885bo$2214b
oo41boo171boo884b3o$2237boo19bo237boo821bo23boo$2237bobo15b3o237bobo
820boo23bo$2239bo15bo173boo64bo845bobo$2227boo10boo19boo148boo17boo63b
oo803bo37boobboo$2227bo33bo100boo46boo861bo9bo15b3o35boo$2183boo32boo
9b3o27b3o71boo28boo909b3o5b3o18bo$2183boo11boo20bo11bo27bo74bo942bo3bo
20boo11boo224boo$1788boo406bo21bobo109b3o942boo3boo32boo224boo5boo$
1788boo370boo35b3o19boo109bo1216boo$2156boobboo37bo$2155bobo255boo$
2155bo23boo212boo19bo1101boo8boo17boo$2154boo23bo71boo120bo6boo11bobo
15b3o92boo1008boo9bo17boo$2180b3o69bo118b3o6boo13bo15bo94boo1019bobo
21boo$2182bo69bobo15boo98bo24boo19boo1110boo21boo$2253boo15boo98boo45b
o871boo52boo165boo$2414b3o872boo34boo16bobo164boo$2414bo862boo45bobo
18bo168boo$3276bobbo44bo20boo167boo$1800boo693boo107bo666boo4boo44boo
4boo$1800boo694bo19boo86b3o663bobo55bobo$2432boo62bobo17bo90bo662bo57b
o$2408bo23bobo62boo15bobo71bo17boo661boo56boo7boo171boo$2408b3o23bo74b
o4boo60bo11b3o688boo33boo20boo171boo$2411bo22boo72bobo63b3o14bo687bo
34bo$2410boo14boo80bobo47bo14bo16boo688b3o32b3o$2426boo69boo10bo48b3o
12boo707bo34bo$2013bo257boo223bobo62bo725boo265boo$2012bobo256bobo222b
o63boo726bo265bo$2013boo258bo221boo788b3o264bobo$2273boo235boo773bo60b
oo204boo$1812boo696bo50boo783bo$1812boo697b3o47boo17boo762bobo$2513bo
66boo762boo$3328bo187boo$2618boo708b3o186bo$2618boo711bo182b3o$2280boo
1048boo182bo$2280bo146boo917boo181boo$2261boo15bobo146bobo147boo767bo
182bobo$2261boo15boo149bo147bo19boo745bobo11boo171bo$2429boo147b3o15bo
bo745boo12bo172boo$2580bo15bo759bobo192boo$1824boo748boo19boo755boobb
oo177boo14boo$1824boo748bo777boo182bo22boo$2575b3o955b3o23bo$2577bo
808boo145bo23bobo$3386boo169boo$3351boo168boo$3351boo4boo162boo$2417b
oo938boo25boo$2417boo965boo129bo$2260boo321boo786boo140b3o23boo$2259bo
bo321bo788bo139bo17boo8bo$2259bo166boo136boo15bobo788bobo72boo48boo13b
oo16bo9bobo$1836boo420boo166boo136boo15boo790boo46bo25bo23bo25bo30bobo
10boo$1836boo714boo815boo50b3o21bobo23b3o21bobo30boo$2551bobo815boo53b
o20boo27bo20boo$2551bo811boo58boo48boo38bo$2550boo811bo149b3o$2276boo
147boo17bo9bo906bobo90bo49bo11bo$2276bobo146bo18b3o5b3o27bo878boo91b3o
47b3o8boo14bo$2278bo142boo3b3o5boo11bo3bo30b3o972bo49bo22bobo$2217bo
60boo141bobo4bo4bobo10boo3boo32bo14bo955boo11boo35boo23bo$2217b3o203bo
9bo50boo12b3o881boo85boo$2220bo171boo29boo7boo63bo884boo29boo$2219boo
170bobo103boo914boo$1848boo364bo34bo141bo4boo165boo977boo$1848boo362b
3o32b3o140boo5bo164bobo977boo14boo$2211bo34bo147b3o99boo64bo839bo131b
oo22bo$2211boo33boo20boo124bo82boo17boo63boo838bobo122boo7bo23b3o$
2060bo140boo56boo7boo159boo46boo922boo123bobo6bobo23bo$2059bobo140bo
57bo138boo28boo979boo32boo48boo32bo7boo$2059bobo140bobo55bobo137bo887b
oo53boo15boo48bo20boo11boo35boo11boo23boo7boo$2060bo142boo4boo44boo4b
oo134b3o888boo52bobo15boo46bobo21bo49bo36bo$2208bobbo44bo20boo118bo
944bo65boo19b3o47b3o38b3o$2209boo45bobo18bo1063boo32boo52bo49bo42bo$
2221boo34boo16bobo202boo893boo157boo$2054boo165boo52boo183boo19bo966b
oo48boo35bo$2054boo384bo6boo11bobo15b3o92boo702boo72bo97bo20boo27bo22b
oo11bobo$2438b3o6boo13bo15bo94boo703bo72b3o92b3o21bobo23b3o24bo12boo$
2437bo24boo19boo793bobo73bo91bo25bo23bo26bobo$2437boo45bo794boo72boo
117boo50boobboo$2481b3o1044boo$2481bo$3292boo$2207boo3boo32boo314boo
728bobo$2208bo3bo20boo11boo315bo19boo90boo617bo234boo$2199boo4b3o5b3o
18bo264boo62bobo17bo91boo617boo227boo4boo$2199bobo3bo9bo15b3o35boo204b
o23bobo62boo15bobo71bo867boo$2200bo30bo37boobboo200b3o23bo74bo4boo60bo
11b3o$2273bobo202bo22boo72bobo63b3o14bo$2250boo23bo201boo14boo80bobo
47bo14bo16boo726bo$2251bo23boo216boo69boo10bo48b3o12boo704boo35b3o$
2248b3o312bobo62bo661boo54boo34bo$2248bo314bo63boo661bobo89boo42boo96b
oo$2562boo728bo133bo96bobo$2577boo713boo130bobo96bo$2577bo50boo721boo
67boobboo96boo$2578b3o47boo17boo702boo67boo$2580bo66boo698boo$3347boo$
2685boo587boo$2685boo586bobo115boo$3273bo79boo36boo$2494boo776boo79boo
13boo$2494bobo147boo721bobo$2496bo147bo19boo701bo$2496boo147b3o15bobo
700boo10boo$2647bo15bo715bo$2641boo19boo712b3o9boo36boo$2641bo734bo11b
o19boo16bobo$2642b3o637boo102bobo18bobo18bo$2644bo637boo102boo19bo20b
oo$3406boo4boo$3289bo121bobo$3289b3o119bo$2484boo806bo117boo7boo$2484b
oo805boo126boo$2650boo619boo$2650bo621bo$2493boo136boo15bobo621bobo$
2493boo136boo15boo623boo$2619boo594bo$2618bobo592b3o$2618bo593bo74boo
140boo$2617boo593boo73bobo139bo$2492boo17bo9bo675boo90bo137bobo$2492bo
18b3o5b3o27bo648bo90boo136boo$2488boo3b3o5boo11bo3bo30b3o646bobo$2488b
obo4bo4bobo10boo3boo32bo14bo631boo10bo$2490bo9bo50boo12b3o642bobo$
2459boo29boo7boo63bo645bobo$2458bobo103boo645bo4boo191boo$2458bo4boo
165boo567boo15bobo191bo$2457boo5bo164bobo566bobo17bo65boo124bobo$2461b
3o99boo64bo568bo19boo64bo126boo$2461bo82boo17boo63boo567boo86b3o$2496b
oo46boo741bo$2466boo28boo724boo$2467bo754bo$2464b3o753bobo$2464bo755b
oo46boo$3208boo57bobo$2547boo659boo57bo$2527boo19bo717boo$2507bo6boo
11bobo15b3o92boo$2505b3o6boo13bo15bo94boo$2504bo24boo19boo860boo15boo$
2504boo45bo860boo15bobo$2548b3o853boo25bo$2548bo856bo25boo$3276boo127b
obo$2629boo107bo457boo78boo128boo$2630bo19boo86b3o456bo$2566boo62bobo
17bo90bo455bobo83bo$2542bo23bobo62boo15bobo71bo17boo456boo83b3o$2542b
3o23bo74bo4boo60bo11b3o561bo138bo$2545bo22boo72bobo63b3o14bo559boo136b
3o$2544boo14boo80bobo47bo14bo16boo539boo155bo$2560boo69boo10bo48b3o12b
oo557bo155boo$2630bobo62bo570bobo$2630bo63boo571boo$2629boo$2644boo$
2644bo50boo584boo$2645b3o47boo17boo565bobo$2647bo66boo567bo143boo$
3199boo15boo65boo142bo$2752boo445boo15bobo206bobo$2752boo99boo336boo
25bo206boo$2839boo12boo337bo25boo$2561boo277bo351bobo$2561bobo147boo
127bobo350boo216boo$2563bo147bo19boo93boo13boo567bobo$2563boo147b3o15b
obo93boo450boo130bo$2714bo15bo547bo130boo$2708boo19boo481bo66b3o147boo
$2708bo111boo388b3o68bo148bo$2709b3o108boo37boo348bo217b3o$2711bo112b
oo33boo348boo20bo195bo$2824boo389bo15b3o$3213b3o18bo185boo$3212bo20boo
11boo172boo$2551boo659boo32boo$2551boo266boo$2717boo100boo38bo$2717bo
140bobo$2560boo136boo15bobo141bo$2560boo136boo15boo$2686boo527boo37boo
21boo131boo$2685bobo508boo17boo36bobo21boo132bo$2685bo163boo345boo55bo
17boo138bobo$2684boo162bobo401boo17boo139boo$2559boo17bo9bo259bo$2559b
o18b3o5b3o27bo230boo346boo$2555boo3b3o5boo11bo3bo30b3o577bo76boo$2555b
obo4bo4bobo10boo3boo32bo14bo191boo365b3o12boo56boo5boo$2557bo9bo50boo
12b3o192bo365bo14bo16boo39boo142boo$2526boo29boo7boo63bo192b3o382b3o
14bo184bo$2525bobo103boo191bo386bo11b3o20boo150boo11bobo$2525bo4boo
165boo140boo382bo22bo152bo12boo$2524boo5bo164bobo140bobo405b3o149bobo$
2528b3o99boo64bo144bo407bo150boobboo$2528bo82boo17boo63boo144boo561boo
$2563boo46boo$2533boo28boo$2534bo$2531b3o871boo$2531bo867boo4boo$3399b
oo$2614boo215boo$2594boo19bo215boo$2574bo6boo11bobo15b3o92boo$2572b3o
6boo13bo15bo94boo116bo$2571bo24boo19boo204b3o$2571boo45bo203bo577boo$
2615b3o204boo575bobo$2615bo226boo555bo$2842bo555boo$2696boo142bobo$
2697bo19boo121boo$2633boo62bobo17bo$2609bo23bobo62boo15bobo$2609b3o23b
o74bo4boo109boo$2612bo22boo72bobo113bobo$2611boo14boo80bobo113bo$2627b
oo69boo10bo113boo$2697bobo$2697bo$2696boo$2199bo511boo$2199b3o509bo$
2202bo509b3o$2201boo511bo114boo$2830bo$2219bo607b3o$2217b3o607bo$2026b
o189bo88boo$2024b3o189boo87boo321boo$2023bo302bo301bobo$2023boo299b3o
11bo291bo658boo$2008boo184boo19boo106bo14b3o289boo631bo25bo$2009bo184b
oo19boo106boo16bo14bo894bo11b3o21bobo$2009bobo328boo12b3o476boo414b3o
14bo20boo$2010boo10bo330bo479boo4boo392bo14bo16boo39boo$2021bobo329boo
484boo392b3o12boo56boo5boo$2021bobo1212bo76boo$2022bo4boo1206boo$2010b
oo15bobo322boo$2009bobo17bo303boo17boo484boo452boo17boo$2009bo19boo
302boo283boo214boobboo396boo55bo17boo$2008boo608boo213bobo400boo17boo
36bobo21boo$2295boo536bo12boo407boo37boo21boo$2202boo91boo535boo11bobo
$2203bo423boo216bo$2200b3o424boo215boo$2200bo135boo522boo$2019boo295b
oo19bo522bo$2019boo295bobo15b3o524b3o388boo32boo$2318bo15bo528bo388bo
20boo11boo$2318boo19boo285boo17bo9bo190boo405b3o18bo$2340bo285bo18b3o
5b3o27bo161bobo407bo15b3o$2337b3o282boo3b3o5boo11bo3bo30b3o159bo403boo
20bo$2206boo129bo284bobo4bo4bobo10boo3boo32bo14bo142boo60bo342bo$1742b
oo462boo4boo410bo9bo50boo12b3o202b3o343b3o37boo$1743bo25bo442boo36boo
341boo29boo7boo63bo204bo348bo38bo28boo$1743bobo21b3o480bobo339bobo103b
oo203boo383b3o29bo$1744boo20bo240boo243bo339bo4boo275bo34bo378bo29bobo
$1766boo240bo243boo337boo5bo275b3o32b3o406boo$2008bobo200boo117boo263b
3o99boo178bo34bo320boo$1786bo222boo196boobboo118bo263bo82boo17boo155b
oo20boo33boo319bobo23bo$1676boo106b3o19boo398bobo122bobo15boo279boo46b
oo174boo7boo56boo309bo23b3o$1669boo5boo105bo21bobo398bo125boo15boo249b
oo28boo231bo57bo309boo22bo$1669boo99boo11boo20bo11bo387boo154boo238bo
259bobo55bobo317boo14boo$1707boo61boo32boo9b3o543bobo234b3o260boo4boo
44boo4boo318boo$1706bobo105bo548bo234bo246boo20bo44bobbo$1671boo17boo
14bo107boo10boo387boo146boo481bo18bobo45boo$1671boo17bo14boo119bo387bo
bo464boo163bobo16boo34boo$1665boo21bobo133bobo169boo216bo21boo423boo
19bo164boo52boo$1665boo21boo134boo13boo156bo215boo21bobo402bo6boo11bob
o15b3o$1801boo36boo156bobo238bo400b3o6boo13bo15bo637boo$1801boo195boo
238boo398bo24boo19boo615boo14boo$1730boo13boo263boo15boo215boo392boo
45bo616bo22boo$1702boo26boo13boo11boo85boo163boo15bobo214bo437b3o614b
3o23bo$1702boo54bo86boo182bo195boo15bobo105boo330bo616bo23bobo$1759b3o
79boo186boo194boo15boo106bobo970boo$1761bo79boo509bo523boo32boo3boo
321boo$2352boo522boo11boo20bo3bo321bobo$2700boo187bo18b3o5b3o318bo$
1769boo39boo864bo23bobo150boo35b3o15bo9bo317boo$1732boo34bobo40bo34boo
828b3o23bo146boobboo37bo412boo$1662bo29boo38bobo33bo39b3o35boo175bo
655bo22boo144bobo455bo$1662b3o27bo41bo32boo39bo212b3o654boo14boo152bo
23boo432bobo$1665bo27b3o11boo25boo284bo673boo151boo23bo434boo$1664boo
29bo11boo311boo19boo830b3o378boo$2026bo15bo832bo378bobo$2024b3o15bobo
295boo914bo$1721boo300bo19boo179boo114boo914boo$1721bo301boo198bobo$
1722b3o498bo$1724bo497boo$1659boo50boo351boo$1660bo51bo126boo223boo
1161boo$1660bobo46b3o127bo511boo848bo25bo$1661boo46bo130b3o183boo302b
oo19bo849b3o21bobo18boo$1842bo164boo17boo212boo89bo17bobo343boo507bo
20boo10boo7boo60boo$1753boo252boo231bobo88bobo15boo344bobo505boo33bo
69boo14boo$1675boo69boo5boo62boo423bo89boo4bo358bo540bobo59boo22bo$
1675bobo68boo69boo32boo328bo60boo93bobo357boo485bo48boo4boo60bo23b3o$
1677bo106boo65bo154boo173b3o153bobo823boo19b3o47bo20boo44bobo23bo$
1677boo104bobo46boo15bobo155bo176bo153bo10boo812bobo21bo46bobo18bo46b
oo$1657boo89boo17boo14bo48boo15boo153b3o12boo162boo164bobo801bo11bo20b
oo11boo34boo16bobo$1657bo90boo17bo14boo220bo14bo16boo140bo34bo137bo
801b3o9boo32boo52boo$1658b3o81boo21bobo23boo227b3o14bo138b3o32b3o137b
oo803bo$1660bo81boo21boo23bobo229bo11b3o138bo34bo125boo805boo10boo$
1791bo242bo140boo33boo20boo103bo806bo155boo$1666boo386boo109boo56boo7b
oo100b3o807bobo154bo$1666boo386boo110bo57bo109bo350boo94bo348boo13boo
141boo11bobo$1779boo385bobo55bobo458boo93bobo347boo36boo119bo12boo$
1779boo29boo355boo4boo44boo4boo553boo386boo119bobo$1810boo360bobbo44bo
20boo981boo64boobboo$2173boo45bobo18bo452boo428boo85boo11boo68boo$
2185boo34boo16bobo452boo428boo86bo$1831boo352boo52boo887boo79b3o35boo$
1676boo152bobo1295boo79bo37boobboo$1676bo153bo1420bobo41boo$1674bobo
92boo58boo1397boo23bo35boo4boo$1674boo93bo53boo868boo464boo39boo27bo
23boo34boo$1770b3o50boo868bo429boo34bo40bobo23b3o$1772bo46boo868boo3b
3o426boo35b3o39bo23bo$1819bobo867bobo4bo465bo39boo$1821bo349boo3boo32b
oo479bo$1676boo143boo349bo3bo20boo11boo448boo16boo11boo$1676bo131boo
359b3o5b3o18bo460bobo16boo610boo$1674bobo11boo118boo25boo332bo9bo15b3o
35boo424bo4boo623bobo$1674boo12bo146boo4boo352bo37boobboo378bo40boo5bo
623bo$1686bobo46boo104boo394bobo375b3o44b3o391bo231boo$1682boobboo48bo
69boo71boo333boo23bo374bo47bo25boo366b3o$1682boo52bobo67boo71bo335bo
23boo373boo53boo17bobo368bo23boo$1737boo141b3o329b3o384boo67bobo19bo
367boo23bo$1761boo77boo40bo329bo387bo67bo21boo389bobo46boo$1761boo73b
oobboo758bobo64boo370bo37boobboo48bo$1681boo152bobo763boo10bo399bo9bo
15b3o35boo49b3o$1681boo4boo146bo12boo762bobo371boo25b3o5b3o18bo85bo$
1687boo145boo11bobo762bobo371boo28bo3bo20boo11boo160boo$1847bo765bo4b
oo395boo3boo32boo96boo62boo5boo$1846boo753boo15bobo497boo32boo69boo$
1759boo101boo736bobo17bo65boo431bo65boo$1759bo102bo737bo19boo64bo432bo
bo15boo46bobo$1760b3o100b3o733boo86b3o285boo143boo15boo48bo33boo$1686b
oo74bo102bo823bo286bo210boo32boo$1686bobo159boo774boo350bobo199boo47b
oo$1688bo158bobo774bo352boo199bobo46boo$1688boo157bo774bobo404boo52boo
94bo$1846boo774boo46boo357boo34boo16bobo$2610boo57bobo318boo25boo45bob
o18bo$2610boo57bo320bobo23bobbo44bo20boo103boo$2668boo322bo18boo4boo
44boo4boo88boo29boo$2992boo16bobo55bobo88boo$3010bo57bo$1763boo1244boo
56boo7boo$1763bo92boo1161boo33boo20boo60boo$1761bobo92boo7boo1152bo34b
o83bobo$1761boo102bo1154b3o32b3o82bo$1752boo109bobo812boo308boo32bo34b
o82boo58boo$1752boo109boo4boo727boo78boo308bobo36boo117boo53bo$1847boo
20bo19boo708bo390bo37bo117boo50b3o6boo$1848bo18bobo18bobo708bobo83bo
304boo33b3o122boo46bo9bo$1848bobo16boo19bo11bo699boo83b3o337bo60boo61b
obo56bobo$1849boo36boo9b3o787bo397bo62bo59boo$1897bo789boo395bobo61boo
68boo$1769boo126boo10boo756boo415boo75boo55boo$1769bo139bo758bo303boo
160boo25boo$1767bobo137bobo758bobo300bobo154boo4boo$1767boo138boo13boo
745boo300bo118boo36boo$1884boo36boo1046boo117bobo71boo$1884boo1180boo
21bo73boo$2683boo382bo20boo111boo$1928boo753bobo381bobo59boo71bo$1928b
oo755bo382boo59boobboo67bobo$1855boo67boo675boo15boo65boo446bobo67boo$
1851boobboo67boo675boo15bobo500boo12bo$1850bobo740boo25bo359boo139bobo
11boo$1771boo77bo254boo487bo25boo358boo141bo$1771bobo75boo42boo210boo
487bobo526boo$1773bo120bo34boo664boo390bo119boo$1773boo116b3o35boo
1056b3o118bo$1744boo17boo126bo788boo308bo114b3o$1744bo18boo915bo308boo
114bo$1745b3o368boo496bo66b3o285boo150boo76boo$1747bo368bo495b3o68bo
286bo150bobo74bobo$2114bobo494bo358bobo96boo15boo35bo74bo$1753boo359b
oo495boo20bo337boo96boo15bobo34boo72boo$1753boo242bo619bo15b3o277bo
174bo118boo17boo$1995b3o617b3o18bo274b3o174boo117boo18bo$1969boo23bo
106boo511bo20boo11boo260bo74boo237b3o$1970bo23boo104bobo511boo32boo
260boo73bobo236bo$1922boo46bobo127bo794boo90bo$1922bo48boobboo37bo84b
oo795bo90boo228boo$1923b3o49boo35b3o15bo9bo855bobo214boo102boo$1763boo
160bo85bo18b3o5b3o856boo10bo172bo21boo7boo$1763bo72boo160boo11boo20bo
3bo870bobo169b3o22bo$1761bobo65boo5boo62boo96boo32boo3boo578boo37boo
21boo227bobo168bo25bobo$1761boo66boo69boo32boo662boo17boo36bobo21boo
228bo4boo163boo19boo4boo$1867boo65bo168boo493boo55bo17boo222boo15bobo
168bo15bo20boo$1866bobo46boo15bobo167bobo549boo17boo221bobo17bo65boo
99b3o15bobo18bo$1831boo17boo14bo48boo15boo168bo793bo19boo64bo99bo19boo
16bobo84boo$1831boo17bo14boo234boo494boo296boo86b3o96boo36boo86bo$
1763boo60boo21bobo23boo722bo76boo308bo222bobo$1763bo61boo21boo23bobo
719b3o12boo56boo5boo243boo287boo$1761bobo11boo97bo94boo52boo570bo14bo
16boo39boo250bo$1761boo12bo192bobo16boo34boo586b3o14bo289bobo$1773bobo
192bo18bobo45boo82boo492bo11b3o20boo268boo46boo$1769boobboo87boo103boo
20bo44bobbo81bobo503bo22bo257boo57bobo117boo$1769boo91boo29boo88boo4b
oo44boo4boo78bo527b3o254boo57bo100boo17boo120boo$1893boo88bobo55bobo
77boo528bo312boo100boo140bo$1985bo57bo1151boo11bobo$1976boo7boo56boo
1151bo12boo$1768boo144boo60boo20boo33boo1030boo47boo80bobo$1768boo4boo
137bobo83bo34bo1031bo47boobboo77boobboo$1774boo137bo82b3o32b3o1029b3o
12boo38bobo80boo$1822bo29boo58boo82bo34bo368boo661bo14bo16boo23bo$
1822b3o27bo53boo117boo84boo287boo572boo103b3o14bo23boo$1825bo27b3o50b
oo117bo85boo267bo513boo78boo105bo11b3o$1824boo29bo46boo122b3o339bo11b
3o512bo197bo108boo$1902bobo61boo60bo76bo260b3o14bo511bobo83bo214boo4b
oo$1773boo129bo62bo135b3o244bo14bo16boo512boo83b3o212boo$1773bobo128b
oo61bobo132bo247b3o12boo617bo$1775bo115boo75boo132boo249bo629boo$1775b
oo114boo25boo202boo228boo609boo$1918boo4boo196bo841bo$1819boo103boo36b
oo156bobo353bo487bobo$1820bo68boo71bobo155boo231boo119b3o488boo230boo$
1820bobo66boo73bo21boo191bo173boo17boo99bo722bobo$1821boo141boo20bo
192b3o190boo99boo17bo703bo$1923boo59bobo119boo74bo307b3o11bo474boo214b
oo$1919boobboo59boo119bobo73boo227boo77bo14b3o472bobo$1835boo81bobo
184bo90boo212boo77boo16bo14bo458bo$1835bobo80bo12boo171boo90bo309boo
12b3o374boo15boo65boo$1837bo79boo11bobo261bobo322bo377boo15bobo$1837b
oo91bo252bo10boo173boo148boo368boo25bo$1817boo110boo251bobo184bo19boo
499bo25boo$1817bo127boo235bobo185b3o15bobo499bobo$1818b3o124bo231boo4b
o188bo15bo129boo371boo$1820bo125b3o227bobo15boo170boo19boo110boo17boo$
1948bo160boo65bo17bobo169bo132boo475boo$1826boo103boo177bo64boo19bo
170b3o606bo$1826boo102bobo174b3o86boo171bo91boo178bo268bo66b3o$1930bo
35boo15boo122bo353boo177bobo265b3o68bo$1929boo34bobo15boo186boo468boo
264bo$1965bo206bo734boo20bo$1964boo206bobo327boo409bo15b3o$2125boo46b
oo307boo19bo407b3o18bo$2125bobo57boo188boo105bobo15b3o407bo20boo11boo$
2127bo57boo188bo108bo15bo409boo32boo$2127boo227boo15bobo108boo19boo$
1939boo415boo15boo131bo$1939boo7boo21bo531b3o$1948bo22b3o529bo$1946bob
o25bo$1946boo4boo19boo938boo37boo21boo$1930boo20bo15bo925boo17boo36bob
o21boo$1931bo18bobo15b3o146boo775boo55bo17boo$1839boo90bobo16boo19bo
145boo78boo751boo17boo$1839bo92boo36boo225bo298boo$1837bobo271bo83bobo
299bo395boo$1837boo270b3o83boo300bobo15boo377bo76boo$1828boo278bo389b
oo15boo374b3o12boo56boo5boo$1828boo278boo245boo170boo362bo14bo16boo39b
oo$2128boo224bobo170bobo377b3o14bo$1967boo159bo225bo174bo379bo11b3o20b
oo$1967boo17boo138bobo224boo174boo390bo22bo$1986boo138boo817b3o$2947bo
$1845boo$1845bo92boo47boo123boo$1843bobo88boobboo47bo123bobo$1843boo
88bobo38boo12b3o120bo$1933bo23boo16bo14bo119boo65boo15boo$1932boo23bo
14b3o201bobo15boo320boo$1958b3o11bo203bo25boo161boo149bobo$1960bo214b
oo25bo162boo151bo$2200bobo174boo139boo$2200boo175bobo$2379bo$2115boo
262boo$1847boo267bo$1847bobo263b3o66bo171boo$1849bo263bo68b3o170bo19b
oo$1849boo334bo169bobo17bo$1820boo17boo322bo20boo170boo15bobo$1820bo
18boo320b3o15bo188bo4boo131boo$1821b3o336bo18b3o185bobo136boo$1823bo
323boo11boo20bo184bobo$2147boo32boo173boo10bo$1829boo91boo431bobo$
1829boo92bo25bo405bo$1923bobo21b3o11bo392boo$1924boo20bo14b3o405boo
146boo$1905boo39boo16bo14bo389bo126boo19bo$1898boo5boo56boo12b3o136boo
21boo37boo190b3o124bo17bobo$1898boo76bo139boo21bobo36boo17boo173bo124b
obo15boo$1976boo144boo17bo55boo299boo4bo$1839boo281boo17boo360bobo$
1839bo60boo17boo582bobo$1837bobo60boo17bo55boo221boo304bo10boo$1837boo
55boo21bobo36boo17boo143boo76bo316bobo$1894boo21boo37boo162boo5boo56b
oo12b3o315bo$2127boo39boo16bo14bo315boo$2168bo14b3o316boo$2147boo20b3o
11bo319bo$1839boo307bo22bo328b3o$1839bo305b3o352bo$1837bobo11boo72boo
32boo184bo$1837boo12bo73boo11boo20bo$1849bobo86bo18b3o$1845boobboo88b
3o15bo$1845boo94bo20boo$1963bo$1921boo37b3o$1891boo28bo38bo$1844boo46b
o29b3o$1844boo4boo40bobo29bo$1850boo41boo$1978boo$1954bo23bobo$1954b3o
23bo$1957bo22boo$1956boo14boo$1849boo121boo$1849bobo$1851bo$1851boo3$
1894boo$1894boo14boo$1886boo22bo$1887bo23b3o$1887bobo23bo$1888boo$
1973boo$1973bobo$1975bo$1975boo$1906boo$1906bo$1904bobo$1904boo$1957b
oo$1956bobo$1956bo$1955boo5$1984boo$1985bo25bo$1965boo18bobo21b3o$
1903boo60boo7boo10boo20bo$1887boo14boo69bo33boo$1888bo22boo59bobo$
1885b3o23bo60boo4boo48bo$1885bo23bobo44boo20bo47b3o19boo$1909boo46bo
18bobo46bo21bobo$1957bobo16boo34boo11boo20bo11bo$1958boo52boo32boo9b3o
$2056bo$2056boo10boo$1911boo155bo$1911bo154bobo$1909bobo11boo141boo13b
oo$1909boo12bo119boo36boo$1921bobo119boo$1917boobboo64boo$1917boo68boo
11boo85boo452bo$2000bo86boo452b3o$1964boo35b3o79boo459bo$1960boobboo
37bo79boo458boo$1916boo41bobo$1916boo4boo35bo23boo$1922boo34boo23bo27b
oo39boo$1984b3o23bobo40bo34boo$1986bo23bo39b3o35boo$2009boo39bo485boo$
2536boo$$1921boo$1921bobo$1923bo$1923boo231bo$2154b3o$2128boo23bo$
2129bo23boo$2081boo46bobo$2081bo48boobboo37bo$2082b3o49boo35b3o15bo9bo
$2084bo85bo18b3o5b3o$1995boo160boo11boo20bo3bo355boo$1988boo5boo62boo
96boo32boo3boo354boo$1988boo69boo32boo$2026boo65bo$2025bobo46boo15bobo
$1990boo33bo48boo15boo$1990boo32boo$1984boo47boo587bo$1984boo46bobo
585b3o$2033bo94boo52boo435bo$2127bobo16boo34boo435boo17bo$2127bo18bobo
45boo350boo88b3o11bo$2021boo103boo20bo44bobbo348bobo87bo14b3o$2021boo
29boo88boo4boo44boo4boo343bo89boo16bo14bo$2052boo88bobo55bobo341boo
106boo12b3o$2144bo57bo462bo$2135boo7boo56boo461boo$2073boo60boo20boo
33boo$2072bobo83bo34bo$2072bo82b3o32b3o471boo$2011boo58boo82bo34bo454b
oo17boo$2011bo53boo117boo368boo89boo$2004boo6b3o50boo117bo369boo$2004b
o9bo46boo122b3o419boo$2002bobo56bobo61boo60bo373bo45boo$2002boo59bo62b
o98boo334b3o$1993boo68boo61bobo96boo317boo18bo$1993boo55boo75boo415boo
17boo83boo$2050boo25boo455boo92boo19bo$2077boo4boo450bo92bobo15b3o$
2083boo36boo412bobo92bo15bo$2048boo71bobo112boo298boo92boo19boo$2048b
oo73bo21boo89bo415bo$2010boo111boo20bo88bobo412b3o$2010bo71boo59bobo
88boo413bo$2008bobo67boobboo59boo$2008boo67bobo$2077bo12boo129boo$
2076boo11bobo128bobo$2089bo130bo$2088boo129boo319boo100boo$2104boo433b
obo101bo$2104bo434bo103bobo15boo$2105b3o430boo104boo15boo$2107bo565boo
$2012boo76boo581bobo$2012bobo74bobo131boo450bo$2014bo74bo35boo15boo78b
obo450boo$2014boo72boo34bobo15boo78bo$1985boo17boo118bo96boo332boo$
1985bo18boo117boo430boo$1986b3o557boo$1988bo556bobo$2545bo$1994boo243b
oo303boo$1994boo102boo139bobo420boo$2098boo7boo21bo110bo420bobo$2107bo
22b3o108boo421bo$2105bobo25bo530boo$2105boo4boo19boo$2089boo20bo15bo$
2090bo18bobo15b3o$2004boo84bobo16boo19bo$2004bo86boo36boo430boo$2002bo
bo226boo322boo4boo$2002boo227boo322boo$$2225bo426boo$2223b3o426boo$
2126boo94bo333boo$2004boo120boo17boo75boo332boobboo$2004bo140boo95boo
316bobo$2002bobo11boo224bo305boo12bo$2002boo12bo223bobo305bobo11boo$
2014bobo80boo47boo92boo308bo112boo$2010boobboo77boobboo47bo152bo250boo
90boo19bo$2010boo80bobo38boo12b3o149b3o232boo107bo17bobo$2092bo23boo
16bo14bo76boo74bo232bo107bobo15boo$2091boo23bo14b3o91bobo73boo229b3o
109boo4bo$2117b3o11bo93bo90boo214bo116bobo$2009boo108bo104boo90bo231b
oo99bobo$2009boo4boo297bobo231bobo99bo10boo$2015boo286bo10boo234bo110b
obo$2302bobo184bo60boo111bo$2302bobo184b3o171boo$2297boo4bo188bo155boo
$2296bobo15boo175boo156bo$2229boo65bo17bobo169bo34bo124b3o$2014boo214b
o64boo19bo167b3o32b3o124bo$2014bobo210b3o86boo165bo34bo$2016bo210bo
255boo33boo20boo$2016boo273boo180boo56boo7boo$2292bo181bo57bo$2292bobo
179bobo55bobo$2245boo46boo180boo4boo44boo4boo$2245bobo57boo173bobbo44b
o20boo$2247bo57boo174boo45bobo18bo$2247boo244boo34boo16bobo$2493boo52b
oo6$2237boo$2237boo78boo$2317bo161boo3boo32boo$2231bo83bobo162bo3bo20b
oo11boo$2229b3o83boo160b3o5b3o18bo$2228bo248bo9bo15b3o35boo$2228boo
273bo37boobboo$2248boo295bobo$2248bo273boo23bo$2246bobo274bo23boo$
2246boo272b3o$2520bo$$2232boo$2231bobo$2231bo$2230boo65boo15boo$2296bo
bo15boo$2296bo25boo$2295boo25bo$2320bobo44bo$2320boo43b3o$2339boo23bo$
2235boo103bo23boo$2236bo103bobo$2233b3o66bo38boobboo37bo$2233bo68b3o
40boo35b3o15bo9bo$2305bo75bo18b3o5b3o$2142boo139bo20boo62boo11boo20bo
3bo$2135boo5boo137b3o15bo68boo32boo3boo$2135boo143bo18b3o$2267boo11boo
20bo$2267boo32boo$2137boo17boo8boo$2137boo17bo9boo265boo$2131boo21bobo
276boo$2131boo21boo$2172boo165boo52boo$2172boo62boo21boo37boo38bobo16b
oo34boo$2168boo66boo21bobo36boo17boo19bo18bobo45boo$2168boo72boo17bo
55boo18boo20bo44bobbo36boo$2242boo17boo90boo4boo44boo4boo31bo$2353bobo
55bobo28bobo$2318boo35bo57bo28boo$2173boo65boo76bo27boo7boo56boo$2173b
oo65boo5boo56boo12b3o24boo20boo33boo$2247boo39boo16bo14bo47bo34bo24boo
$2288bo14b3o60b3o32b3o24bobo$2267boo20b3o11bo62bo34bo26bo$2128boo138bo
22bo103boo30boo$2129bo135b3o127bo$2129bobo133bo130b3o$2130boo204boo60b
o$2337bo$2337bobo$2338boo91boo$2166boo187bo74bobo$2166bo186b3o74bo$
2167b3o182bo76boo$2169bo182boo$2153boo181boo$2152bobo182bo$2152bo171b
oo11bobo$2151boo172bo12boo107boo$2131boo192bobo119bobo$2131boo14boo
177boobboo117bo$2123boo22bo182boo117boo$2124bo23b3o$2124bobo23bo145boo
$2125boo169boo$2161boo168boo$2161boo162boo4boo$2298boo25boo$2168bo129b
oo139boo$2143boo23b3o140boo126boo$2143bo8boo17bo139bo$2141bobo9bo16boo
13boo48boo72bobo121bo$2141boo10bobo30bo25bo23bo25bo46boo120b3o$2154boo
30bobo21b3o23bobo21b3o50boo115bo$2187boo20bo27boo20bo53boo115boo$2170b
o38boo48boo58boo129boo$2168b3o149bo129bo$2167bo11bo49bo90bobo125bobo$
2152bo14boo8b3o47b3o91boo125boo$2151bobo22bo49bo280bo$2152bo23boo35boo
11boo279b3o$2213boo85boo132boo74bo$2269boo29boo131bobo73boo$2269boo
162bo90boo$2140boo290boo90bo$2124boo14boo380bobo$2125bo22boo131bo229bo
10boo$2122b3o23bo7boo122bobo227bobo$2122bo23bobo6bobo123boo227bobo$
2146boo7bo32boo48boo32boo231boo4bo$2154boo7boo23boo11boo35boo11boo20bo
48boo15boo163bobo15boo$2164bo36bo49bo21bobo46boo15bobo95boo65bo17bobo$
2161b3o38b3o47b3o19boo65bo96bo64boo19bo$2161bo42bo49bo52boo32boo92b3o
86boo$2148boo157boo126bo$2148bo35boo48boo263boo$2146bobo11boo22bo27boo
20bo97bo167bo$2146boo12bo24b3o23bobo21b3o92b3o167bobo$2158bobo26bo23bo
25bo91bo123boo46boo$2154boobboo50boo117boo122bobo57boo$2154boo299bo57b
oo$2455boo3$2153boo$2153boo4boo$2159boo$$2445boo$2298bo146boo78boo$
2298b3o35boo187bo$2301bo34boo101bo83bobo$2158boo96boo42boo135b3o83boo$
2158bobo96bo178bo$2160bo96bobo176boo$2160boo96boobboo67boo123boo$2262b
oo67boo123bo$2335boo117bobo$2335boo117boo$$2291boo$2291boo36boo109boo$
2314boo13boo108bobo$2314bobo122bo$2316bo121boo65boo15boo$2304boo10boo
186bobo15boo$2304bo199bo25boo$2256boo36boo9b3o195boo25bo$2255bobo16boo
19bo11bo220bobo$2255bo18bobo15b3o233boo$2254boo20bo15bo$2270boo4boo
165boo$2270bobo171bo$2272bo168b3o66bo$2263boo7boo167bo68b3o533bo$2263b
oo248bo531bobo$2491bo20boo531boo$2489b3o15bo$2488bo18b3o$2475boo11boo
20bo$2475boo32boo$$2253boo$2254bo$2254bobo$2255boo$2444boo21boo37boo$
2444boo21bobo36boo17boo$2450boo17bo55boo$2450boo17boo$2273boo$2273bo
252boo$2271bobo174boo76bo$2271boo175boo5boo56boo12b3o$2455boo39boo16bo
14bo$2496bo14b3o$2475boo20b3o11bo$2476bo22bo$2473b3o$2473bo6$2253boo
15boo$2252bobo15boo$2252bo25boo$2251boo25bo$2276bobo$2276boo4$2258bo$
2258b3o$2261bo$2260boo4$2876bo$2874b3o$2873bo$2255boo616boo17bo$2256bo
633b3o11bo$2256bobo630bo14b3o$2257boo630boo16bo14bo$2906boo12b3o$2919b
o$2271boo646boo$2271bobo$2273bo505boo$2273boo504boo137boo$2253boo504bo
139boo17boo$2253bo493bo11b3o137boo$2254b3o488b3o14bo$2256bo472bo14bo
16boo98boo$2729b3o12boo115boo$2262boo468bo$2262boo467boo$2902boo$2882b
oo19bo$2732boo148bobo15b3o$2732boo17boo131bo15bo$2751boo131boo19boo$
2906bo$2272boo515boo112b3o$2272bo516boo112bo$2270bobo$2270boo$2748boo$
2748bo19boo$2749b3o15bobo$2751bo15bo128boo$2272boo471boo19boo129bo$
2272bo78boo392bo151bobo15boo$2270bobo11boo66bo25bo367b3o149boo15boo$
2270boo12bo67bobo21b3o11bo357bo$2282bobo68boo20bo14b3o$2278boobboo50b
oo39boo16bo14bo$2278boo47boo5boo56boo12b3o$2327boo76bo535boo$2405boo
534boo$2754boo$2277boo50boo17boo404bo$2277boo4boo44boo17bo55boo329boo
15bobo$2283boo38boo21bobo36boo17boo329boo15boo200boo$2323boo21boo37boo
567bo$2916boo34bobo$2916bobo33boo$2918bo$2918boo$2282boo$2282bobo69boo
32boo544boo$2284bo69boo11boo20bo528bo15boo$2284boo81bo18b3o529b3o$
2368b3o15bo534bo30boo$2370bo20boo527boo30bobo$2392bo341boo218bo$2350b
oo37b3o341bobo218boo$2320boo28bo38bo343bo172boo$2321bo29b3o378boo172b
oo$2321bobo29bo$2322boo619boo$2407boo534bobo$2383bo23bobo535bo$2383b3o
23bo535boo$2386bo22boo506boo$2385boo14boo493boo19bo$2401boo494bo17bobo
$2744boo151bobo15boo$2744boo152boo4bo18boo$2756boo145bobo16bobo$2756bo
bo144bobo16bo$2758bo145bo10boo4boo$2323boo433boo155bobo$2323boo14boo
576bo$2315boo22bo393boo182boo$2316bo23b3o391bo19boo146boo$2316bobo23bo
391bobo17bo148bo$2317boo416boo15bobo145b3o$2402boo343bo4boo146bo85bo$
2402bobo341bobo235b3o$2404bo341bobo234bo$2404boo329boo10bo179boo54boo$
2335boo397bobo190bobo38boo$2335bo398bo193bo40bo$2333bobo397boo234bobo$
2333boo413boo220boo10bo$2386boo360bo232bobo$2385bobo361b3o229bobo$
2385bo365bo230bo4boo$2384boo584boo15bobo$2969bobo17bo$2969bo19boo$
2968boo$$2413boo578boo$2414bo25bo552bo$2394boo18bobo21b3o550bobo$2332b
oo60boo7boo10boo20bo553boo$2316boo14boo69bo33boo540boo$2317bo22boo59bo
bo575boo$2314b3o23bo60boo4boo48bo$2314bo23bobo44boo20bo47b3o19boo$
2338boo46bo18bobo46bo21bobo$2386bobo16boo34boo11boo20bo11bo$2387boo52b
oo32boo9b3o$2485bo$2485boo10boo$2340boo155bo$2340bo154bobo469boo$2338b
obo11boo141boo13boo456bo$2338boo12bo119boo36boo456bobo$2350bobo119boo
495boo$2346boobboo64boo$2346boo68boo11boo85boo$2429bo86boo$2393boo35b
3o79boo$2389boobboo37bo79boo$2345boo41bobo$2345boo4boo35bo23boo467boo$
2351boo34boo23bo27boo39boo397bobo$2413b3o23bobo40bo34boo362bo$2415bo
23bo39b3o35boo$2438boo39bo$2970boo15boo$2970boo15bobo$2350boo637bo$
2350bobo636boo$2352bo$2352boo231bo$2583b3o$2557boo23bo$2558bo23boo$
2510boo46bobo422bo$2510bo48boobboo37bo378b3o$2511b3o49boo35b3o15bo9bo
351bo$2513bo85bo18b3o5b3o351boo19boo$2424boo160boo11boo20bo3bo360bo15b
o$2417boo5boo62boo96boo32boo3boo357b3o15bobo$2417boo69boo32boo459bo19b
oo$2455boo65bo460boo$2454bobo46boo15bobo$2419boo33bo48boo15boo$2419boo
32boo569boo$2413boo47boo560boo$2413boo46bobo$2462bo94boo52boo373boo$
2556bobo16boo34boo354boo17boo$2556bo18bobo45boo342boo$2450boo103boo20b
o44bobbo$2450boo29boo88boo4boo44boo4boo$2481boo88bobo55bobo334boo$
2573bo57bo335bo$2564boo7boo56boo331b3o12boo$2502boo60boo20boo33boo341b
o14bo16boo$2501bobo83bo34bo357b3o14bo$2501bo82b3o32b3o360bo11b3o$2440b
oo58boo82bo34bo374bo$2440bo53boo117boo399boo$2433boo6b3o50boo117bo400b
oo$2433bo9bo46boo122b3o$2431bobo56bobo61boo60bo$2431boo59bo62bo$2422b
oo68boo61bobo$2422boo55boo75boo$2479boo25boo$2506boo4boo$2512boo36boo$
2477boo71bobo$2477boo73bo21boo$2439boo111boo20bo$2439bo71boo59bobo$
2437bobo67boobboo59boo$2437boo67bobo$2506bo12boo$2505boo11bobo$2518bo$
2517boo$2533boo$2533bo$2534b3o$2536bo$2441boo76boo$2441bobo74bobo$
2443bo74bo35boo15boo$2443boo72boo34bobo15boo$2414boo17boo118bo$2414bo
18boo117boo$2415b3o$2417bo$$2423boo$2423boo102boo$2527boo7boo21bo$
2536bo22b3o$2534bobo25bo$2534boo4boo19boo$2518boo20bo15bo$2519bo18bobo
15b3o$2433boo84bobo16boo19bo$2433bo86boo36boo$2431bobo$2431boo4$2555b
oo$2433boo120boo17boo$2433bo140boo$2431bobo11boo$2431boo12bo$2443bobo
80boo47boo$2439boobboo77boobboo47bo28boo$2439boo80bobo38boo12b3o25boo$
2521bo23boo16bo14bo$2520boo23bo14b3o$2546b3o11bo$2438boo108bo$2438boo
4boo169boo$2444boo169bo$2613bobo$2613boo3$2600boo$2443boo154bobo$2443b
obo153bo$2445bo152boo$2445boo5$2602boo$2601bobo$2601bo$2600boo3$3001b
3o$3001bo$2618boo382bo$2618bobo$2620bo$2620boo7$2610boo$2610boo$$2604b
o$2602b3o$2601bo$2601boo$2621boo$2621bo$2619bobo$2619boo$2678bo$2678b
3o$2605boo74bo$2604bobo73boo$2604bo90boo$2603boo90bo$2693bobo$2682bo
10boo$2681bobo$2681bobo$2676boo4bo$2675bobo15boo$2608boo65bo17bobo$
2609bo64boo19bo$2606b3o86boo$2606bo$2670boo$2671bo$2671bobo$2624boo46b
oo$2624bobo57boo$2626bo57boo$2626boo7$2616boo$2616boo78boo$2696bo$
2610bo83bobo$2608b3o83boo$2607bo$2607boo$2627boo$2627bo$2625bobo$2625b
oo3$2611boo$2610bobo$2610bo$2609boo65boo15boo$2675bobo15boo$2675bo25b
oo$2674boo25bo$2699bobo$2699boo$$2614boo$2615bo$2612b3o66bo$2612bo68b
3o$2684bo$2662bo20boo$2660b3o15bo$2659bo18b3o$2646boo11boo20bo$2646boo
32boo6$2615boo21boo37boo$2615boo21bobo36boo17boo$2621boo17bo55boo$
2621boo17boo$$2697boo$2619boo76bo$2619boo5boo56boo12b3o$2626boo39boo
16bo14bo$2667bo14b3o$2646boo20b3o11bo$2647bo22bo$2644b3o$2644bo!


0
Paul
5/24/2004 4:54:23 PM
comp.theory.cell-automata 542 articles. 0 followers. amarbravo (1) is leader. Post Follow

36 Replies
1070 Views

Similar Articles

[PageSpeed] 21

Paul Chapman <paul@igblan.free-online.co.uk> wrote or quoted:

> Dave Greene and Paul Chapman wish to announce the joint construction of a
> prototype programmable universal* constructor. [...]

> *The authors tentatively claim universality, but a lot of work still has to
> be done to find recipes for eg eaters in close proximity.

"Universal construction" in an irreversible automata has not - to my
knowledge - even been defined.

My brief stab - a constructor is universal if it can be "programmed"
<cough> to produce any specified finite field at some future time - 
provided that the field is not a garden of eden - or can only be
reached by passing through one.

Proving a structure has this property seems likely to be tricky ;-)
-- 
__________
 |im |yler  http://timtyler.org/  tim@tt1.org
0
Tim
5/24/2004 7:34:20 PM
Tim Tyler <tim@tt1lock.org>  writes:

>"Universal construction" in an irreversible automata has not - to my
>knowledge - even been defined.

>My brief stab - a constructor is universal if it can be "programmed"
><cough> to produce any specified finite field at some future time - 
>provided that the field is not a garden of eden - or can only be
>reached by passing through one.

>Proving a structure has this property seems likely to be tricky ;-)

It would be almost impossible for the near future, I think...

So why not define a notion of "restricted universality" which is still
interesting? A constructor would be universal with respect to a certain
class of patterns if it can construct every pattern of that class, of which
it is also a member.

The author of the original posting seems to have something similar in mind
when he writes:

>> The pattern nevertheless uses only five different still lifes: block,
>> beehive, boat, tub and eater. This is to facilitate the later
>> construction of a replicator.

The pattern class would consist of all still lifes composed of the five
"elementary" still lifes mentioned above -- plus maybe one ingoing glider
which activates the pattern.

With this definition, there is a good chance to prove something.

-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/1/2004 7:34:10 AM
Tim,

> "Universal construction" in an irreversible automata has not - to my
> knowledge - even been defined.
>
> My brief stab - a constructor is universal if it can be "programmed"
> <cough> to produce any specified finite field at some future time -
> provided that the field is not a garden of eden - or can only be
> reached by passing through one.

The <cough> is a key detail. :)

There's no way to canonically distinguish "software" from "hardware" in a
CA.  I could, for example, define a constructor (type "A") with "hardware"
consisting of all dead cells, and "software" an ancenstor pattern of the
desired construction.  I can easily prove that this is universal. :)

[A CA has a "dead" cell state iff it has a state such that if a cell and all
of its neighbours have that state, the cell will have the same state in the
next generation.  We can confine our discussion to these kinds of CAs.]

So let's have another stab: let's say a certain type of constructor (type
"B") may not have any non-dead cells where the final pattern has non-dead
cells.  Glider constructions in Life would fit this category, for example.
This is already hard to prove to be "universal".

We could further require that a constructor work as follows (type "C"): that
the construction site be in the opposite quadrant (or octant for a 3D CA,
etc) from the constructor.  (This is not quite true of the published Life
constructor, but can be made so with a trivial rearragement of components.)

What then becomes apparent is that we can ask whether our type-C constructor
(or more rigorously, our *family* of type-C constructors, the family spanned
by all possible programs) can construct all patterns which are type-B
constructible.  This may prove a more fruitful area of research.

Cheers, Paul


0
Paul
6/1/2004 9:13:06 AM
"Paul Chapman" <paul@igblan.free-online.co.uk> writes:

>Tim,

>> "Universal construction" in an irreversible automata has not - to my
>> knowledge - even been defined.

Then we should define it. An "official" definition would be very useful to
focus the research. I would like to see a universal constructor actually
implemented.

I add some remarks what such a definition could look like.

>> My brief stab - a constructor is universal if it can be "programmed"
>> <cough> to produce any specified finite field at some future time -
>> provided that the field is not a garden of eden - or can only be
>> reached by passing through one.

>The <cough> is a key detail. :)

>There's no way to canonically distinguish "software" from "hardware" in a
>CA.  I could, for example, define a constructor (type "A") with "hardware"
>consisting of all dead cells, and "software" an ancenstor pattern of the
>desired construction.  I can easily prove that this is universal. :)

I disagree. We should, as already von Neumann did, consider the program as
something static. It could consist of still lifes, or maybe oscillators. The
point is that the program, when left alone, must stay the same forever.

>So let's have another stab: let's say a certain type of constructor (type
>"B") may not have any non-dead cells where the final pattern has non-dead
>cells.

So you have an empty "construction site" somewhere. I agree.

There should also be a "program area", able to contain programs of every
size. They should not overlap.

>We could further require that a constructor work as follows (type "C"):
>that the construction site be in the opposite quadrant (or octant for a 3D
>CA, etc) from the constructor. (This is not quite true of the published
>Life constructor, but can be made so with a trivial rearragement of
>components.)

It is better to weaken that request a bit: Objects of every size should be
constructible. This requires a construction area of unboundend size but
doesn't specify its shape.


This are my ideas for the definition. More must be added. What do you think?

-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/7/2004 8:35:55 PM
Markus Redeker <cep@ibp.de> wrote or quoted:
> "Paul Chapman" <paul@igblan.free-online.co.uk> writes:

> >> "Universal construction" in an irreversible automata has not - to my
> >> knowledge - even been defined.
> 
> Then we should define it. An "official" definition would be very useful to
> focus the research. I would like to see a universal constructor actually
> implemented.
> 
> I add some remarks what such a definition could look like.
> 
> >> My brief stab - a constructor is universal if it can be "programmed"
> >> <cough> to produce any specified finite field at some future time -
> >> provided that the field is not a garden of eden - or can only be
> >> reached by passing through one.
> 
> >The <cough> is a key detail. :)
> 
> >There's no way to canonically distinguish "software" from "hardware" in a
> >CA.  I could, for example, define a constructor (type "A") with "hardware"
> >consisting of all dead cells, and "software" an ancenstor pattern of the
> >desired construction.  I can easily prove that this is universal. :)
> 
> I disagree. We should, as already von Neumann did, consider the program as
> something static. It could consist of still lifes, or maybe oscillators. The
> point is that the program, when left alone, must stay the same forever.

I agree that the cough omits something important - but I'm not convinced
that it can't be satisfyingly fleshed out.

The universal constructor should be regarded as a fixed program, accepting 
data input, and producing an output.  The input is its "program".  It 
need not necessarily be a linear stream of instructions - but it could 
be.

Is the program necessarily static?  No - the instructions should 
"interfere" with the constructor, yet still leave it as a universal
construction machine.  However this simply seems like a unnecessary 
confusion - much like allowing self-modifying code. You could do that - 
but it's not needed - fix the program and little is lost.

"Universal construction in irreversible automata" seems like a
bit of a messy concept.

IMO, the focus for universal construction should be on reversible 
automata - where the concept is cleaner - and perhaps more useful.
-- 
__________
 |im |yler  http://timtyler.org/  tim@tt1lock.org  Remove lock to reply.
0
Tim
6/7/2004 10:10:58 PM
"Tim Tyler" <tim@tt1lock.org> wrote in message
news:HyyLMA.Du2@bath.ac.uk

> [...]
> "Universal construction in irreversible automata" seems like a
> bit of a messy concept.
> 
> IMO, the focus for universal construction should be on reversible 
> automata - where the concept is cleaner - and perhaps more useful.

Isn't this something that keeps getting discussed here, in one 
context or another? Anyway, note that von Neumann's constructor 
runs in a decidedly irreversible environment. Indeed, wasn't this 
the inspiration for Moore's Garden of Eden theorem, and thereby 
the opening step in what has been a long discussion of universality 
and what it should mean? 

As far as I understand it, all that is required is to exhibit a
mechanism which will construct a variety of artifacts, hopefully 
useful and interesting artifacts. Von Neumann wanted to include 
a Turing machine in his constructor just in order to anticipate 
a wide variety of useful constructions, much more than simple 
copies of things. Universality and self-reproduction comes into 
play when the machins so exhibited can recreate itself. No doubt 
somewhere off to the side, in some vacant lot or other. 

No doubt some criterion is needed to exclude something as simple 
as Langton's ants, and it is evidently impossible to construct 
Garden's of Eden within the same cell space and laid out on the 
same floor plan. That doesn't mean that models of a Garden of Eden 
can't be constructed on the basis of another representation. 

Of course, if someone wants to design one of these machines so 
that it will operate in a reversible space, there is no reason 
why the attempt should not be made. It is a matter of opinion, 
or perhaps experience, to decide whether such a restriction would 
complicate the task or not. 


- hvm 


-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
0
McIntosh
6/8/2004 3:01:29 AM
Tim Tyler <tim@tt1lock.org>  writes:

>The universal constructor should be regarded as a fixed program,
>accepting data input, and producing an output. The input is its
>"program". It need not necessarily be a linear stream of instructions -
>but it could be.

>Is the program necessarily static?  No - the instructions should
>"interfere" with the constructor, yet still leave it as a universal
>construction machine.

"Static" may be a bit too much. But what we need is an _inactive_ program,
that can't do anything without the constructor. This is similar to the
definition of "reduction" in the context of NP-completeness. There, the
program which transforms the input for one problem to input for another
problem, must be polynomial, to make sure that the real computation occurs
elsewhere. Similarily, the program of a constructor should not do the
construction on its own but is read by the constructor. How that is
accomplished is not so important.

-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/8/2004 7:33:18 AM
"McIntosh Harold V." <mcintosh@servidor.unam.mx> writes:

>As far as I understand it, all that is required is to exhibit a
>mechanism which will construct a variety of artifacts, hopefully
>useful and interesting artifacts.

There are already three different levels of construction:

1) "Programmable constructor": a machine that can be programmed to
   construct every pattern from a specified infinite class.
2) "Self-reproducing constructor": a programmable constructor that is
   in its own class of constructible patterns.
3) "Universal constructor": a self-reproducing constructor that can
   construct everything except that which can only be reached through
   a Garden of Eden.

Even a constructor of type (1) would be a great achievement -- say a
machine that could construct every pattern of non-interacting blocks
in Life. John von Neumann attempted (2). It is not clear whether a
type (3) constructor exists at all.

>No doubt some criterion is needed to exclude something as simple 
>as Langton's ants, and it is evidently impossible to construct 
              ^^^^
>Garden's of Eden within the same cell space and laid out on the 
>same floor plan. That doesn't mean that models of a Garden of Eden 
>can't be constructed on the basis of another representation. 

Do you mean his self-reproducing loops? They are of a different
species -- not machines, but something more biological. It might be
possible to build something similar in Life (from Herschel loops or
so), but I would not call that a constructor, even if it were
programmable. For me, construction is like building machines in the
real world: first you put the parts together and then you switch it
on. We should limit the word "construction" to that kind of process.
(For the other process, biological metaphors like "giving birth" will
be more appropriate.)


-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/8/2004 8:08:02 AM
Markus Redeker <cep@ibp.de> wrote or quoted:
> "McIntosh Harold V." <mcintosh@servidor.unam.mx> writes:

> >No doubt some criterion is needed to exclude something as simple 
> >as Langton's ants, and it is evidently impossible to construct 
>               ^^^^
> >Garden's of Eden within the same cell space and laid out on the 
> >same floor plan. That doesn't mean that models of a Garden of Eden 
> >can't be constructed on the basis of another representation. 
> 
> Do you mean his self-reproducing loops? They are of a different
> species -- not machines, but something more biological.

Langton's ant:

  http://users.libero.it/acnard/ant.html

....constructs all kinds of stuff from a set of initial conditions - but it 
isn't very clear whether it could be described as a universal constructor.

It seems to rather lack any concept of the "constructor/program" 
distinction - so if it can construct arbitrary fields at an
arbitrary specified future date, the "program" for doing so might
be quite a mess.
-- 
__________
 |im |yler  http://timtyler.org/  tim@tt1lock.org  Remove lock to reply.
0
Tim
6/8/2004 9:03:10 AM
Tim Tyler <tim@tt1lock.org> wrote or quoted:

[universal constructor]

> Is the program necessarily static?  No - the instructions should 
> "interfere" with the constructor, yet still leave it as a universal
> construction machine.  However this simply seems like a unnecessary 
> confusion - much like allowing self-modifying code. [...]

Oops - I meant to say "could" at the end of line 1, here.
-- 
__________
 |im |yler  http://timtyler.org/  tim@tt1lock.org  Remove lock to reply.
0
Tim
6/8/2004 9:04:59 AM
Markus,

> >There's no way to canonically distinguish "software" from "hardware" in a
> >CA.  ...
>
> I disagree. We should, as already von Neumann did, consider the program as
> something static. It could consist of still lifes, or maybe oscillators.
The
> point is that the program, when left alone, must stay the same forever.

My CA knowledge is not broad (I am a Life "specialist"), but I do know that
Rule 110 doesn't support (information-carrying) stable or cyclic patterns.
Nevertheless, it does support information-carrying gliders, and is capable
of universal computation (Cook).

I already narrowed the class of CAs I was considering in my various
definitions (requiring a "dead" state, which Rule 110 has, for example).

I am concerned that further restrictions, like supporting "static" programs,
are not terribly "natural" (Platonic), and in fact are an artifact of our
pea-brained human preferences for "mechanistic" patterns and behaviours -- 
since we have difficulty grasping ideas which cannot be broken down
systematically.

(Nevertheless, after thousands of years of mysticism and vitalism, it was
interesting that we finally discovered that many, if not most, of the
processes of life, and in particular of course of inheritance, are
mechanistic.  But we can just about imagine a different sort of universe
with more amorphous low-level structures and processes which nevertheless
allow something like "intelligence" or "consciousness" to exist.)

> So you have an empty "construction site" somewhere. I agree.
>
> There should also be a "program area", able to contain programs of every
> size. They should not overlap.

In practice, we may have to limit consideration to mechanistic, systematic
definitions and solutions.  Nevertheless, I can (vaguely) imagine a CA where
an "interesting" kind of universal construction is possible, but only if
hardware and software are mixed up together.

> It is better to weaken that request a bit: Objects of every size should be
> constructible. This requires a construction area of unboundend size but
> doesn't specify its shape.

In the work on the Life constructor, this was obviously a good practical
design goal -- and an "obvious" choice to a human researcher. :)  I tried in
my brief exploration of definitions to invoke some geometry (quadrants, etc)
in an attempt to make the definitions more "fundamental".  I suspect,
however, that I have at least partially failed. :)

Cheers, Paul


0
Paul
6/8/2004 11:50:41 AM
Tim,

> The universal constructor should be regarded as a fixed program, accepting
> data input, and producing an output.  The input is its "program".  It
> need not necessarily be a linear stream of instructions - but it could
> be.

Dave Greene and I have some long-term ideas about allowing (non-recursive!)
subroutine calls in our Life constructor, and arranging the "program" in two
dimensions.  The chief motive, however, is to be able to actually publish a
*complete* self-replicator which isn't terabytes in size. :)

> Is the program necessarily static?  No - the instructions should
> "interfere" with the constructor, yet still leave it as a universal
> construction machine.  However this simply seems like a unnecessary
> confusion - much like allowing self-modifying code. You could do that -
> but it's not needed - fix the program and little is lost.

For many CAs, including Life, fine.  But I contend there are probably CAs
where universal construction is possible but a "fixed" program in this sense
is not.

Cheers, Paul


0
Paul
6/8/2004 12:00:37 PM
Harold,

> ... Von Neumann wanted to include
> a Turing machine in his constructor just in order to anticipate
> a wide variety of useful constructions, much more than simple
> copies of things.

I wanted to include an MRM in our constructor, but Dave Greene talked me out
of it -- for now. :)

I assume that Von Neumann's original constructor was far from universal, and
in particular capable only of constructing "static" patterns -- ie patterns
which did not contain arbitrary cells with states used for the transmission
of information.  I'd guess that more recent CAs have the same restriction.

Does anyone know if a CA has been designed which IS capable of non-type-"A"
universal construction?  Ie, say of type-"B"?  The difficulty seems to me to
be that in order to move information around (specifically from the program
store to the construction site), a CA must either employ special states (Von
Neumann) or support information-carrying patterns (Life), either of which is
going to mean that there will be some arbitrary non-GOE patterns which are
very difficult to produce out of thin air. :)

Becuase I am a simpleton, I expect the only contribution I will make will be
simplistic, like Markus's "every pattern of non-interacting blocks in Life".

But I would love to see attempts made to design a CA capable of implementing
a type-"B" universal constructor. :)


> Universality and self-reproduction comes into
> play when the machins so exhibited can recreate itself. No doubt
> somewhere off to the side, in some vacant lot or other.

Self-replication is easier to define and implement than universal
construction, because it avoids the problems of creating arbitrary patterns
of transient states.

Cheers, Paul


0
Paul
6/8/2004 12:17:53 PM
> Markus,
> 
> > >There's no way to canonically distinguish "software" from "hardware" in a
> > >CA.  ...
> >
> > I disagree. We should, as already von Neumann did, consider the program as
> > something static. It could consist of still lifes, or maybe oscillators.
> The
> > point is that the program, when left alone, must stay the same forever.
> 
> My CA knowledge is not broad (I am a Life "specialist"), but I do know that
> Rule 110 doesn't support (information-carrying) stable or cyclic patterns.
> Nevertheless, it does support information-carrying gliders, and is capable
> of universal computation (Cook).

I do not understand well when you talk about to patterns or gliders.
Glider can be considered like cyclic pattern.

Carrying-information between gliders in Rule 110 is conserved thanks to
solitons, several Rule 110 objects illustrate this phenomenon.

Cyclic tag system (developed by Matthew Cook) in Rule 110 defines two
static cyclical regions. In the left an enormous cycle formed by groups
of gliders A^4 that represent the operators and in the right another
great cycle formed by groups of gliders E's that represent the data.

Dear Paul not know the environment. What is RLE format?

-genaro


-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
0
Genaro
6/10/2004 2:58:01 PM
Genaro Juarez Martinez <genarojm@correo.unam.mx> wrote or quoted:

> What is RLE format?

``Run-length encoding, which is a simple (but not very efficient) method 
  of file compression. In Life the term refers to a specific ASCII 
  encoding used for Life patterns (and patterns for other similar 
  cellular automata).  This encoding was introduced by Dave Buckingham and 
  is now the usual means of exchanging Life patterns (especially large 
  ones) by e-mail (Silver).''

 - http://www.ericweisstein.com/encyclopedias/life/RLE.html
-- 
__________
 |im |yler  http://timtyler.org/  tim@tt1lock.org  Remove lock to reply.
0
Tim
6/10/2004 4:24:08 PM
"Tim Tyler" <tim@tt1lock.org> wrote in message
news:Hz3pK8.3Mo@bath.ac.uk

> Genaro Juarez Martinez <genarojm@correo.unam.mx> wrote or quoted:
> 
> > What is RLE format?
> 
> ``Run-length encoding, which is a simple (but not very efficient) method 
>   of file compression. In Life the term refers to a specific ASCII 
>   encoding used for Life patterns (and patterns for other similar 
>   cellular automata).  This encoding was introduced by Dave Buckingham and 
>   is now the usual means of exchanging Life patterns (especially large 
>   ones) by e-mail (Silver).''
> 
>  - http://www.ericweisstein.com/encyclopedias/life/RLE.html

More specifically, if the letter x occurs 10 times, write 10x rather 
than xxxxxxxxxx. This is especialy important for publishing Life 
configurations because of the large number of blanks they typically 
contain. 

Of course there are better codes - the Huffman codes, for example. 
But given that decoding takes time and can be complicated, RLE seemed 
a good compromise which met the requirements of the Life enthusiasts. 

Rule 110, as we know, is beset by a similar problem, for which RLE is 
not a solution. Cook has one notation which is helpful; Genaro has 
another. I once tried to ZIP code some cellular automaton fields, but 
it didn't work because they were already pretty random. 

- hvm 




-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
0
Mcintosh
6/10/2004 6:58:40 PM
Genaro,

> I do not understand well when you talk about to patterns or gliders.
> Glider can be considered like cyclic pattern.

In the algebra I've developed privately for working with Life, I make no
distinction between still lifes, oscillators and spaceships -- I just call
them all "periodicals" which have certain periods and velocities.

But whether an information-carrying pattern is stationary or moving makes a
large practical difference to the "machinery" which processes the
information.  Stationary patterns, for example, can be interrogated many
times for their information by a single "machine", while (in the absence of
reflectors) moving patterns like Rule 110's solitons require multiple copies
either of the machinery or of the information.  Cook's Rule 110 computer
starts with an infinite number of copies of the Cyclic-Tag-System rule
table, for example.

> Dear Paul not know the environment. What is RLE format?

I see Tim and Harold have answered that.  For programs which can read RLE
and run Life patterns, look at the bottom of:

http://entropymine.com/jason/life/links.html

Cheers, Paul


0
Paul
6/10/2004 7:36:27 PM
Tim Tyler <tim@tt1lock.org>  writes:

>Langton's ant:

>  http://users.libero.it/acnard/ant.html

>...constructs all kinds of stuff from a set of initial conditions - but it 
>isn't very clear whether it could be described as a universal constructor.

>It seems to rather lack any concept of the "constructor/program" 
>distinction - so if it can construct arbitrary fields at an
>arbitrary specified future date, the "program" for doing so might
>be quite a mess.

This is because you view everything that causes the creation of a certain
pattern as a program for that pattern. But to prove that something is a
programmable constructor, we only have to make sure that there exists _one_
program that constructs each pattern.

In fact, we have therefore two classes of patterns that come with a
programmable constructor: (1) the class of patterns the constructor can
construct, (2) the class of pattern the constructor uses as programs -- its
programming language, so to speak.

But have an effectively programmable constructor, it must be possible to
find a program for each pattern by a simple process, a function that
transforms patterns in (1) to patterns in (2). One could request that the
transformation takes polynomial (or even linear?) time. (Note that this
transformation function doesn't have to create a good program for each
pattern; we are dealing here only with existence proofs.)

Another concept uses the idea that to construct a complex object, one may
construct its parts and then put them together. So if pattern A consists of
patterns B next to C, then a program for A can be created from the programs
for B and C by a simple transformation. One example would be the description
of a configuration by the coordinates of its cells: If B and C are
non-overlapping, then a plan for A can be created by concatenating the plans
of B and C. (This kind of description is probably not useful for a
constructor in Life.)

To conclude, I wouldn't consider Langton's ant as a programmable constructor
for anything, unless there is a programming language specified.

-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/16/2004 8:55:33 AM
"Genaro Juarez Martinez" <genarojm@correo.unam.mx> writes:

>Carrying-information between gliders in Rule 110 is conserved thanks to
>solitons, several Rule 110 objects illustrate this phenomenon.

>Cyclic tag system (developed by Matthew Cook) in Rule 110 defines two
>static cyclical regions. In the left an enormous cycle formed by groups
>of gliders A^4 that represent the operators and in the right another
>great cycle formed by groups of gliders E's that represent the data.

Where is a good description of these gliders (and the rest of "rule 110
technology")?


-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/16/2004 9:00:27 AM
Markus Redeker <cep@ibp.de> wrote or quoted:
> Tim Tyler <tim@tt1lock.org>  writes:

> >Langton's ant:
> 
> >  http://users.libero.it/acnard/ant.html
> 
> >...constructs all kinds of stuff from a set of initial conditions - but it 
> >isn't very clear whether it could be described as a universal constructor.
> 
> >It seems to rather lack any concept of the "constructor/program" 
> >distinction - so if it can construct arbitrary fields at an
> >arbitrary specified future date, the "program" for doing so might
> >be quite a mess.
> 
> This is because you view everything that causes the creation of a certain
> pattern as a program for that pattern. But to prove that something is a
> programmable constructor, we only have to make sure that there exists _one_
> program that constructs each pattern.

?

You are saying that there can't be _two_ programs that do this?!?

To present a counter-example - a simple counter that counts from 0 will 
construct any finite pattern you care to mention - and a counter that 
counts from 1 will do so as well.

> In fact, we have therefore two classes of patterns that come with a
> programmable constructor: (1) the class of patterns the constructor can
> construct, (2) the class of pattern the constructor uses as programs -- its
> programming language, so to speak.
> 
> But have an effectively programmable constructor, it must be possible to
> find a program for each pattern by a simple process, a function that
> transforms patterns in (1) to patterns in (2). One could request that the
> transformation takes polynomial (or even linear?) time. (Note that this
> transformation function doesn't have to create a good program for each
> pattern; we are dealing here only with existence proofs.) [...]

This is not part of the definition of universal construction - as far
as I'm aware.

AFAICS, it doesn't matter how complex the program to transform the
output into a program is - or how long it takes to run.  At least
I don't think such constraints have been associated with the
idea of universal construction historically.

Such constraints *might* be part of the definition of an "effectively 
programmable constructor" - but that is not a term with a standard 
definition - as far as I can tell:

http://google.com/search?q="effectively+programmable+constructor"

> To conclude, I wouldn't consider Langton's ant as a programmable constructor
> for anything, unless there is a programming language specified.

You do need a program - but AFAICS, there may be a set of initial 
condtions for Langton's ant that makes it act as a universal constructor - 
i.e. a program that accepts a program in a defined format, and produces as 
an output an arbitrary specified region.

Langton's ant is Turing complete: it might be contruction-universal as well.
-- 
__________
 |im |yler  http://timtyler.org/  tim@tt1lock.org  Remove lock to reply.
0
Tim
6/16/2004 11:10:06 AM
"Paul Chapman" <paul@igblan.free-online.co.uk> writes:

>I wanted to include an MRM in our constructor, but Dave Greene talked me
>out of it -- for now. :)

What is a MRM?

>Becuase I am a simpleton, I expect the only contribution I will make will
>be simplistic, like Markus's "every pattern of non-interacting blocks in
>Life".

The constructor that you have posted looks as if it can construct every
pattern of blocks, provided that there is enough distance between them.
Is this true?

-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/17/2004 8:00:18 AM
"Paul Chapman" <paul@igblan.free-online.co.uk> writes:

>In the algebra I've developed privately for working with Life, I make no
>distinction between still lifes, oscillators and spaceships -- I just call
>them all "periodicals" which have certain periods and velocities.

What kind of algebra is this (or is planned to become later)?

I am always interested in methods to understand the behaviour of a cellular
automaton on a theoretical level.

>But whether an information-carrying pattern is stationary or moving makes a
>large practical difference to the "machinery" which processes the
>information. Stationary patterns, for example, can be interrogated many
>times for their information by a single "machine", while (in the absence of
>reflectors) moving patterns like Rule 110's solitons require multiple
>copies either of the machinery or of the information.

Well, one could think of a moving computer with information stored in
gliders, interrogated by faster gliders...

-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/17/2004 8:12:46 AM
> >I wanted to include an MRM in our constructor, but Dave Greene talked me
> >out of it -- for now. :)
>
> What is a MRM?

Minsky Register Machine, a Turing-equivalent computer.  I built a Life
pattern to emulate an MRM in November 2002.  See

http://www.igblan.free-online.co.uk/igblan/ca/index.html

> The constructor that you have posted looks as if it can construct every
> pattern of blocks, provided that there is enough distance between them.
> Is this true?

Provided there is enough distance between them, yes.  But we (Dave Greene
and I) don't yet have an upper bound on that distance -- well, I'd be
confident at around the 100-cell mark. :)

The research we have done strongly indicates that all such patterns are
probably buildable.  A proof is a long way off, though.

Cheers, Paul


0
Paul
6/17/2004 6:41:57 PM
"Markus Redeker" <cep@ibp.de> wrote in message
news:upjrac.0c.ln@ID-219982.user.uni-berlin.de...
> "Paul Chapman" <paul@igblan.free-online.co.uk> writes:
>
> >In the algebra I've developed privately for working with Life, I make no
> >distinction between still lifes, oscillators and spaceships -- I just
call
> >them all "periodicals" which have certain periods and velocities.
>
> What kind of algebra is this (or is planned to become later)?

Well, there's an informal notation for writing down reactions, which is
really nothing new.  But I'm also working on a (flat ASCII) notation to
specify reactions exactly.  I've successfully used the algebra to work out
specific, if rather trivial, problems.

Later on, it *might* become part of an executable scripting language to
describe properties and behaviours of Life patterns.

> I am always interested in methods to understand the behaviour of a
cellular
> automaton on a theoretical level.

My "algebra" is very much an engineering tool.  It is exact in the sense of
describing patterns in detail, but is nowhere near powerful enough to start
making generalizations about, say, limits in statistical behaviour of CAs.

I'm just a simple engineer with some very basic knowlelge of trivial Group
Theory. :)

> Well, one could think of a moving computer with information stored in
> gliders, interrogated by faster gliders...

Again, though, unless one or other set of gliders is reflectable, or
convertible to slower gliders say, the interaction between them can only
happen once.  That's not enough time to do recursive computations. :)

Cheers, Paul


0
Paul
6/17/2004 6:48:48 PM
"Markus Redeker" <cep@ibp.de> wrote in message

> Where is a good description of these gliders (and the rest of "rule 110
> technology")?

We are finishing a paper "Gliders in Rule 110," where we displayed
several constructions in Rule 110 objects. We hoped to soon display with
all these constructions and is interesting for several investigators.

For example you can construct a fuse with the D1 and G gliders (we must
take the classification from gliders propose by Cook) with the following
expression:

{D1(A,f1_1)-e}*-G(H,f1_1)

We have a program (totally gratuitous) to reproduce these collisions
codified in phases fi_1 (regular expressions). You can download of:

http://delta.cs.cinvestav.mx/~mcintosh/comun/s2001/s2001.html

Some Rule 110 objects constructed by Cook you can see in his cyclic tag
system illustrated in the Wolfram's book, in:

http://www.wolframscience.com

Rule 110 can be as complicated as Life in several constructions,
synchronization of multiple collisions is very complicated. For example
synchronize many solitons with different speeds between several gliders,
all of them different ones.

A good description of gliders in Rule 110 was displayed by Cook in:


http://w3.datanet.hu/~cook/Workshop/CellAut/Elementary/Rule110/110pics.html
(January 1999)

the other is displayed by McIntosh in:

http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html

and other in:

http://delta.cs.cinvestav.mx/~mcintosh/comun/s2001/s2001.html

-genaro




-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
0
Genaro
6/17/2004 8:58:58 PM
Tim Tyler <tim@tt1lock.org>  writes:

>Markus Redeker <cep@ibp.de> wrote or quoted:

>> This is because you view everything that causes the creation of a certain
>> pattern as a program for that pattern. But to prove that something is a
>> programmable constructor, we only have to make sure that there exists
>> _one_ program that constructs each pattern.

>?

>You are saying that there can't be _two_ programs that do this?!?

No. I wanted to say that in order to _prove_ trat something is a
constructor, we need only one program for each pattern.

>> But have an effectively programmable constructor, it must be possible to
>> find a program for each pattern by a simple process, a function that
>> transforms patterns in (1) to patterns in (2). One could request that the
>> transformation takes polynomial (or even linear?) time. (Note that this
>> transformation function doesn't have to create a good program for each
>> pattern; we are dealing here only with existence proofs.) [...]

>This is not part of the definition of universal construction - as far
>as I'm aware.

Yes, you are right. It would be no good idea to request such a thing -- even
if one probably will use such a transformation to prove that a constructor
is universal.


-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/18/2004 7:12:51 AM
"Genaro Juarez Martinez" <genarojm@correo.unam.mx> writes:

>"Markus Redeker" <cep@ibp.de> wrote in message

>> Where is a good description of these gliders (and the rest of "rule 110
>> technology")?
[...]
>A good description of gliders in Rule 110 was displayed by Cook in:

>http://w3.datanet.hu/~cook/Workshop/CellAut/Elementary/Rule110/110pics.html
>(January 1999)

This is probably the text I need, but the page doesn't exist anymore. Has
anyone the text or another link?

-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/21/2004 2:32:25 PM
In article <phr6bc.gj4.ln@ID-219982.user.uni-berlin.de>,
 Markus Redeker <cep@ibp.de> wrote:

> >http://w3.datanet.hu/~cook/Workshop/CellAut/Elementary/Rule110/110pics.html
> >(January 1999)
> 
> This is probably the text I need, but the page doesn't exist anymore. Has
> anyone the text or another link?

As I understand it, Stephen Wolfram sued Cook to take down those pages.
McIntosh has replicated a lot of Cook's work, though:
http://delta.cs.cinvestav.mx/~mcintosh/comun/RULE110W/RULE110.html

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
0
David
6/21/2004 5:06:00 PM
"David Eppstein" <eppstein@ics.uci.edu> wrote in message
news:eppstein-379FE2.10055921062004@news.service.uci.edu

> As I understand it, Stephen Wolfram sued Cook to take down those pages.
> McIntosh has replicated a lot of Cook's work, though:
> http://delta.cs.cinvestav.mx/~mcintosh/comun/RULE110W/RULE110.html 

There was a time when searches for topics like Rule 110, but cellular 
automata in general, turned up Matthew Cook's page at wri.com with 
lots of other things, like a hovercraft and a list of hungarian words. 
One of the search engines was apparently a bit more intrusive, but the 
most readily accessible page had a listing of gliders which had been 
discovered in Rule 110, together with some properties such as its 
lattice periodicity which implied a parity rule for collisions, and 
some challenges, such as maximum speed limits and discovering additional
gliders. 

Somewhat after a conference at the Santa Fe Institute, toweards the end
of the year, wri.com started giving "page inaccessible" messages and 
demanding a password, whereas information on one of the internet 
discussion groups located the page on a hosting network in Hungary. 
Having lost the wri.com reference, the latter was substituted in 
references, it being thought necessary to acknowledge and leave some 
trace of the information upon which we had based our own interest and 
investigations. 

After the latter reference disappeared as well, inquiry to Cook revealed
that he had withdrawn the page in deference to some discussion with 
Stephen Wolfram. Since I had neither copied the page in question, not 
knowing how to do so at the time, nor thought to preserve the exact 
wri.com reference, we have left the other item as a testimonial to and 
acknowledgement of, our sources. No doubt this state of affairs 
represents an inconvenience for those who wish to check references, and
one could really wish that, now that time has passed and emotions have 
cooled, Mr. W would relent and allow this historical material to be 
restored. I haven't been able to find it in the WayBack Machine, for 
example. 

As to whether we have a fair representation of Cook's work, it is hard 
to say. Having laboriously depixellated his illustrations, we were able
to reconstruct his gliders, and from there on we subjected Rule 110 to 
an exhaustive analysis using our own procedures. Unfortunately although
we found a great many of the reactions which he used in his universality
arguments, we didn't fully appreciate the significance of all of them, 
the leapfrog being an outstanding example. 

This has been commented on in my "gadgeteering" article. But that is 
only half of the story, and the other half, as yet untold in a concrete
and published form, consists in the invocation of the cyclic tag 
system. That part is ingenious (also!); not just any old tag system will
do. There are still some delicate synchronization issues. 






-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
0
McIntosh
6/22/2004 1:57:01 AM
"Markus Redeker" <cep@ibp.de> wrote in message

> This is probably the text I need, but the page doesn't exist anymore. Has
> anyone the text or another link?

Indeed the reference of Matthew Cook disappear. Nevertheless
historically exists, we have a copy of the document when was available
in Internet, I do not know whichever people managed print or save the
reference.

In Rule 110 history the document of Cook is important because it
establishes an extensive classification of gliders (greater than the one
of Doug Lind). We used it in our investigations (initiated in 1999 by
McIntosh).

A, B, B-, B^, E, E-, F, G, H gliders and glider Gun. Where B-, B^, E, G
gliders are extensible. In addition Cook discusses some important points
that they exist between Life and Rule 110.

The problem of which the information was retired does not imply that it
is not possible refer, are found important results in a complicated
process of investigation to construct cyclic tag system. For example
like the construction of Paul Chapman or the Turing machine constructed
by Paul Rendell discussed with detail in the book of Andrew Adamatzky
"Collision-Based Computing."

Partial results found by Cook similar in Life are interesting and we
hoped that Cook can publish them.

For example the Acorn object in Life was found in an attempt to find
limitless growth. Cook found that the collision between
A->G$^{\infinity}$ gliders is the one that greater number of generations
needs to become stabilized. Nonmemory if in Life exists a pattern that
never becomes stabilized or extensible gliders.

Results of Cook are displayed in the Wolfram's book, although they are
not discussed in detail as Cook does. For example the list of gliders
and the construction of cyclic tag system.

Paper on universality in Rule 110 displayed in January of 1998 in Santa
Fe Institute by Cook, discusses the list of gliders found. Lamentably he
did not leave published in the book of David Griffeath and Cristopher
Moore "New Constructions in Cellular Automata."

-genaro




-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
0
Genaro
6/23/2004 3:15:03 PM
Genaro,

> Nonmemory if in Life exists a pattern that
> never becomes stabilized or extensible gliders.

Since a universal computer has been built in Life, it follows that one can
easily construct a pattern which does not "stablize" in the sense that, for
example, a glider gun or puffer train stabilizes, or even in the sense that
Dean Hickerson's Primes pattern "stablizes".

I think. :)

Cheers, Paul


0
Paul
6/23/2004 3:27:49 PM
"Genaro Juarez Martinez" <genarojm@correo.unam.mx> writes:

>A, B, B-, B^, E, E-, F, G, H gliders and glider Gun. Where B-, B^, E, G
>gliders are extensible. In addition Cook discusses some important points
>that they exist between Life and Rule 110.

First of all I wanted to know the definitions of these gliders: What are A,
B, B-, ...?

I have seen the texts by Harold McIntosh, but they are BIG and difficult to
print without a color printer. Isn't there something more compact?


-- 
Markus Redeker                                              Hamburg, Germany
0
Markus
6/24/2004 9:18:37 AM
"Markus Redeker" <cep@ibp.de> wrote in message

> Isn't there something more compact?

You can download small paper "Introduction to Rule 110" in:

www.rule110.org/donwload

or paper "Productions of Gliders by Collisions in Rule 110" in:


http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/m/Mart=iacute=nez:Genaro_Ju=aacute=rez.html

-genaro



-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
0
Genaro
6/25/2004 4:27:05 PM
"Genaro Juarez Martinez" <genarojm@correo.unam.mx> wrote in message
news:fad404d4a089026123811310114d0ffb.49589@mygate.mailgate.org...
> "Markus Redeker" <cep@ibp.de> wrote in message
>
> > Isn't there something more compact?
>
> You can download small paper "Introduction to Rule 110" in:
>
> www.rule110.org/donwload

This should be www.rule110.org/download

But it did not matter which version I tried. They did not work. I could
download pdf and text files. But none of the zip or other files would
download :-(


>
> or paper "Productions of Gliders by Collisions in Rule 110" in:
>
>
>
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/m/Mart=iacute=nez:
Genaro_Ju=aacute=rez.html
>
> -genaro
>
>
>
> --
> Posted via Mailgate.ORG Server - http://www.Mailgate.ORG


0
David
6/27/2004 2:04:17 AM
"Paul Chapman" <paul@igblan.free-online.co.uk> wrote in message

> Since a universal computer has been built in Life, it follows that one can
> easily construct a pattern which does not "stablize" in the sense that, for
> example, a glider gun or puffer train stabilizes, or even in the sense that
> Dean Hickerson's Primes pattern "stablizes".

How an insoluble problem?, I believe that yes.

Although it thought about one more primitive and less complicated
configuration.

We can think the same about Rule 110. Cook comments that the pair of
propose productions in cyclic tag system (Wolfram's book), is
undecidable.

Then instability forever is not product of a pattern, is product of the
values that generates the machine and that these never get to be
periodic. But they are the values and not them patterns.

-genaro


-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
0
Genaro
6/28/2004 12:58:00 PM
"David Milne" <djomilne@hotmail.com> wrote in message

> 
> This should be www.rule110.org/download
> 
> But it did not matter which version I tried. They did not work. I could
> download pdf and text files. But none of the zip or other files would
> download :-(
> 

The correct leagues are:

paper one.

http://www.rule110.org/amhso/intros.html

http://www.rule110.org/amhso/results/rule110-intro/introRule110.html

paper two.

http://www.rule110.org/amhso/workshops.html

http://www.rule110.org/amhso/results/osxlcau-intro/OSXLCAU21.html

Sorry.

-genaro




-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
0
Genaro
6/28/2004 2:25:37 PM
Reply: