# 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 Sierpinski 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 Sierpinski 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