callahan@cs.jhu.edu (Paul Callahan) (01/11/91)
I've been reading about/experimenting with Conway's Life off and on for about
six years or so, but I only recently obtained a copy of the latest version
of life for X-windows. I was impressed with its speed and its unbounded
universe (though I've thought of numerous improvements to the user interface
that would allow more structured design and careful experimentation). In any
case, I've finally gotten to the point where I've come up with some interesting
reactions that I haven't read about or don't remember, in any case (I do not
fool myself by calling them "new").
I've been dealing primarily with rake and spaceship interactions for
ease of experimentation (a rake will invariably escape before being eaten by
even its most hellish progeny, and a spaceship is easy to redraw on the spot).
I do have a goal in mind for all of this, but I may never get around to
completing it, and I'd like to know if its even worthwhile (i.e. has not been
done before). I'm suspecting it has, because it's so natural, but I've never
read anything about it.
Ok. Here's the main question: We all know Life is universal, but has anyone
given a manageable, understandable, _explicit_ construction that proves
universality? The literature I've read (such as _The Recursive Universe_ and
_Winning Ways_) talks about self-replicating machines, which is fascinating in
its own right, but what I have in mind is a bit less ambitious. All I want is
a universal Turing machine with one semi-infinite tape. Less exciting,
perhaps, but at least something for which one could give an explicit
construction that could be easily verified by hand.
I have an overall scheme for this construction that appears plausible. Namely,
we define each tape cell of the Turing maching as a finite automaton using
standard glider gun interactions to compute the logic. This includes "blank"
tape cells, which will contain an automaton in some initial configuration.
Each automaton will be a duplicate of the TM head's automaton, and its finite
memory will consist of the tape cell contents, a flag telling whether the head
is currently at that cell, and if so, the state of the head. The tape head
will "move" when a cell turns off its "head" flag, and emits a small group of
spaceships towards either its left or right neighbor, carrying away the state
of the head.
I think this can be made to work, with such cells being no harder to verify
than any simple digital circuit. The only apparent question is how to get
an infinite sequence of them. The answer, which the reader may have
anticipated, is to use a flotilla of sufficiently thinned-out rakes, headed
towards infinity, which leave a sequence of tape cells in their wake (much
as the breeder leaves a sequence of glider guns).
So, the first sub-question (which I haven't read about, but may have missed),
is whether an arbitrarily thin rake is possible. This turns out to be true.
I don't know if there is another standard method, but the following approach
works: Consider the collision of gliders from three rakes that produces a
medium spaceship in the _same_ direction as the rake. This ship will follow
along to the next collision point, which will not produce a spaceship, but
rather some stable garbage, consisting of a block and a beehive. The block can
be cleaned up with a spaceship, and the beehive can be exploited (using another
rake construction) to produce the same spaceship collision each time the beehive
appears. In general, the thinning process becomes:
Every other collision point forms a beehive
--> Every fourth collision point forms a beehive
--> Every eighth collision point forms a beehive
--> ...
To finish the thin rake, we use a construction that sends off a glider every
time it eats a beehive.
The rakes that produce gliders every 24 turns are sufficiently thin to use as
components of the constructions. (I have a rake in xlife format that thins down
to sixteenths, which I could post/mail if anyone is interested.) The thinness
grows exponentially with the size of the construction, but it is still rather
big and clunky. This brings me to my next question, which I think I can
partially answer.
Suppose we want to create an arbitrary collision of two or more gliders every
time we encounter a single glider. Does there exist, for each such collision,
a flotilla of spaceships to produce it from a single glider (without destroying
the spaceships). I know that a fairly robust set of collisions can be obtained,
using glider/spaceship-spark interactions, based on some experimentation
on my own. Two interesting interactions that both yield the same result (at
different orientations) are the following (where "*" is live, "." is dead).
.****** .*****
*.....* *....*
......* .....*
*....*. *...*.
..**... ..*...
....... ......
**..... ..***.
.**.... ..*...
*...... ...*..
Note that in the first, the glider is going in the same direction (horizontally)
as the spaceship, while in the second, it is going in the opposite direction.
The result of the collision is three blocks, two gliders, and the following
shape (ship?):
**.
*.*
.**
The blocks are easily eliminated by spaceships, and the gliders are useful for
initiating other similar reactions. (Note that if this reaction is attempted
with gliders from a rake, they must be spread fairly thin to give enough space
for the reaction. A 120-step rake, constructed from the 20-step and 24-step
rakes, and turns out to be thin enough).
A sequence of these interactions (with appropriate clean-up) can be made to
yield almost any sufficiently thin pattern of the above shape (and its mirror
image). These can be turned into gliders later on, using the following
interaction:
.*****.
*....*.
.....*.
*...*..
..*....
.......
..**...
..*.*..
...**..
.......
.......
.......
.****..
******.
****.**
....**.
This reaction is (relatively) quick, and requires no cleanup. The advantage to
being able to turn a stable shape into a glider is that timing problems in
glider collisions are easy to resolve. Also, the exact position of a glider
in a collision can be determined as a function of its diagonal path toward
the collision point, and the time at which it is released, so we need only place
the stable seed on the correct diagonal line for the collision. It's true that
these gliders will only go in two of the possible four directions (away from
the ship), but pairs of gliders arranged for kick-back reactions can overcome
this deficiency. At this point, the single problem remaining is how to make
collisions that require densely packed gliders headed in the same direction.
Fortunately, these are not needed for glider-gun construction.
What I would like to see is a set of CAD tools for life. It would be nice to
be able to specify a layout of logic gates, and have a program turn it into
a pattern of glider guns, then turn this into a collision of gliders, and
ultimately construct a flotilla of spaceships to turn a single glider into
this collision. By feeding the flotilla with the output of a thin rake,
it should be possible to construct an unbounded linear array of simple
computing elements. The result would be a universal machine that could be
quite small and easily verified. I would find this to be a more satisfying
proof of universality than the more general schema of self-replication, which
while certainly correct, requires many details left to the imagination.
--
Paul Callahan
callahan@cs.jhu.educallahan@cs.jhu.edu (Paul Callahan) (01/16/91)
In article <callahan.663546920@newton.cs.jhu.edu> I write: >The rakes that produce gliders every 24 turns are sufficiently thin to use as >components of the constructions. (I have a rake in xlife format that thins down >to sixteenths, which I could post/mail if anyone is interested.) The thinness >grows exponentially with the size of the construction [Note: someone asked what a rake is. For those unfamiliar with that terminology, a rake produces gliders (like a glider gun), while moving forward (like a puffer train).] My latter claim seems to have surprised a knowledgable person, so I am posting my rake. The trick is to use small rakes to produce a certain 3-glider collision every time a beehive is encountered. As a result of this, a spaceship is formed when the collision point is empty, and a beehive (and a block, which is removed) is formed when the collision point contains the spaceship created last time. Thus, we have a rake that can store two states (spaceship/no spaceship). Note that in a stationery construction (a glider gun logic circuit, for example), a stationery object, such as a block, is sufficient to store a state, while we need a moving object to store a state in a rake. Using a period-24 rake, we can form the inverse of a thin rake from the thinly spaced beehives, by annihilating the beehives with gliders. Now, by aiming another rake into this inverse stream, using a kick-back reaction, we obtain two streams of gliders, one the inverse, and the other the inverse of the inverse (i.e. a glider stream as thin as the beehive trail). Using two more rakes at positions carefully chosen for kickback and annihilation collisions, we produce a collision of two of the gliders in the spaceship-producing collision. Spurious gliders leaving the collision point can be destroyed with spaceships. For the third glider in the spaceship collision, we use a single period-24 rake. Here, we are fortunate enough that the spark from the spaceship produced by the collision actually destroys the unnecessary gliders. Otherwise, the collision would have been a bit harder to set up. This is much more fun to watch than to think about (for me, anyway) so I'm posting the pattern for those of you who have access to Xlife (available by ftp from expo.lcs.mit.edu, and probably some other places). Please excuse the size of the file (compressing and uuencoding doesn't help enough to be worth it). -- Paul Callahan callahan@cs.jhu.edu ---cut here--- #O callahan "Paul Callahan,319 NEB,338-7052,235-3804,Goodrich"@galileo.cs.jhu.edu Sat Jan 5 23:13:19 1991 1169 87 265 216 265 217 265 218 265 210 265 211 265 212 1217 165 1217 166 1217 167 843 207 1124 112 292 135 699 159 771 183 1096 136 1096 137 1133 143 1157 167 609 16 609 17 609 18 610 17 161 92 161 93 161 94 162 93 465 173 465 174 465 175 466 174 1217 16 1217 17 1217 18 1218 17 769 92 769 93 769 94 770 93 1225 200 1225 192 1225 193 1225 194 1225 198 1225 199 1226 193 1226 199 967 120 359 120 1039 96 431 96 1111 72 503 72 1151 111 440 48 1048 48 296 96 904 96 224 120 976 72 368 72 1120 24 512 24 273 168 273 171 274 168 274 169 274 170 913 266 914 264 914 265 914 266 881 168 881 171 882 168 882 169 882 170 857 168 857 169 858 169 859 168 249 168 249 169 250 169 251 168 448 88 448 89 1056 88 1056 89 984 112 984 113 376 112 376 113 1128 64 1128 65 520 64 520 65 441 48 1049 48 297 96 905 96 833 120 225 120 977 72 369 72 1121 24 513 24 824 202 824 203 752 178 752 179 680 154 680 155 608 130 608 131 564 159 565 159 636 183 637 183 708 207 709 207 780 231 781 231 492 135 493 135 586 88 449 114 449 116 449 117 450 114 450 115 450 116 451 115 865 205 865 206 866 206 866 207 867 207 577 112 577 114 577 115 578 112 578 113 578 114 579 113 753 150 753 151 754 151 753 153 754 152 754 153 755 152 1209 152 1209 154 1210 152 1210 153 1210 154 1211 153 1209 146 1209 148 1209 149 1209 151 1210 146 1210 147 1210 148 1211 147 145 150 145 151 146 151 152 144 145 153 146 152 146 153 147 152 281 124 281 125 622 120 622 121 623 121 624 120 480 200 480 201 480 202 1088 200 1088 201 1088 202 336 152 336 153 336 154 944 152 944 153 944 154 1016 176 1016 177 1016 178 408 176 408 177 408 178 0 123 0 124 0 125 72 99 72 100 72 101 144 75 144 76 144 77 216 51 216 52 216 53 281 182 282 179 282 182 283 180 283 181 283 182 281 186 282 186 282 189 283 186 283 187 283 188 586 78 587 79 585 81 585 85 586 81 586 85 587 80 587 81 587 85 587 86 587 87 889 182 890 179 890 182 891 180 891 181 891 182 889 186 890 186 890 189 891 186 891 187 891 188 640 113 640 114 640 115 712 89 712 90 712 91 784 65 784 66 784 67 1193 16 1194 16 1194 17 585 16 586 16 586 17 1191 190 1191 191 1192 190 1097 118 833 166 834 166 834 167 225 166 226 166 226 167 439 47 440 47 1047 47 1048 47 295 95 296 95 903 95 904 95 151 143 152 143 223 119 224 119 975 71 976 71 367 71 368 71 1119 23 1120 23 511 23 512 23 129 175 130 174 130 175 1049 64 1050 64 1050 65 441 64 442 64 442 65 905 112 906 112 906 113 297 112 298 112 298 113 225 136 226 136 226 137 833 136 834 136 834 137 369 88 370 88 370 89 977 88 978 88 978 89 57 151 58 150 58 151 513 40 514 40 514 41 1121 40 1122 40 1122 41 201 199 202 198 202 199 777 152 778 152 1169 108 1169 109 1169 110 1170 108 1170 109 1170 111 1171 109 1171 110 1171 111 1172 110 569 220 569 221 569 222 570 220 570 221 570 223 571 221 571 222 571 223 572 222 569 228 569 229 569 230 570 227 570 229 570 230 571 227 571 228 571 229 572 228 873 37 873 38 873 39 874 37 874 38 875 38 875 39 876 39 873 45 873 46 873 47 874 40 874 44 874 46 874 47 875 40 875 44 875 45 875 46 876 45 1177 220 1177 221 1177 222 1178 220 1178 221 1178 223 1179 221 1179 222 1179 223 1180 222 1177 228 1177 229 1177 230 1178 227 1178 229 1178 230 1179 227 1179 228 1179 229 1180 228 853 239 854 238 854 239 815 244 816 243 816 244 743 220 744 219 744 220 671 196 672 195 672 196 599 172 600 171 600 172 527 148 528 147 528 148 781 215 782 214 782 215 709 191 710 190 710 191 637 167 638 166 638 167 550 144 550 145 551 145 552 144 817 136 818 137 819 136 819 137 838 48 838 49 839 49 840 48 1093 117 1093 119 1094 116 1094 119 1095 116 1096 116 1096 117 694 96 694 97 695 97 696 96 766 72 766 73 767 73 768 72 209 136 210 137 211 136 211 137 962 158 962 159 963 158 964 159 354 158 354 159 355 158 356 159 1034 182 1034 183 1035 182 1036 183 426 182 426 183 427 182 428 183 1106 206 1106 207 1107 206 1108 207 498 206 498 207 499 206 500 207 516 112 517 113 518 112 518 113 857 267 859 266 860 264 860 265 180 64 180 65 181 65 182 64 108 88 108 89 109 89 110 88 36 112 36 113 37 113 38 112 799 221 799 222 800 220 800 221 655 173 655 174 656 172 656 173 727 197 727 198 728 196 728 197 871 245 871 246 872 244 872 245 1169 179 1169 180 1170 180 1170 181 183 193 183 194 184 192 184 193 111 169 111 170 112 168 112 169 39 145 39 146 40 144 40 145 351 93 351 94 352 94 352 95 959 93 959 94 960 94 960 95 423 69 423 70 424 70 424 71 1031 69 1031 70 1032 70 1032 71 495 45 495 46 496 46 496 47 1103 45 1103 46 1104 46 1104 47 249 205 249 206 249 207 250 205 250 206 250 207 251 205 251 206 252 206 252 207 253 207 1177 98 1177 99 1178 98 1178 99 1178 100 1179 97 1179 99 1179 100 1180 97 1180 98 1180 99 1181 98 1177 91 1177 92 1178 90 1178 91 1178 92 1179 90 1179 91 1179 93 1180 91 1180 92 1180 93 1181 92 1145 155 1145 156 1146 156 1146 157 1191 192 881 119 882 117 882 118 883 118 883 119 887 117 887 118 888 118 888 119 273 119 274 117 274 118 275 118 275 119 279 117 279 118 280 118 280 119 529 101 530 99 530 100 530 101 532 96 1121 126 1122 126 1225 177 1226 178 1227 178 1228 178 1229 176 1229 177 1229 178 1225 171 1225 173 1225 175 1226 170 1227 170 1228 170 1228 173 1228 175 1229 170 1229 171 1229 172 473 115 473 119 474 115 474 119 475 119 476 116 476 119 477 117 477 118 477 119 1081 115 1081 119 1082 115 1082 119 1083 119 1084 116 1084 119 1085 117 1085 118 1085 119 1162 175 1163 173 1163 174 1164 174 1164 175 555 215 556 215 1163 215 1164 215 1113 122 1113 123 1114 127 1115 125 1115 126 1116 126 1116 127 1120 126 1120 127 1138 151 1139 149 1139 150 1140 150 1140 151 449 89 449 90 450 88 1057 89 1057 90 1058 88 985 113 985 114 986 112 377 113 377 114 378 112 1129 65 1129 66 1130 64 521 65 521 66 522 64 163 152 164 152 589 136 590 137 590 138 591 136 591 137 644 142 644 143 645 141 645 142 646 143 716 166 716 167 717 165 717 166 718 167 788 190 788 191 789 189 789 190 790 191 1174 144 1174 145 1175 144 1175 146 1176 144 725 214 726 213 726 214 727 213 727 215 581 166 582 165 582 166 583 165 583 167 653 190 654 189 654 190 655 189 655 191 797 238 798 237 798 238 799 237 799 239 260 48 261 48 618 7 619 6 620 6 621 6 622 6 622 7 618 9 618 11 618 13 619 14 620 14 621 9 621 11 621 14 622 8 622 12 622 13 622 14 922 254 923 253 924 253 925 253 926 253 926 254 926 255 922 256 922 258 922 260 923 261 924 261 925 256 925 258 925 261 926 259 926 260 926 261 1226 7 1227 6 1228 6 1229 6 1230 6 1230 7 1226 9 1226 11 1226 13 1227 14 1228 14 1229 9 1229 11 1229 14 1230 8 1230 12 1230 13 1230 14 1193 142 1194 142 1195 142 1196 142 1197 142 1198 142 1198 143 1137 17 1138 17 1138 18 1139 16 1139 18 529 17 530 17 530 18 531 16 531 18 548 89 549 89 549 90 550 88 550 90 1150 112 1150 113 1151 112 1152 113 734 172 734 173 735 171 735 172 736 173 126 81 126 82 126 83 127 83 128 82 54 105 54 106 54 107 55 107 56 106 662 148 662 149 663 147 663 148 664 149 198 57 198 58 198 59 199 59 200 58 806 196 806 197 807 195 807 196 808 197 577 148 578 149 578 150 579 148 579 149 583 149 583 150 584 148 584 149 502 70 502 71 503 71 504 70 1110 70 1110 71 1111 71 1112 70 430 94 430 95 431 95 432 94 1038 94 1038 95 1039 95 1040 94 358 118 358 119 359 119 360 118 966 118 966 119 967 119 968 118 1065 41 1066 41 1066 42 1067 40 1067 42 457 41 458 41 458 42 459 40 459 42 993 65 994 65 994 66 995 64 995 66 385 65 386 65 386 66 387 64 387 66 921 89 922 89 922 90 923 88 923 90 313 89 314 89 314 90 315 88 315 90 849 113 850 113 850 114 851 112 851 114 241 113 242 113 242 114 243 112 243 114 259 39 260 38 260 39 261 38 261 39 262 39 257 43 259 40 259 46 259 47 260 40 260 46 260 47 261 41 261 45 261 47 262 40 262 41 262 45 262 46 262 47 263 40 263 46 281 162 283 165 283 166 284 165 284 166 284 167 285 160 285 164 285 166 285 167 286 160 286 164 286 165 286 166 287 165 283 158 283 159 284 157 284 158 284 159 285 157 285 158 286 158 286 159 287 159 585 105 587 108 587 109 588 108 588 109 588 110 589 107 589 109 589 110 590 107 590 108 590 109 591 108 587 101 587 102 588 100 588 101 588 102 589 100 589 101 589 103 590 101 590 102 590 103 591 102 889 162 891 165 891 166 892 165 892 166 892 167 893 160 893 164 893 166 893 167 894 160 894 164 894 165 894 166 895 165 891 158 891 159 892 157 892 158 892 159 893 157 893 158 894 158 894 159 895 159 550 143 819 135 1142 218 1142 219 1142 220 1143 218 1144 219 838 47 534 218 534 219 534 220 535 218 536 219 694 95 622 119 766 71 211 135 161 149 161 151 162 148 163 148 164 148 165 148 166 148 166 151 167 148 167 149 167 150 571 56 572 57 573 57 574 57 575 56 575 57 569 53 571 50 571 52 571 54 572 49 573 49 574 49 574 52 574 54 575 49 575 50 575 51 575 55 561 44 562 44 562 47 563 44 563 45 563 46 265 192 265 194 267 195 268 195 270 194 271 192 271 193 875 217 876 218 877 218 878 218 879 216 879 217 879 218 873 214 875 211 875 213 875 215 876 210 877 210 878 210 878 213 878 215 879 210 879 211 879 212 1179 56 1180 57 1181 57 1182 57 1183 56 1183 57 1177 53 1179 50 1179 52 1179 54 1180 49 1181 49 1182 49 1182 52 1182 54 1183 49 1183 50 1183 51 1183 55 1169 44 1170 44 1170 47 1171 44 1171 45 1171 46 873 192 873 194 875 195 876 195 878 194 879 192 879 193 854 122 854 123 854 124 855 122 856 123 1070 194 1070 195 1070 196 1071 194 1072 195 462 194 462 195 462 196 463 194 464 195 998 170 998 171 998 172 999 170 1000 171 390 170 390 171 390 172 391 170 392 171 926 146 926 147 926 148 927 146 928 147 318 146 318 147 318 148 319 146 320 147 513 131 514 130 515 130 515 131 515 132 522 106 523 107 524 105 524 106 524 107 801 222 657 174 585 150 729 198 873 246 564 16 567 16 567 21 567 22 568 22 568 23 1172 16 1175 16 1175 21 1175 22 1176 22 1176 23 554 233 554 234 555 233 555 234 555 235 556 233 556 234 556 235 557 233 557 234 557 235 558 232 558 234 558 235 559 232 559 233 559 234 560 233 1162 233 1162 234 1163 233 1163 234 1163 235 1164 233 1164 234 1164 235 1165 233 1165 234 1165 235 1166 232 1166 234 1166 235 1167 232 1167 233 1167 234 1168 233 205 125 206 125 206 126 207 124 207 126 885 101 886 101 886 102 887 100 887 102 277 101 278 101 278 102 279 100 279 102 957 77 958 77 958 78 959 76 959 78 349 77 350 77 350 78 351 76 351 78 1029 53 1030 53 1030 54 1031 52 1031 54 421 53 422 53 422 54 423 52 423 54 1101 29 1102 29 1102 30 1103 28 1103 30 493 29 494 29 494 30 495 28 495 30 531 33 531 34 532 34 532 35 533 33 1139 33 1139 34 1140 34 1140 35 1141 33 459 57 459 58 460 58 460 59 461 57 1067 57 1067 58 1068 58 1068 59 1069 57 387 81 387 82 388 82 388 83 389 81 995 81 995 82 996 82 996 83 997 81 315 105 315 106 316 106 316 107 317 105 923 105 923 106 924 106 924 107 925 105 3 133 3 134 4 132 4 133 5 134 75 157 75 158 76 156 76 157 77 158 147 181 147 182 148 180 148 181 149 182 219 205 219 206 220 204 220 205 221 206 1124 212 1124 213 1124 214 1125 212 1126 213 516 212 516 213 516 214 517 212 518 213 811 140 811 142 812 143 813 139 813 143 814 143 815 140 815 143 816 141 816 142 816 143 865 255 866 255 868 251 868 253 869 254 870 254 871 251 871 254 872 252 872 253 872 254 980 164 980 165 980 166 981 164 982 165 372 164 372 165 372 166 373 164 374 165 300 140 300 141 300 142 301 140 302 141 304 136 304 137 305 137 305 138 306 136 908 140 908 141 908 142 909 140 910 141 912 136 912 137 913 137 913 138 914 136 444 188 444 189 444 190 445 188 446 189 1052 188 1052 189 1052 190 1053 188 1054 189 785 67 786 66 713 91 714 90 641 115 642 114 206 149 207 148 208 148 208 149 208 150 814 149 815 148 816 148 816 149 816 150 564 6 567 6 568 7 561 10 561 11 561 12 562 10 562 11 562 12 564 8 564 14 565 9 565 13 566 9 566 13 567 9 567 13 568 8 568 9 568 13 568 14 568 15 865 256 865 257 866 256 866 257 868 259 868 261 869 258 870 258 871 258 871 261 872 258 872 259 872 260 1172 6 1175 6 1176 7 1169 10 1169 11 1169 12 1170 10 1170 11 1170 12 1172 8 1172 14 1173 9 1173 13 1174 9 1174 13 1175 9 1175 13 1176 8 1176 9 1176 13 1176 14 1176 15 1180 120 1181 121 1182 121 1183 121 1184 120 1184 121 1177 116 1177 117 1177 118 1178 117 1180 114 1180 116 1180 118 1181 113 1182 113 1183 113 1183 116 1183 118 1184 113 1184 114 1184 115 1184 119 203 140 203 142 204 143 205 139 205 143 206 143 207 140 207 143 208 141 208 142 208 143 507 125 507 127 508 124 509 124 510 124 511 124 511 127 512 124 512 125 512 126 165 187 165 188 166 186 166 187 167 188 477 51 477 52 478 52 478 53 479 51 1085 51 1085 52 1086 52 1086 53 1087 51 21 139 21 140 22 138 22 139 23 140 333 99 333 100 334 100 334 101 335 99 941 99 941 100 942 100 942 101 943 99 869 123 869 124 870 124 870 125 871 123 1013 75 1013 76 1014 76 1014 77 1015 75 405 75 405 76 406 76 406 77 407 75 93 163 93 164 94 162 94 163 95 164 1157 27 1157 28 1158 28 1158 29 1159 27 549 27 549 28 550 28 550 29 551 27 637 168 639 168 709 192 711 192 781 216 783 216 1163 86 1163 87 1164 85 1164 86 1164 87 1165 85 1165 86 1165 87 1166 85 1166 86 1166 87 1167 85 1167 86 1168 86 1168 87 1223 191 1224 191 462 176 463 176 464 176 1211 166 1212 165 1213 165 1214 165 1215 165 1216 165 257 213 257 214 257 215 258 213 258 214 258 215 259 214 261 211 261 213 261 215 262 210 263 210 264 210 264 213 264 215 261 217 262 218 263 218 264 218 218 161 219 160 220 160 220 161 220 162 224 167 826 161 827 160 828 160 828 161 828 162 832 167 1173 184 1173 185 1173 186 1174 184 1175 185 1176 185 1138 132 1138 133 1139 132 1139 134 1140 132 852 178 853 177 853 178 854 177 854 179 244 178 245 177 245 178 246 177 246 179 1120 133 1144 157 279 125 280 123 280 124 1222 200 1223 200 1223 201 1224 200 1224 201 1217 194 1217 198 1218 194 1218 198 1219 195 1219 196 1219 197 1220 196 1222 192 1222 193 1222 199 1223 192 1223 193 1223 199 1224 192 1224 194 1224 198 765 92 765 93 766 91 766 92 766 93 767 91 767 92 767 93 768 91 768 92 768 94 1212 17 1212 18 1213 17 1213 18 1213 19 1214 17 1214 18 1214 19 1215 17 1215 18 1215 19 1216 16 1216 18 1216 19 461 174 461 175 462 174 462 175 463 174 463 175 464 173 464 175 157 92 157 93 158 91 158 92 158 93 159 91 159 92 159 93 160 91 160 92 160 94 604 17 604 18 605 17 605 18 605 19 606 17 606 18 606 19 607 17 607 18 607 19 608 16 608 18 608 19 394 106 394 107 395 107 395 108 396 106 1002 106 1002 107 1003 107 1003 108 1004 106 466 82 466 83 467 83 467 84 468 82 1074 82 1074 83 1075 83 1075 84 1076 82 322 130 322 131 323 131 323 132 324 130 187 131 188 131 188 132 189 130 189 132 1156 138 1156 139 1157 138 1157 140 1158 138 1083 35 1084 35 1084 36 1085 34 1085 36 475 35 476 35 476 36 477 34 477 36 939 83 940 83 940 84 941 82 941 84 331 83 332 83 332 84 333 82 333 84 259 107 260 107 260 108 261 106 261 108 867 107 868 107 868 108 869 106 869 108 403 59 404 59 404 60 405 58 405 60 1011 59 1012 59 1012 60 1013 58 1013 60 876 169 876 171 877 168 878 168 878 172 879 168 879 172 880 168 908 265 909 266 910 266 911 266 912 266 268 169 268 171 269 168 270 168 270 172 271 168 271 172 272 168 834 168 834 172 835 172 836 171 838 173 839 172 840 172 840 173 840 174 226 168 226 172 227 172 228 171 230 173 231 172 232 172 232 173 232 174 1129 107 1130 106 1131 106 1132 106 1132 107 1133 105 1133 106 1134 107 1092 76 1092 77 1093 77 1093 78 1094 76 484 76 484 77 485 77 485 78 486 76 948 124 948 125 949 125 949 126 950 124 340 124 340 125 341 125 341 126 342 124 412 100 412 101 413 101 413 102 414 100 1020 100 1020 101 1021 101 1021 102 1022 100 529 147 529 149 601 171 601 173 673 195 673 197 745 219 745 221 817 243 817 245 583 88 142 152 143 152 144 152 1202 150 1203 148 1204 149 1204 151 1205 150 1207 147 1207 148 1208 147 1208 148 1208 149 1208 151 1203 152 1207 152 1207 153 1208 152 1208 153 750 151 751 150 751 151 752 150 752 151 750 152 751 152 752 152 573 113 573 114 574 113 574 114 574 115 575 113 575 114 575 115 576 113 576 114 576 115 861 206 861 207 862 205 862 206 862 207 863 205 863 206 863 207 864 205 864 206 864 207 446 115 446 116 447 115 447 116 447 117 448 115 448 116 448 117 853 240 855 240 36 111 108 87 180 63 881 184 882 184 883 185 884 184 884 185 885 184 885 185 887 187 887 189 888 186 883 183 884 183 885 183 887 179 887 181 888 182 583 78 577 83 578 83 579 82 579 84 580 82 580 83 580 84 581 82 581 83 581 84 583 80 583 86 584 81 584 85 273 184 274 184 275 185 276 184 276 185 277 184 277 185 279 187 279 189 280 186 275 183 276 183 277 183 279 179 279 181 280 182 604 125 604 126 604 127 605 127 606 126 676 101 676 102 676 103 677 103 678 102 748 77 748 78 748 79 749 79 750 78 820 53 820 54 820 55 821 55 822 54 491 136 492 136 493 137 820 155 821 154 822 154 822 155 822 156 212 155 213 154 214 154 214 155 214 156 1170 225 1171 224 1171 226 1173 224 1173 225 1173 226 1174 225 1176 228 1176 229 1176 221 1176 222 857 49 857 51 858 48 859 48 859 52 860 48 860 52 861 48 862 48 862 51 863 48 863 49 863 50 866 42 867 41 867 43 869 41 869 42 869 43 870 42 872 45 872 46 872 38 872 39 562 225 563 224 563 226 565 224 565 225 565 226 566 225 568 228 568 229 568 221 568 222 1162 104 1164 105 1165 105 1166 109 1166 110 1167 104 1167 108 1167 109 1167 110 1168 108 1168 109 1168 110 779 232 780 232 781 233 707 208 708 208 709 209 635 184 636 184 637 185 563 160 564 160 565 161 817 227 817 228 818 226 818 227 819 228 745 203 745 204 746 202 746 203 747 204 673 179 673 180 674 178 674 179 675 180 601 155 601 156 602 154 602 155 603 156 529 131 529 132 530 130 530 131 531 132 217 53 218 52 730 83 730 84 730 85 731 85 732 84 658 107 658 108 658 109 659 109 660 108 802 59 802 60 802 61 803 61 804 60 509 128 854 264 854 266 856 267 145 77 146 76 73 101 74 100 1 125 2 124 835 233 835 234 836 232 836 233 837 234 691 185 691 186 692 184 692 185 693 186 619 161 619 162 620 160 620 161 621 162 763 209 763 210 764 208 764 209 765 210 1169 93 1170 93 1172 93 1173 93 1174 94 1174 95 1175 95 1169 97 1170 97 1172 97 1173 97 1174 96 247 206 247 207 248 205 248 206 248 207 1156 169 1157 168 1158 168 1158 169 1132 145 1133 144 1134 144 1134 145 1126 139 1127 137 1127 138 1128 138 1128 139 930 130 930 131 931 131 931 132 932 130 775 149 775 151 776 148 1117 116 1118 117 1118 118 1119 116 1119 117 285 131 286 129 286 130 287 130 287 131 890 134 890 135 891 134 892 135 893 131 894 129 894 130 895 130 895 131 1079 116 1079 118 1080 119 1073 136 1073 139 1074 137 1074 138 471 116 471 118 472 119 1217 173 1217 175 1218 173 1218 174 1218 175 1219 173 1219 174 1219 175 1220 173 1220 174 1220 175 1221 172 1221 173 1221 175 1222 173 1222 174 1222 175 1223 174 1217 181 1221 176 518 111 1150 163 1151 161 1151 162 1152 162 1152 163 1092 132 1093 130 1093 132 1093 134 1094 128 1094 134 1094 135 1095 132 1095 133 1095 135 1096 128 1096 133 1096 135 609 129 609 130 610 131 681 153 681 154 682 155 753 177 753 178 754 179 825 201 825 202 826 203 530 95 531 95 534 94 535 95 536 93 536 94 536 95 761 226 762 225 762 226 763 225 763 227 617 178 618 177 618 178 619 177 619 179 545 154 546 153 546 154 547 153 547 155 689 202 690 201 690 202 691 201 691 203 249 49 249 52 250 49 250 50 250 51 1192 143 1222 9 1222 10 1222 11 1223 9 1223 10 1223 11 1224 10 1217 1 1217 4 1218 1 1218 2 1218 3 913 263 918 256 918 257 918 258 919 256 919 257 919 258 920 257 913 249 913 250 913 251 914 250 614 9 614 10 614 11 615 9 615 10 615 11 616 10 609 1 609 4 610 1 610 2 610 3 770 184 770 185 771 184 772 185 162 69 162 70 162 71 163 71 164 70 626 136 626 137 627 136 628 137 18 117 18 118 18 119 19 119 20 118 90 93 90 94 90 95 91 95 92 94 698 160 698 161 699 160 700 161 881 152 881 153 881 155 882 153 882 154 882 155 883 154 885 162 886 161 886 163 888 161 888 162 888 163 577 96 577 99 578 97 578 98 578 99 581 105 582 104 582 106 584 104 584 105 584 106 273 152 273 153 273 155 274 153 274 154 274 155 275 154 277 162 278 161 278 163 280 161 280 162 280 163 249 33 249 34 249 36 250 34 250 35 250 36 251 35 249 40 249 41 249 42 249 44 249 45 249 46 253 43 254 42 254 44 256 42 256 43 256 44 890 136 1165 45 1165 47 1166 44 1167 44 1168 44 1175 52 1175 53 1175 54 1176 52 1176 53 1176 54 1169 59 1169 61 1169 62 1170 59 1170 60 1170 61 1171 60 865 208 866 208 871 213 871 214 871 215 872 213 872 214 872 215 865 223 866 220 866 223 867 221 867 222 867 223 557 45 557 47 558 44 559 44 560 44 567 52 567 53 567 54 568 52 568 53 568 54 561 59 561 61 561 62 562 59 562 60 562 61 563 60 153 144 498 208 1106 208 426 184 1034 184 354 160 962 160 510 118 511 119 512 117 512 118 512 119 1105 45 497 45 1033 69 425 69 961 93 353 93 889 117 281 117 41 146 113 170 185 194 1177 21 569 21 1177 184 1177 185 1178 185 1178 186 1179 184 409 176 410 177 1017 176 1018 177 945 152 946 153 337 152 338 153 1089 200 1090 201 481 200 482 201 1169 117 1169 118 1169 119 1170 118 1170 119 1171 118 1171 119 1172 116 1172 118 1173 116 1173 117 1173 118 1174 116 1174 117 1174 118 1175 116 1175 117 1175 118 1176 115 1176 116 1176 118 1176 119 1169 122 1169 126 1170 126 1171 123 1171 126 1172 124 1172 125 1172 126 1161 0 1161 4 1162 4 1163 1 1163 4 1164 2 1164 3 1164 4 1166 11 1167 11 1168 10 1168 12 857 263 858 263 859 263 860 263 862 256 863 256 864 257 553 0 553 4 554 4 555 1 555 4 556 2 556 3 556 4 558 11 559 11 560 10 560 12 201 200 203 200 1121 39 1123 39 513 39 515 39 57 152 59 152 977 87 979 87 369 87 371 87 833 135 835 135 225 135 227 135 297 111 299 111 905 111 907 111 441 63 443 63 1049 63 1051 63 129 176 131 176 1209 186 1209 190 1210 186 1210 190 1211 190 1212 187 1212 190 1213 188 1213 189 1213 190 249 219 249 223 250 219 250 223 251 217 251 223 252 216 252 220 252 223 253 216 253 221 253 222 253 223 249 211 249 213 249 214 249 215 250 213 250 214 250 215 251 208 251 211 251 213 251 215 252 208 252 212 253 212 1106 123 1106 124 1107 123 1107 124 1111 122 1112 123 1112 124 1209 204 1209 205 1209 206 1210 204 1210 205 1210 206 1211 204 1211 205 1211 206 1212 203 1212 205 1212 206 1213 203 1213 204 1213 205 1214 204 1209 196 1209 197 1209 198 1210 196 1211 199 1213 195 1214 194 1214 198 1215 194 1215 198 513 22 1121 22 369 70 977 70 225 118 833 118 153 142 905 94 297 94 1049 46 441 46 1121 128 1121 131 1121 132 1122 132 1122 133 569 89 569 90 570 88 570 89 570 90 571 88 571 89 571 90 572 88 572 89 572 90 573 88 573 89 573 91 574 89 574 90 574 91 574 95 575 90 575 95 1193 152 1193 157 1193 158 1194 156 1194 157 1194 158 1195 156 1195 157 1195 158 1196 156 1196 157 1196 158 1197 156 1197 157 1197 159 1198 157 1198 158 1198 159 1199 158 1193 150 1194 146 1194 150 1195 146 1197 145 1198 144 265 177 265 178 266 177 266 178 266 179 267 177 267 178 267 179 268 177 268 178 268 179 269 176 269 178 269 179 270 176 270 177 270 178 271 177 266 191 267 191 268 191 269 191 270 191 271 191 569 73 569 75 570 76 571 72 571 76 572 72 572 76 573 76 574 73 574 76 575 74 575 75 575 76 873 177 873 178 874 177 874 178 874 179 875 177 875 178 875 179 876 177 876 178 876 179 877 176 877 178 877 179 878 176 878 177 878 178 879 177 874 191 875 191 876 191 877 191 878 191 879 191 553 216 553 218 554 219 555 219 556 219 557 219 558 216 558 219 559 217 559 218 559 219 553 224 554 225 858 33 858 34 859 32 859 33 859 34 860 32 860 33 860 34 861 32 861 33 861 34 862 32 862 33 862 35 863 33 863 34 863 35 864 34 857 43 858 42 1161 216 1161 218 1162 219 1163 219 1164 219 1165 219 1166 216 1166 219 1167 217 1167 218 1167 219 1161 224 1162 225 291 137 292 136 293 136 293 137 1168 181 1162 102 1163 101 1164 101 1165 101 1166 101 1167 101 1168 96 1168 101 1168 102 1168 103 1164 93 1164 94 1164 95 1165 95 1166 92 1167 88 1168 88 1211 181 1211 182 1212 181 1212 182 1212 183 1213 181 1213 182 1213 183 1214 181 1214 182 1214 183 1215 180 1215 182 1215 183 1216 180 1216 181 1216 182 1211 168 1213 169 1213 173 1214 169 1214 172 1214 173 1214 174 1215 172 1215 173 1216 168 1216 172 1216 173 244 50 244 52 245 49 246 49 246 53 247 49 247 53 248 49 604 2 604 4 605 1 606 1 606 5 607 1 607 5 608 1 603 9 603 10 604 10 604 11 605 9 908 249 908 250 909 248 909 249 909 250 910 248 910 249 910 250 911 248 911 249 911 250 912 248 912 249 912 251 907 257 907 258 908 256 908 257 908 263 909 258 910 262 911 262 1212 2 1212 4 1213 1 1214 1 1214 5 1215 1 1215 5 1216 1 1211 9 1211 10 1212 10 1212 11 1213 9 595 130 596 131 596 132 597 130 597 131 245 34 245 35 246 33 246 34 246 35 247 33 247 34 247 35 247 39 248 33 248 34 248 35 245 42 245 43 245 44 246 45 248 42 248 44 267 161 267 162 267 163 268 163 269 162 269 153 269 154 270 152 270 153 270 154 271 152 271 153 271 154 272 152 272 153 272 154 571 104 571 105 571 106 572 104 573 105 572 96 572 98 573 99 574 99 575 99 576 99 875 161 875 162 875 163 876 163 877 162 877 153 877 154 878 152 878 153 878 154 879 152 879 153 879 154 880 152 880 153 880 154 557 60 557 61 558 60 558 61 558 62 559 60 559 61 559 62 560 60 560 61 560 62 556 52 556 53 557 53 557 54 558 52 559 48 560 48 861 220 861 222 862 223 863 219 863 223 864 219 864 223 860 214 860 215 861 213 861 214 862 215 1165 60 1165 61 1166 60 1166 61 1166 62 1167 60 1167 61 1167 62 1168 60 1168 61 1168 62 1164 52 1164 53 1165 53 1165 54 1166 52 1167 48 1168 48 509 142 510 141 510 142 511 141 511 143 550 1 550 3 551 4 552 0 552 4 547 11 548 11 548 12 549 10 549 12 851 256 852 256 853 257 855 263 856 263 1158 1 1158 3 1159 4 1160 0 1160 4 1155 11 1156 11 1156 12 1157 10 1157 12 1166 123 1166 125 1167 126 1168 122 1168 126 1168 118 553 16 553 17 553 18 554 16 554 17 554 19 555 17 555 18 555 19 556 18 857 249 857 250 857 251 858 248 858 250 858 251 859 248 859 249 859 250 860 249 864 255 1161 16 1161 17 1161 18 1162 16 1162 17 1162 19 1163 17 1163 18 1163 19 1164 18 528 100 1207 187 1207 189 1208 190 248 214 247 220 247 222 248 223 1072 137 1072 138 1208 204 1208 205 1123 110 1124 111 1125 110 1125 111 1128 105 1128 106 1128 107 1192 145 1192 150 1192 151 870 184 871 184 872 185 871 183 872 183 566 83 567 83 567 84 568 82 568 84 262 184 263 184 264 185 263 183 264 183 1160 224 1160 225 1160 226 856 41 856 42 856 43 552 224 552 225 552 226 1097 126 1097 127 1098 120 1098 121 1093 120 1094 120 1096 122 1096 126 1096 127 831 119 832 119 234 45 234 46 234 47 235 47 236 46 142 151 143 150 143 151 144 150 144 151 829 124 830 125 831 123 831 124 831 125 832 120 1193 191 237 211 237 212 238 210 238 211 239 212 768 129 768 130 1146 99 1146 100 1146 101 1147 101 1148 100 1049 136 1049 139 1050 137 1050 138 1195 178 1195 179 1196 179 1196 180 1197 178 585 15 587 15 889 251 889 252 890 250 890 251 891 252 1193 15 1195 15 249 167 553 98 553 99 553 100 554 98 555 99 857 167 538 58 538 59 539 59 539 60 540 58 842 208 842 209 843 208 844 209 1146 58 1146 59 1147 59 1147 60 1148 58 550 17 550 18 551 16 551 17 551 18 552 16 552 17 552 18 1158 17 1158 18 1159 16 1159 17 1159 18 1160 16 1160 17 1160 18 769 128 769 131 770 129 770 130 1081 122 1082 122 1082 124 1083 122 1083 124 1097 131 1097 132 1097 135 1098 133 777 145 777 148 778 145 778 148 779 145 779 148 780 148 780 151 781 148 781 149 781 150 852 255 853 255 854 249 854 250 855 249 855 250 855 251 856 249 856 250 856 251 833 250 834 249 834 250 835 249 835 251 778 143 779 143 1048 137 1048 138 1025 136 1025 139 1026 137 1026 138 417 136 417 139 418 137 418 138 1024 137 1024 138 416 137 416 138 720 129 720 130 1001 136 1001 139 1002 137 1002 138 721 128 721 131 722 129 722 130 1000 137 1000 138 977 136 977 139 978 137 978 138 976 137 976 138 672 129 672 130 953 136 953 139 954 137 954 138 673 128 673 131 674 129 674 130 952 137 952 138 929 136 929 139 930 137 930 138 321 136 321 139 322 137 322 138 928 137 928 138 320 137 320 138 624 129 624 130 17 128 17 131 18 129 18 130 625 128 625 131 626 129 626 130 627 135 16 129 16 130
callahan@cs.jhu.edu (Paul Callahan) (01/18/91)
In article <133@gem.stack.urc.tue.nl> angelo@gem.stack.urc.tue.nl (Angelo Wentzler) writes: >All very fine and very interesting, mr.Callahan, but could you please explain >to me what the following cell-groups are: >Spaceship,spark,glider,rake,block. I guess my first response has to be something like: if you don't know, then you probably won't be able to help me. I know that sounds horrible; it's just that I was writing a long article with limited time, and I didn't feel like spending too much timing giving my own definitions of "well known" patterns. All the patterns I mentioned are defined in either _Winning Ways for All Your Mathematical Plays_ by Berlekamp, Conway, and Guy or _The Recursive Universe_ by William Poundstone. I've seen some variations on names in the files provided with Xlife. To be brief: gliders and blocks are as you supposed (I don't know why you say that my notion of gliders is a larger pattern. Perhaps you could be more specific.) For the other constructions: Spaceships (called "fish" in Xlife files) come in three sizes: small, medium, and large. They are as follows ("sparks" shown capitalized): X..x. ....x (small) x...x .xxxx ..X... X...x. .....x (medium) x....x .xxxxx ..XX... X....x. ......x (large) x.....x .xxxxxx Spaceships move along x or y axes. Sparks have the property that they are produced by a spaceship, but can be removed without destroying it. They are useful for creating effects in which a spaceship passes by a pattern and affects it while escaping unharmed. A rake is an object that moves in the same way as a spaceship, but leaves a trail of gliders in its wake. These trails can be collided to produce stable objects, and other interesting things (such as a variety of "puffer train" effects). My goal was to determine if a set of rakes producing gliders at very wide intervals could be used to directly construct a Turing Machine within the Life universe. I know it _can_ be done, but I was interesting in knowing if an explicit construction had been given. My idea was to duplicate the finite head logic in every tape cell, though I now feel that that is ambitious even for the smallest known Universal Turing Machine (its state set and alphabet both number in the single digits--I don't have the exact numbers at my finger tips). I have another idea for an even simpler universal model of computation, which I will continue in the following posting. -- Paul Callahan callahan@cs.jhu.edu