105:
25:
122:
314:. Wolfram Research claimed that this presentation violated Cook's nondisclosure agreement with his employer, and obtained a court order excluding Cook's paper from the published conference proceedings. The existence of Cook's proof nevertheless became known. Interest in his proof stemmed not so much from its result as from its methods, specifically from the technical details of its construction. The character of Cook's proof differs considerably from the discussion of Rule 110 in
454:
If, on the other hand, the symbol in the string was a 1, the rule separator changes into a new structure which admits the incoming production rule. Although the new structure is again destroyed when it encounters the next rule separator, it first allows a series of structures to pass through towards
434:
on which the cyclic tag system is operating, and the first such symbol is destroyed upon consideration of every production rule. When this leading symbol is a 1, new symbols are added to the end of the string; when it is 0, no new symbols are added. The mechanism for achieving this is described
421:
The initial spacing between these components is of utmost importance. In order for the cellular automaton to implement the cyclic tag system, the automaton's initial conditions must be carefully selected so that the various localized structures contained therein interact in a highly ordered way.
450:
When a left-moving rule separator encounters a stationary symbol in the cyclic tag system's data string, it causes the first symbol it encounters to be destroyed. However, its subsequent behavior varies depending on whether the symbol encoded by the string had been a 0 or a 1. If a 0, the rule
438:
Entering from the right are a series of left-moving structures of the type shown above, separated by varying amounts of horizontal space. Large numbers of these structures are combined with different spacings to represent 0s and 1s in the cyclic tag system's production rules. Because the tag
345:
Three localized patterns are of particular importance in the Rule 110 universal machine. They are shown in the image below, surrounded by the repeating background pattern. The leftmost structure shifts to the right two cells and repeats every three generations. It comprises the sequence
439:
system's production rules are known at the time of creation of the program, and infinitely repeating, the patterns of 0s and 1s at the initial condition can be represented by an infinitely repeating string. Each production rule is separated from the next by another structure known as a
252:, Rule 110 is the only one for which Turing completeness has been directly proven, although proofs for several similar rules follow as simple corollaries (e.g. Rule 124, which is the horizontal reflection of Rule 110). Rule 110 is arguably the simplest known Turing complete system.
337:
The function of the universal machine in Rule 110 requires a finite number of localized patterns to be embedded within an infinitely repeating background pattern. The background pattern is fourteen cells wide and repeats itself exactly every seven iterations. The pattern is
459:
in the right-moving pattern shown above. The clock pulses transform incoming left-moving 1 symbols from a production rule into stationary 1 symbols of the data string, and incoming 0 symbols from a production rule into stationary 0 symbols of the data string.
117:
In an elementary cellular automaton, a one-dimensional pattern of 0s and 1s evolves according to a simple set of rules. Whether a point in the pattern will be 0 or 1 in the new generation depends on its current value, as well as on those of its two neighbors.
429:
in the cyclic tag system is represented by a series of stationary repeating structures of the type shown above. Varying amounts of horizontal space between these structures serve to differentiate 1 symbols from 0 symbols. These symbols represent the
329:, self-perpetuating localized patterns, that could be constructed on an infinitely repeating pattern in a Rule 110 universe. He then devised a way for combinations of these structures to interact in a manner that could be exploited for computation.
455:
the left. These structures are then made to append themselves to the end of the cyclic tag system's data string. This final transformation is accomplished by means of a series of infinitely repeating, right-moving
871:
MartĂnez, Genaro J.; Adamatzky, A.; Chen, Fangyue; Chua, Leon (2012). "On
Soliton Collisions between Localizations in Complex Elementary Cellular Automata: Rules 54 and 110 and Beyond".
377:
Below is an image showing the first two structures passing through each other without interacting other than by translation (left), and interacting to form the third structure (right).
382:
358:
470:
786:
Neary, Turlough; Woods, Damien (2006). "P-completeness of cellular automaton Rule 110". In
Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.).
451:
separator changes into a new structure which blocks the incoming production rule. This new structure is destroyed when it encounters the next rule separator.
321:
Cook proved that Rule 110 was universal (or Turing complete) by showing it was possible to use the rule to emulate another computational model, the
353:
In the figures, time elapses from top to bottom: the top line represents the initial state, and each following line the state at the next time.
989:; Mora, Juan C.S.T.; Vergara, Sergio V.C. (2008). "Determining a regular language by glider-based structures called phases fi_1 in Rule 110".
911:
249:
788:
Automata, Languages and
Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I
104:
267:
behavior", which is neither completely stable nor completely chaotic. Localized structures appear and interact in complex ways.
1111:
293:. Neary and Woods (2006) presented a different construction that replaces 2-tag systems with clockwise Turing machines and has
1096:
194:
The name "Rule 110" derives from the fact that this rule can be summarized in the binary sequence 01101110; interpreted as a
836:
Cook, Matthew (2008). "A Concrete View of Rule 110 Computation". In Neary, T.; Woods, D.; Seda, A. K.; Murphy, N. (eds.).
308:
presented his proof of the universality of Rule 110 at a Santa Fe
Institute conference, held before the publication of
1186:
1025:
817:
68:
46:
966:
39:
387:
There are numerous other spaceships in Rule 110, but they do not feature as prominently in the universality proof.
1049:
367:
surrounded by the background pattern given above, as well as twenty-nine different evolutions of this sequence.
363:
The center structure shifts left eight cells and repeats every thirty generations. It comprises the sequence
101:. This implies that, in principle, any calculation or computer program can be simulated using this automaton.
90:
593:
370:
The rightmost structure remains stationary and repeats every seven generations. It comprises the sequence
125:
An animation of the way the rules of a 1D cellular automaton determine the next generation, using Rule 110.
374:
surrounded by the background pattern given above, as well as five different evolutions of this sequence.
93:
with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to
350:
surrounded by the background pattern given above, as well as two different evolutions of this sequence.
264:
1123:
475:
The figure above is the schematic diagram of the reconstruction of a cyclic tag system in Rule 110.
256:
108:
An example run of the rule 110 cellular automaton over 256 iterations, starting from a single cell.
94:
33:
967:"Reproducing the cyclic tag systems developed by Matthew Cook with Rule 110 using the phases fi_1"
286:
1138:
50:
1191:
910:
MartĂnez, Genaro J.; Adamatzky, A.; Stephens, Christopher R.; Hoeflich, Alejandro F. (2011).
310:
294:
232:
219:
654:
Martinez, Genaro J.; Seck Tuoh Mora, Juan; Chapa, Sergio; Lemaitre, Christian (April 2019).
1008:
933:
748:
290:
552:
447:), which moves towards the left at the same rate as the encoding of the production rules.
278:
274:
8:
215:
98:
1166:
1012:
937:
752:
1134:
1119:
1107:
1073:
1069:
1045:
1021:
998:
986:
962:
949:
923:
898:
880:
859:
841:
840:. Electronic Proceedings in Theoretical Computer Science. Vol. 1. pp. 31–55.
774:
685:
667:
227:
273:
proved Rule 110 capable of supporting universal computation by successively emulating
1092:
894:
813:
766:
689:
655:
322:
902:
863:
778:
121:
97:. Like Life, Rule 110 with a particular repeating background pattern is known to be
1084:
953:
941:
890:
851:
791:
756:
739:
677:
237:
681:
214:
published a proof that Rule 110 with a particular repeating background pattern is
1088:
803:
790:. Lecture Notes in Computer Science. Vol. 4051. Springer. pp. 132–143.
528:
524:
521:
260:
223:
714:
596:(sometimes cited as "Wolfram Research Inc. v. Matthew Cook. 8/31 CV00-9357 CBM")
326:
282:
1171:
945:
1180:
195:
1156:
770:
305:
270:
236:. This resulted in a legal affair based on a non-disclosure agreement with
211:
199:
240:. Wolfram Research blocked publication of Cook's proof for several years.
795:
1083:. Lecture Notes in Computer Science. Vol. 2801. pp. 175–182.
517:
1161:
855:
807:
381:
1003:
846:
761:
734:
357:
1172:
Marble-based mechanical implementation of a 4-bit Rule 110 computer
672:
660:
International
Journal of Parallel, Emergent and Distributed Systems
653:
557:. University of California Television (UCTV). Event occurs at 9:51
520:, written in conventional decimal notation, and thus is pronounced
494:
928:
885:
909:
489:
484:
318:. Cook has since written a paper setting out his complete proof.
960:
325:, which is known to be universal. He first isolated a number of
469:
1112:"ATLAS: Collisions of gliders as phases of ether in rule 110"
656:"Brief notes and history computing in Mexico during 50 years"
289:
overhead because the Turing machine's tape is encoded with a
1026:"Rule 110 objects and other constructions based-collisions"
1019:
984:
395:
The cyclic tag system machinery has three main components:
870:
226:
had conjectured in 1985. Cook presented his proof at the
198:, this corresponds to the decimal value 110. This is the
965:; Mora, Juan C.S.T.; Vergara, Sergio V.C. (2003–2008).
129:
The Rule 110 automaton has the following set of rules:
635:
390:
230:
conference CA98 before publication of
Wolfram's book
1067:
1043:
1124:"Rule 110 as it relates to the presence of gliders"
1024:; Mora, Juan C.S.T.; Vergara, Sergio V.C. (2007).
577:
575:
573:
571:
1074:"Production of Gliders by Collisions in Rule 110"
1178:
1162:Rule 110 in Wolfram's atlas of cellular automata
1105:
599:
568:
250:88 possible unique elementary cellular automata
715:"Universality in Elementary Cellular Automata"
594:Wolfram Research Inc v. Cook (2:00-cv-09357)
463:
300:
417:which start on the left and move rightward.
410:which start on the right and move leftward;
785:
641:
1002:
927:
884:
845:
760:
671:
406:An infinitely repeating series of finite
332:
243:
69:Learn how and when to remove this message
1133:
1118:
120:
103:
32:This article includes a list of general
802:
629:
617:
554:A New Kind of Science - Stephen Wolfram
1179:
732:
605:
835:
712:
581:
18:
1057:Int. J. Of Unconventional Computing
912:"Cellular automaton supercolliders"
531:pronounces the name "rule one-ten".
13:
828:
413:An infinitely repeating series of
391:Constructing the cyclic tag system
38:it lacks sufficient corresponding
14:
1203:
1157:Rule 110 — from Wolfram MathWorld
1150:
838:The Complexity of Simple Programs
895:10.25088/ComplexSystems.21.2.117
468:
380:
356:
23:
735:"What kind of science is this?"
705:
647:
623:
611:
587:
544:
507:
1:
682:10.1080/17445760.2019.1608990
538:
112:
91:elementary cellular automaton
16:Elementary cellular automaton
1089:10.1007/978-3-540-39432-7_19
1072:; Mora, Juan C.S.T. (2003).
1048:; Mora, Juan C.S.T. (2006).
1033:Journal of Cellular Automata
991:Journal of Cellular Automata
974:Journal of Cellular Automata
7:
1081:Advances in Artificial Life
478:
83:Rule 110 cellular automaton
10:
1208:
205:
164:New state for center cell
946:10.1142/S0129183111016348
527:ordinarily. For example,
464:Cyclic tag system working
301:The proof of universality
1187:Cellular automaton rules
1139:"Rule 110 Is Universal!"
642:Neary & Woods (2006)
551:Stephen Wolfram (2003).
500:
620:, pp. 169, 675–691
53:more precise citations.
713:Cook, Matthew (2004).
333:Spaceships in Rule 110
285:. The final stage has
244:Interesting properties
126:
109:
1106:MartĂnez, Genaro J.;
1068:MartĂnez, Genaro J.;
1050:"Gliders in Rule 110"
1044:MartĂnez, Genaro J.;
1020:MartĂnez, Genaro J.;
985:MartĂnez, Genaro J.;
961:MartĂnez, Genaro J.;
809:A New Kind of Science
316:A New Kind of Science
311:A New Kind of Science
233:A New Kind of Science
220:universal computation
124:
107:
95:Conway's Game of Life
85:(often called simply
916:Int. J. Mod. Phys. C
403:which is stationary;
291:unary numeral system
1167:Rule 110 repository
1135:McIntosh, Harold V.
1120:McIntosh, Harold V.
1108:McIntosh, Harold V.
1070:McIntosh, Harold V.
1046:McIntosh, Harold V.
1022:McIntosh, Harold V.
1013:2007arXiv0706.3348J
987:McIntosh, Harold V.
963:McIntosh, Harold V.
938:2011IJMPC..22..419M
796:10.1007/11786986_13
753:2002Natur.417..216G
733:Giles, Jim (2002).
255:Rule 110, like the
218:, i.e., capable of
275:cyclic tag systems
228:Santa Fe Institute
127:
110:
1098:978-3-540-20057-4
856:10.4204/EPTCS.1.4
812:. Wolfram Media.
747:(6886): 216–218.
522:as one pronounces
323:cyclic tag system
192:
191:
79:
78:
71:
1199:
1145:
1143:
1130:
1128:
1115:
1102:
1078:
1064:
1054:
1040:
1030:
1016:
1006:
981:
971:
957:
931:
906:
888:
867:
849:
823:
804:Wolfram, Stephen
799:
782:
764:
729:
719:
700:
699:
697:
696:
675:
651:
645:
639:
633:
627:
621:
615:
609:
603:
597:
591:
585:
579:
566:
565:
563:
562:
548:
532:
511:
472:
408:production rules
384:
360:
287:exponential time
259:, exhibits what
238:Wolfram Research
135:Current pattern
132:
131:
74:
67:
63:
60:
54:
49:this article by
40:inline citations
27:
26:
19:
1207:
1206:
1202:
1201:
1200:
1198:
1197:
1196:
1177:
1176:
1153:
1148:
1141:
1126:
1099:
1076:
1052:
1028:
980:(2–3): 121–161.
969:
873:Complex Systems
831:
829:Further reading
826:
820:
762:10.1038/417216a
722:Complex Systems
717:
708:
703:
694:
692:
652:
648:
640:
636:
628:
624:
616:
612:
604:
600:
592:
588:
580:
569:
560:
558:
550:
549:
545:
541:
536:
535:
529:Stephen Wolfram
525:nominal numbers
512:
508:
503:
481:
466:
445:block separator
393:
335:
303:
283:Turing machines
246:
224:Stephen Wolfram
216:Turing complete
208:
202:naming scheme.
115:
99:Turing complete
75:
64:
58:
55:
45:Please help to
44:
28:
24:
17:
12:
11:
5:
1205:
1195:
1194:
1189:
1175:
1174:
1169:
1164:
1159:
1152:
1151:External links
1149:
1147:
1146:
1131:
1116:
1103:
1097:
1065:
1041:
1017:
997:(3): 231–270.
982:
958:
922:(4): 419–439.
907:
879:(2): 117–142.
868:
832:
830:
827:
825:
824:
818:
800:
783:
730:
709:
707:
704:
702:
701:
666:(2): 185–192.
646:
634:
630:Wolfram (2002)
622:
618:Wolfram (2002)
610:
598:
586:
567:
542:
540:
537:
534:
533:
505:
504:
502:
499:
498:
497:
492:
487:
480:
477:
465:
462:
441:rule separator
419:
418:
411:
404:
392:
389:
340:00010011011111
334:
331:
302:
299:
245:
242:
207:
204:
190:
189:
186:
183:
180:
177:
174:
171:
168:
165:
161:
160:
157:
154:
151:
148:
145:
142:
139:
136:
114:
111:
77:
76:
31:
29:
22:
15:
9:
6:
4:
3:
2:
1204:
1193:
1190:
1188:
1185:
1184:
1182:
1173:
1170:
1168:
1165:
1163:
1160:
1158:
1155:
1154:
1140:
1136:
1132:
1125:
1121:
1117:
1113:
1109:
1104:
1100:
1094:
1090:
1086:
1082:
1075:
1071:
1066:
1062:
1058:
1051:
1047:
1042:
1039:(3): 219–242.
1038:
1034:
1027:
1023:
1018:
1014:
1010:
1005:
1000:
996:
992:
988:
983:
979:
975:
968:
964:
959:
955:
951:
947:
943:
939:
935:
930:
925:
921:
917:
913:
908:
904:
900:
896:
892:
887:
882:
878:
874:
869:
865:
861:
857:
853:
848:
843:
839:
834:
833:
821:
819:1-57955-008-8
815:
811:
810:
805:
801:
797:
793:
789:
784:
780:
776:
772:
768:
763:
758:
754:
750:
746:
742:
741:
736:
731:
727:
723:
716:
711:
710:
691:
687:
683:
679:
674:
669:
665:
661:
657:
650:
643:
638:
632:, p. 229
631:
626:
619:
614:
607:
602:
595:
590:
583:
578:
576:
574:
572:
556:
555:
547:
543:
530:
526:
523:
519:
515:
510:
506:
496:
493:
491:
488:
486:
483:
482:
476:
473:
471:
461:
458:
452:
448:
446:
442:
436:
433:
428:
423:
416:
412:
409:
405:
402:
398:
397:
396:
388:
385:
383:
378:
375:
373:
368:
366:
361:
359:
354:
351:
349:
343:
341:
330:
328:
324:
319:
317:
313:
312:
307:
298:
296:
292:
288:
284:
280:
276:
272:
268:
266:
262:
258:
253:
251:
241:
239:
235:
234:
229:
225:
221:
217:
213:
203:
201:
197:
196:binary number
187:
184:
181:
178:
175:
172:
169:
166:
163:
162:
158:
155:
152:
149:
146:
143:
140:
137:
134:
133:
130:
123:
119:
106:
102:
100:
96:
92:
88:
84:
73:
70:
62:
59:November 2012
52:
48:
42:
41:
35:
30:
21:
20:
1192:Wolfram code
1080:
1060:
1056:
1036:
1032:
994:
990:
977:
973:
919:
915:
876:
872:
837:
808:
787:
744:
738:
725:
721:
693:. Retrieved
663:
659:
649:
637:
625:
613:
606:Giles (2002)
601:
589:
559:. Retrieved
553:
546:
513:
509:
474:
467:
457:clock pulses
456:
453:
449:
444:
440:
437:
431:
426:
424:
420:
415:clock pulses
414:
407:
400:
394:
386:
379:
376:
371:
369:
364:
362:
355:
352:
347:
344:
339:
336:
320:
315:
309:
306:Matthew Cook
304:
271:Matthew Cook
269:
257:Game of Life
254:
247:
231:
212:Matthew Cook
209:
200:Wolfram code
193:
128:
116:
86:
82:
80:
65:
56:
37:
1004:0706.3348v1
847:0906.3248v1
706:Works cited
582:Cook (2004)
427:data string
401:data string
281:, and then
51:introducing
1181:Categories
695:2020-04-15
673:1905.07527
561:2023-06-19
539:References
518:number 110
348:0001110111
327:spaceships
297:overhead.
295:polynomial
279:tag system
248:Among the
113:Definition
34:references
929:1105.4332
886:1301.6258
690:150262966
277:, then 2-
210:In 2004,
1137:(2002).
1122:(1999).
1110:(2001).
903:10165042
864:10266058
806:(2002).
779:10636328
771:12015565
495:Rule 184
479:See also
222:, which
89:) is an
87:Rule 110
1063:: 1–49.
1009:Bibcode
954:7508070
934:Bibcode
749:Bibcode
728:: 1–40.
516:is the
490:Rule 90
485:Rule 30
435:below.
365:1001111
265:Class 4
263:calls "
261:Wolfram
206:History
47:improve
1095:
952:
901:
862:
816:
777:
769:
740:Nature
688:
36:, but
1142:(PDF)
1127:(PDF)
1077:(PDF)
1053:(PDF)
1029:(PDF)
999:arXiv
970:(PDF)
950:S2CID
924:arXiv
899:S2CID
881:arXiv
860:S2CID
842:arXiv
775:S2CID
718:(PDF)
686:S2CID
668:arXiv
501:Notes
1093:ISBN
814:ISBN
767:PMID
443:(or
432:word
425:The
159:000
156:001
153:010
150:011
147:100
144:101
141:110
138:111
81:The
1085:doi
942:doi
891:doi
852:doi
792:doi
757:doi
745:417
678:doi
514:110
372:111
1183::
1091:.
1079:.
1059:.
1055:.
1035:.
1031:.
1007:.
993:.
976:.
972:.
948:.
940:.
932:.
920:22
918:.
914:.
897:.
889:.
877:21
875:.
858:.
850:.
773:.
765:.
755:.
743:.
737:.
726:15
724:.
720:.
684:.
676:.
664:35
662:.
658:.
570:^
399:A
342:.
188:0
185:1
182:1
179:1
176:0
173:1
170:1
167:0
1144:.
1129:.
1114:.
1101:.
1087::
1061:2
1037:2
1015:.
1011::
1001::
995:3
978:6
956:.
944::
936::
926::
905:.
893::
883::
866:.
854::
844::
822:.
798:.
794::
781:.
759::
751::
698:.
680::
670::
644:.
608:.
584:.
564:.
72:)
66:(
61:)
57:(
43:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
