Index
Rucker, Rudy v. B. (USA, 1946– )
and 2D Turing machines, 930
in Preface, xiii
Rugs
and 2D cellular automata, 929
Rule ()
basic examples of, 854
Rule 0
block emulation of, 702
as having simple behavior, 57
with random initial conditions, 224
Rule 1
as first rule with period 2, 1186
Rule 2
as having simple behavior, 57
Rule 3
half-speed growth in, 57
Rule 4
attractor for, 275
as first rule with period 1, 1186
as having simple behavior, 57
as not universal, 694
with random initial conditions, 225
as statistical test, 597
Rule 7
conserved quantities in, 1022
as having simple behavior, 57
Rule 12
conserved quantities in, 1022
Rule 14
as not universal, 695
Rule 15
block emulation of, 702
as reversible system, 436
Rule 18
nested domains in, 360
repetitive behavior in, 954
spacetime entropy for, 960
temporal sequences in, 960
Rule 22
algebraic form for, 947
attractor network sizes in, 958
block emulations in, 702
density in, 947, 951
evolution of density in, 265
and Game of Life, 965
initial conditions giving randomness in, 951
Lyapunov exponent in, 949
nested pattern from, 58
nesting and randomness in, 263
probabilistic estimates in, 953
with random initial conditions, 227
sensitive dependence in, 251
sources of randomness compared in, 262
spacetime entropy for, 960
Rule 30
adjacent columns in, 1087
algebraic form for, 869
as algorithm from search, 1193
as analogy for quantum measurement, 1063
asymmetry of, 29
attractors in, 280
averaging of pattern from, 353
backtracking tree for, 1089
block frequencies in center column of, 594
blocks in pattern from, 569, 725, 871, 1127
Boolean form for, 616, 869
center column of, 871
compression of pattern from, 562
and computational irreducibility, 745
conserved quantities in, 1022
cryptography with, 603, 1087
density in, 947, 953
diagonal stripes in, 871
directional reversibility in, 1017
directional sampling in, 1087
effect of perturbations in, 325
efficient implementation of center column, 871
emulated by mobile automaton, 664
emulated by substitution system, 666
emulated by symbolic system, 668
emulated by tag system, 667
emulated by Turing machine, 665
emulated by universal CA, 647
emulated by WireWorld, 1117
emulating logical functions, 704
emulating rule for rule 90, 703
encoded as integer equation, 1160
on endpapers of book, 851
as example of art hard to recognize, 874
examples from CellularAutomaton, 868
and extraterrestrial signals, 836
finite-size behavior of, 259, 963, 1088
as generator of hash codes, 1100
history of, 112, 880, 882
initial condition sequence for, 324
intrinsic randomness generation in, 315
inversion of, 1087, 1147
localized structures in, 700
Lyapunov exponent in, 949
mapping for, 870
mixing of initial conditions in, 976
as not showing purpose, 830
and NP completeness, 770, 1090
numbers of cells in picture of, 874
one-sided additivity of, 604
and P completeness, 1149
pattern forced by constraints, 221
patterns on repetitive backgrounds, 700
periods in limited regions, 260, 951
as practical randomness generator, 975
predecessors in, 1087, 1147
probabilistic density estimates in, 953
probabilistic version of, 976
PSPACE completeness of periods in, 1147
purpose of, 1185
and Random, 317
with random initial conditions, 227
and randomness tests, 1085
reactions of scientists to, 872
repetition of columns in, 1087
repetitive behavior in, 267, 954
sensitive dependence in, 251
with shift-register boundary conditions, 1088
sideways evolution of, 604
simple behavior in, 266
from single cell, 27, 59
sizes of BDDs for, 1097
slow growth in, 1118
sources of randomness in, 261
spectrum of, 1082
square root of, 956
state transition graph for, 963
as surjective CA, 959
technological applications of, 843
temporal sequences in, 960
tiling based on, 943
tiling generating pattern of, 221
triangles in pattern of, 871
universality of, 734
Rule 32
entropy in, 958
Rule 37R
as candidate for universality, 692
localized structures in, 440
period of cycles in, 1022
properties of, 1018
radiation from, 456
repetition period for, 457
as violating Second Law, 453
Rule 41
block emulations in, 702
localized structures in, 1118
spectrum of, 1082
Rule 45
with alternating steps reversed, 885
block emulations in, 702
cryptography with, 1087
finite-size behavior of, 963, 1088
in limited regions, 260, 951
localized structures in, 701
Lyapunov exponent in, 949, 1088
nesting in, 701
periods in limited regions, 260
properties of pattern, 885
as randomness generator, 976
repetitive behavior in, 954
from single cell, 59
state transition graph for, 963
as surjective CA, 959
temporal sequences in, 960
Rule 48
block emulation of, 702
Rule 50
block emulation of, 702
generating repetitive pattern, 57
repetitive behavior in, 954
repetitive domains in, 356
Rule 51
block emulation of, 702
as complement rule, 883
as not universal, 694
as reversible system, 435
Rule 54
block emulations in, 702, 1118
as candidate for universality, 696
enumeration of initial conditions for, 697
excluded blocks in, 958
localized structures in, 696
from random initial conditions, 696
repetitive domains in, 356
spacetime entropy for, 960
spectrum of, 1082
Rule 56
conserved quantities in, 1022
Rule 57
as first rule with period 3, 1186
as statistical test, 597
Rule 60
algebraic analysis of, 951
and computational reducibility, 744
and cryptography, 600
as difference table generator, 1091
emulated by TMs, 1119
finite-size behavior of, 963
firing squad problem and, 1035
formula for pattern from, 608
generating function for, 1091
from iterated bitwise operations, 906
with math functions as initial conditions, 1091
methods for generating pattern from, 931
with nested initial conditions, 1091
nested pattern from, 58
pattern forced by constraints, 220
pattern generated by substitution system, 187
periods in limited regions, 951
reachable states in, 963
related to TM 596440, 1120
sequential analog of, 1034
and shift registers, 974
and similarity of rules to rule 110, 872
sounds from, 1080
state transition graph for, 963
as statistical test, 597
temporal sequences in, 960
tiling generating pattern of, 220
see also Additive cellular automata
see also Rule 90
see also Sierpiński pattern
Rule 62
enumerating multiples of 3, 641
as not universal, 695
repetitive domains in, 356
Rule 67R
irregular growth in, 1018
pattern produced by, 438
Rule 73
with alternating steps reversed, 885
as candidate for universality, 699
conserved quantities in, 1022
density oscillations in, 954
information transmission in, 699
localized structures in, 700
properties of pattern, 885
from random initial conditions, 699
from single cell, 59
unbounded growth in, 700, 1118
walls in, 699
Rule 85
as reversible system, 436
Rule 86
sizes of BDDs for, 1097
Rule 90
as additive rule, 952
algebraic analysis of, 951
attractors in, 280
backtracking tree for, 1089
block emulation of, 702
blocking transformations in, 270
Boolean form for, 869
Boolean function for, 616
compression of pattern from, 562
conserved quantities in, 1022
in Cosmati mosaics, 873
density in, 953
directional reversibility in, 1017
effect of perturbations in, 325
emulated by mobile automaton, 664
emulated by rule 45, 701
emulated by rule 126, 269
emulated by substitution system, 666
emulated by symbolic system, 668
emulated by tag system, 667
emulated by Turing machine, 665
emulated by universal CA, 646
emulated by WireWorld, 1117
emulation of by itself, 270
evolution of density in, 265
finite automaton for pattern in, 609
finite-size behavior of, 259, 963
formula for pattern in, 610
fractal dimension of pattern, 870
fractal pattern in, 25, 270
generating function for, 1091
history of in my work, 880
and linear feedback shift registers, 877
mapping for, 870
nested initial conditions for, 956
nested pattern in, 25, 270
network in pattern of, 197
as not universal, 695
as origin of nested patterns, 358
origin of self-similarity in, 270
periods in limited regions, 260
probabilistic density estimates in, 953
probabilistic version of, 976
random initial conditions for, 265
repetitive behavior in, 954
rule for emulated by rule 30, 703
sequential analog of, 1034
sizes of BDDs for, 1097
sources of randomness in, 264
spacetime entropy for, 960
state transition graph for, 963
striped patterns in, 870
substitution system for pattern in, 609
as surjective CA, 959
technological applications of, 843
temporal sequences in, 960
two-dimensional analog of, 1092
vs. Ulam systems, 929
see also Additive cellular automata
see also Rule 60
see also Sierpiński pattern
Rule 90R
nesting in, 1018
pattern produced by, 438
and reversible behavior, 452
and spacetime symmetry, 485
Rule 94
block emulations in, 702
compression of pattern from, 562
and difficulty in deducing rules from behavior, 467
as generating even numbers, 641
nesting and randomness in, 951
Rule 102
and rule 110, 872
Rule 103
half-speed growth in, 57
as rule with simple behavior, 57
Rule 105
Boolean formula for iterations of, 1096
nested pattern in, 58
Rule 107
Nand expression for, 1097
Rule 108
attractors in, 278, 958
as not universal, 694
with random initial conditions, 225
Rule 109
generating repetitive pattern, 57
Rule 110
algebraic form for, 869
annihilation of structures in, 359
approximate nesting in, 359
attractors in, 279, 958
axiom system for, 1168
background in, 291, 964
block emulations in, 702
Boolean form for, 869
character of universality proof of, 1156
collisions of structures in, 294
and computational irreducibility, 746
conserved quantities in, 964, 1022
constructions in, 681
in cover image, 851
density with random initial conditions, 947
domains in, 356
emulated by combinators, 713
emulated by integer equation, 785, 1161
emulated by TM, 707, 1119
emulated by WireWorld, 1117
and extraterrestrials, 839
finite-size behavior of, 963
in limited regions, 260, 1088
mapping for, 870
my first work on, 881
and P completeness, 1149
periods in limited regions, 260
persistent structures in, 292, 964
phases of background in, 990
and Principle of Computational Equivalence, 718
from random initial conditions, 229, 290, 677
reactions of scientists to, 872
regular expression for, 957
repetitive behavior in, 954
as showing purpose, 830
and similarity of rules to rule 60, 872
from single cell, 32–39
sizes of BDDs for, 1097
spectrum of, 1082
state transition graph for, 963
and technology, 841
typical behavior of, 676
universality of, 675–691
and word problem for groups, 1141
Rule 121
Nand expression for, 1097
Rule 122R
different initial conditions in, 451
as example of thermodynamic behavior, 442
Rule 123
as rule with simple behavior, 57
Rule 124
as variant of rule 110, 693
Rule 126
algebraic form for, 947
attractors in, 279, 958
blocks in evolution of, 278
density evolution in, 953
density with random initial conditions, 947
emulating rule 90, 269
entropy of, 958
excluded blocks in, 958
Lyapunov exponent in, 949
with random initial conditions, 226
regular expression for, 957
repetitive behavior in, 267
sensitive dependence in, 251
spectrum of, 1082
Rule 127
as rule with simple behavior, 57
Rule 128
attractors in, 277, 958
block emulation of, 702
as rule with simple behavior, 57
Rule 129
enumerating powers of 2, 641
nested pattern in, 58
Rule 132
attractors in, 278, 958
computing parity with, 638
finite-size behavior of, 962
and regular languages, 1109
state transition graph for, 962
Rule 136
block emulation of, 702
Rule 137
as variant of rule 110, 693
Rule 144
computations done by, 1109
Rule 146
block emulation of, 702
invariant states in, 348
Rule 148
block emulation of, 702
Rule 150
as additive rule, 952
blocking transformations in, 271
conserved quantities in, 1023
density with random initial conditions, 947
finite automaton for pattern in, 609
formula for iterations of, 1096
formula for pattern in, 610
generating function for, 1091
local conservation laws in, 1023
nested pattern in, 58, 271
as not universal, 695
as origin of nested patterns, 358
origin of nesting in, 271
properties of pattern from, 885
with random initial conditions, 227
represented by Nands, 1096
as rule for code 976 interface, 980
spacetime entropy for, 960
substitution system for pattern in, 609
as surjective CA, 959
two-dimensional analog of, 1092
see also Additive cellular automata
Rule 150R
fractal dimension of, 1018
generating function for, 1018
nested pattern in, 439
and spacetime symmetry, 485
Rule 152
computations done by, 1109
Rule 154R
pattern produced by, 439
properties of, 1018
Rule 160
attractors in, 278, 958
with random initial conditions, 224
Rule 170
block emulation of, 702
conservation of density in, 458
finite-size behavior of, 963
local conservation laws in, 1023
mapping for, 870
as reversible system, 436
as shift rule, 883
state transition graph for, 963
see also Shift map
Rule 172
conserved quantities in, 1022
Rule 173R
nesting in, 1018
pattern produced by, 438
Rule 176
block emulation of, 702
Rule 182
algebraic form for, 947
density with random initial conditions, 947
with random initial conditions, 227
Rule 184
attractors in, 278, 958
and block emulations, 702
blocking transformations in, 271
computation done by, 1109
conservation of density in, 458
and context-free languages, 1109
local conservation laws in, 1023
nested initial conditions for, 272
nested patterns in, 272, 359
and nesting in phase transitions, 989
as not universal, 695
phase transition in, 338
and sandpile models, 990
as statistical test, 597
Rule 188
and computational reducibility, 744
Rule 190
enumerating multiples of 4, 641
Rule 192
block emulation of, 702
Rule 193
as variant of rule 110, 693
Rule 204
block emulation of, 702
conservation of density in, 458
as identity rule, 883
as reversible system, 436
Rule 214R
randomness in, 439
symmetry between past and future in, 437
Rule 218
different behavior in, 952
with random initial conditions, 225
Rule 225
as analog of fluid turbulence, 382
nested pattern in, 58
nesting and randomness in, 951
properties of pattern from, 885
Rule 232
with random initial conditions, 225
spectrum of, 1082
Rule 236
density evolution in, 953
Rule 238
block emulation of, 702
Rule 240
block emulation of, 702
as reversible system, 436
as shift rule, 883
Rule 250
algebraic form for, 869
backtracking tree for, 1089
Boolean form for, 869
mapping for, 870
as not universal, 694
Or additivity of, 952
as producing checkerboard, 25
with random initial conditions, 224
Rule 254
algebraic form for, 869
backtracking tree for, 1089
as basic example of CA, 24
Boolean form for, 616, 869
emulated by universal CA, 645
finite-size behavior of, 962
as having a purpose, 831
invariant states in, 348
as irreversible system, 435
mapping for, 870
Nand expression for, 1097
with random initial conditions, 224
sizes of BDDs for, 1097
state transition graph for, 962
Rule 255
attractor for, 275
as rule with simple behavior, 57
Rule equivalences, 883
Rule numbers
for general cellular automata, 927
for operator systems, 1170
for Turing machines, 888
Ruler-and-compass constructions, 1129, 1137
Rules
and axioms, 1150
for cellular automata, 24
elementary
see Elementary cellular automata
growth totalistic, 928
history of concept of, 874
in Mathematica, 627, 854, 1103
parameter space of, 948
totalistic, 60
see also Programs
Rules of inference
and structure of proofs, 1155
Run-length encoding, 560
in faxes, 1070
implementation of, 1070
iterated, 905
as number representation, 914
two-dimensional, 1072
Run length test, 1085
Run lengths
patterns from, 1091
and Ramsey theory, 1068
and statistical analysis, 595
Run tests
for linear congruential generators, 974
Running times
of FactorInteger, 1090
of Turing machines, 761
see also Computational complexity theory
Runoff
and landscape structure, 1001
Runs up test, 1085
Russell, Bertrand A. W. (England, 1872–1970)
and axioms for logic, 1151
and character of math, 1176
and foundations of math, 1149
and paradoxes in set theory, 1154
and Principia Mathematica, 894
and theory of types, 898
Russell, John Scott (Scotland, 1808–1882)
and solitons, 899
Russell's paradox
in set theory, 1154
Russian peasant method
for computing powers, 1093
Russian work on cellular automata, 877
Rutherford, Ernest (New Zealand/Canada, 1871–1937)
and atomic nuclei, 1044
Rytin, Maxim (Russia, 1975– )
and concatenation sequences, 913