# Index

Shadowing property of chaotic systems, 920

Shafarevich-Tate group, 1164

Shaking

of granular materials, 986

as source of randomness, 968, 969

Shallit, Jeffrey O. (USA/Canada, 1957– )

and continued fractions, 914

Shannon, Claude E. (USA, 1916–2001)

and analog computers, 1129

and Boolean algebra, 1097

and coding theory, 1069

and cryptography, 1086

and information theory, 1071, 1181

and statistical mechanics, 1020

and Turing machines, 1119

Shannon-Fano codes, 1069

Shannon information

for cellular automata, 959

and evolution of languages, 1181

and thermodynamics, 1020

see also Measure entropy

see also Redundancy

Shape space

of antibodies, 1184

Shapes

from aggregation systems, 979

of animals, 421

in complex maps, 933

and human experience, 1177

of leaves, 401-407, 1005

limiting in cellular automata, 929

parametrization of, 980

possible from growth, 1010

smooth from 2D CAs, 980

variation in 2D CAs, 179

Shared subexpressions

in equation solutions, 945

in multilevel logic, 1096

and networks, 1040

and speedups, 1094

Sharks

patterns in teeth of, 1007

Sharpening

and image processing, 1077

Shattering of solids, 995

Shaw, Robert S. (USA, 1946– )

and chaos theory, 971

in Preface, xiii

Sheep

fortune-telling from, 968

Sheffer, Henry M. (USA, 1883–1964)

and axioms for logic, 1151, 1175

and Nand, 1173

Sheffer axioms

and Laws of Form, 1173

for logic, 773, 808

Sheffer stroke

as name for Nand, 1173

Shell patterns, 423

biology of, 1011

and cellular automata, 389

purpose invented for, 387

Shells

as animal artifacts, 1184

biology of, 1008

collecting, 1011

history of studying, 1008

internal, 1008

natural selection of shapes, 417

shapes of, 414-417

Shepherdson, John C. (England, 1926– )

and register machines, 896

Shift-commuting block maps

as cellular automata, 961

and history of CAs, 878

see also Cellular automata

Shift instructions

and CA boundary conditions, 951

and CA implementation, 866

Shift map, 149

and computer experiments, 919

exact iterates of, 919

history of, 961

and origin of randomness, 308

see also Doubling map

see also Rule 170

Shift registers

applications of, 1086

block frequencies in, 594

and CDMA signals, 1188

and cryptography, 1085

and extraterrestrial messages, 1190

flat spectra from, 1081

and history of CAs, 877

vs. linear congruences, 975

linear feedback, 1086

nonlinear feedback, 1088

as precursors to my work, 879

as random generators, 968, 974

searching for long period, 1193

sequences from, 1084

Shift rules

in cellular automata, 883

state transition graphs for, 963

Ships

fracture as issue for, 995

Shipwrecks

recognizing, 1183

Shocks

in CA fluids, 1000

in continuous fluids, 997

in numerical solutions of PDEs, 924

as origin of discreteness, 984

picture of in fluids, 377

as singularities in PDEs, 923

Shor, Peter W. (USA, 1959– )

in Preface, xiii

and quantum computing, 1148

Short descriptions

of general data, 553

Shortcuts

and computational reducibility, 738

and math proofs, 779

and NP completeness, 1148

Shortest descriptions

and algorithmic information, 1067

in block encoding, 1071

for integers, 916

Shortest paths

and distance on networks, 478

geodesics as, 1048

and polynomial time, 1146

see also Geodesics

Shortest programs

and algorithmic information, 1067

for particular sequences, 1186

undecidability of, 1138

see also Smallest programs

Shot noise, 968

in premium bond lottery, 969

Shotgun method

as application of randomness, 1192

Shub, Michael I. (USA, 1943– )

and quadratic pseudorandom generators, 1090

Shuffle-exchange process, 905

Shuffling (of cards), 968, 974

Sierpinski, Waclaw (Poland, 1882–1969)

and nested curves, 934

Sierpinski carpet, 933

Sierpinski pattern

and 2D substitution system, 187

in Cosmati mosaics, 873

formula for, 608

history of, 934

methods for generating, 931

network based on, 197

in network evolution, 509

and recursive multiplication algorithm, 1142

and rule 90, 25, 870

see also Rule 60

see also Rule 90

Sierpinski pyramid, 172

Sieve of Eratosthenes, 132, 909

cellular automaton for, 640

Sigma_n sets, 1139

Signal processing

for SETI, 1189

and Walsh transforms, 1073

Signals

artificial radio, 1188

from pulsars, 1188

recognizing intelligent, 835

Signature

of spacetime metrics, 1051

Significance (statistical), 594

Signs in languages, 1181

Silicon crystal

fracture of, 374

Silverman, Brian (Canada, 1957– )

in Preface, xiii

and WireWorld CA, 1117

Similarities

between natural systems, 298

in memory, 625

Simon, Herbert A. (USA, 1916–2001)

and automated proofs, 1157

Simple behavior

origins of, 351-361

and Principle of Computational Equivalence, 719

Simple groups

classification of finite, 945

Simple programs

crucial experiment on, 23-50

modelling with, 363-369

and searching for technology, 842

world of, 51-113

Simplex

and trivalent networks, 1029

Simplicial complexes, 1050

and approximating space, 1051

and quantum gravity, 1054

Simplicity

of human artifacts, 828

in scientific models, 1025

in ultimate theory of physics, 470, 1026

see also Simple behavior

Simplification

Boolean, 1095

of iterated map formulas, 1098

Simplify

and proofs, 1158

and real algebra, 1154

see also FullSimplify

Simulated annealing, 985, 985'

as application of randomness, 1192

for design optimization, 1193

Simulation games

and history of CAs, 877

Simulations

computational complexity of, 1148

and computational irreducibility, 742

as computationally expensive, 872

of financial markets, 1015

and history of complexity, 862

randomness in, 968, 1192

of rule 90 by rule 126, 269

of ultimate theory of physics, 466

see also Emulation

see also Models

Simultaneity

in relativity theory, 523

and spacelike slices, 1041

in the universe, 486

Sin (sine)

as basis for radio signals, 1188

and computational reducibility, 747

and constructible reals, 1129

curve of, 145

curves with curvature from, 418

difficulty of evaluating, 1134

emulating Mod, 1129

in form for iterated map, 921

and formulas for repetition, 607

and Fourier analysis, 1072

and Fourier series, 917

and logistic map formulas, 1098

and musical notes, 1080

and orthogonal bases, 1072

and uniform distribution mod 1, 904

and universal equations, 1129

and Weierstrass functions, 918

Sinai, Yakov G. (Russia/USA 1935– )

and ergodicity of billiards, 1022

Sine-Gordon equation, 163

Single-cell recording, 1075

Singularities

in Navier-Stokes equations, 997

in PDEs, 164, 923

in spacetime and computation speeds, 1130

Singularity theorems (in general relativity), 1048, 1053

Sinh

in solving 2D Ising model, 982, 1133

SinIntegral

curve of, 145

SIS (program for logic minimization), 1096

Sitnikov, Kirill A. (Russia, 1926– )

and 3-body problem, 973

Six-vertex model

as exactly soluble, 1133

SixJSymbol (6j symbol)

and spin networks, 1055

SK machines

and combinators, 898

Skeletons

forms of animal, 420

of radiolarians, 1011

Skepticism

and teleology, 1185

Sketches

and visual perception, 1076

Skewes number

and numbers of primes, 910

Skewing transformations, 933

Skin

pattern of cells in, 1007

see also Pigmentation patterns

Skolem, A. Thoralf (Norway, 1887–1963)

and non-standard arithmetic, 1169

and set theory, 1154

Skulls

process of growth of, 1010

related by transformations, 1010

Skunk

pigmentation pattern of, 426

Slash-dot (/.)

basic examples of, 854

Sleep, 1100

Sliding-block codes

as cellular automata, 961

Slime molds

spiral waves in, 1013

Slopes

digital representation of, 916

Slot (#)

and projection function, 907

Slow dynamics

in 2D cellular automaton, 336

Slow ship (in Game of Life), 964

Smale, Stephen (USA, 1930– )

and chaos theory, 971

in Preface, xiii

Small changes in initial conditions

see Sensitive dependence

Small programs

and computational complexity theory, 758

crucial experiment on, 23-50

world of, 51-113

Small universal Turing machines, 707, 1119

Smallest programs

and algorithmic complexity theory, 1143

and recognition of purpose, 832

for single CA steps, 884

see also Shortest programs

Smell

and experience of dogs, 827

sense of, 1105

Smith, Alvy Ray, III (USA, 1943– )

and branching in plants, 1005

and L systems, 893

in Preface, xiii

and universal CAs, 1115

Smith, Cyril S. (USA, 1903–1992)

and cellular structures, 1039

Smoke patterns, 377

Smoothing

and image processing, 1077

Smoothness

origin of, 327

see also Continuity

SMP (forerunner of *Mathematica*)

evaluation of recursive functions in, 906

in my personal timeline, 864

my use of, 854

and origins of this book, 18

semantic patterns in, 1156

and tiering of function arguments, 896

Smullyan, Raymond M. (USA, 1919– )

and combinators, 898

Snail shell

growth of, 415

Snakes

pigmentation patterns on, 426

SNOBOL (computer language), 894

Snow

character of, 993

Snowflake pattern

and 2D cellular automaton, 171

and 2D substitution system, 188

Snowflakes, 370

that are the same, 992

history of studies of, 992

issues in modelling, 364, 366

as motivating question, 17

SO(3)

and spin networks, 1055

SO(8) lattice

isotropy of, 980

SO(d)

and spin, 1046

Soap bubbles

packings of, 988

Soap films

vs. Einstein equations, 1052

fluid flow in, 999

in packings, 988

shapes of, 1009

turbulence in, 377

Soap foams

evolution of, 1039

Soccer ball

as defining curved space, 532

as spherical network, 1049

Social animals

and communication, 1180

Social sciences

and complex systems, 862

and defining complexity, 1068

and game theory, 1104

Gaussian distribution in, 977

historical foundations for, 1135

and history of statistics, 1082

mechanistic explanations in, 1185

quantitative laws in, 1014

summary of relations to, 9, 863

Socrates (Greece, ~470–399 BC)

and purpose in nature, 1185

Sofic systems, 958

Softshell

pigmentation pattern on, 426

Software

defining complexity of, 1069

design of as motivation, 18

for experiments in this book, 856

vs. genetic programs, 383, 1003

and history of computing, 1108

intuition from, 872

in practical computers, 1108

used in producing book, 852

Soil samples

tests for life in martian, 1179

Solar

see Sun

Solar system

randomness in, 973

see also Planets

Solid mechanics

as model for animal growth, 1010

Solid-state physics

and quantum theory, 1056

Solids

atomic-scale features on, 1193

breaking of, 374-375

extraterrestrials based on, 1180, 1190

growth of crystals of, 369

history preserved in, 1184, 1195

and memory, 823

modelled with springs, 374

and repeatable randomness, 976

surfaces of and crystal growth, 993

Solitons

and computational irreducibility, 1132

and conservation laws in PDEs, 1023

and elementary particles, 1044

and experimental math, 899

and Fermi-Pasta-Ulam experiment, 1020

optical for SETI, 1189

and sine-Gordon equation, 163

slowing of randomization by, 970

as topological defects, 1045

Solomonoff, Ray J. (USA, 1926– )

and algorithmic randomness, 1068

Solutions

exact, 1133

Sonar data, 1183

Songs

of birds, 826, 1180

of whales, 826, 1180

Sonic booms, 984

Sonification

and auditory perception, 1080

of cellular automata, 869

Sophistication of computations

see Principle of Computational Equivalence

Sort

algorithms for, 1142

lower bound on, 1143

and multiway system, 1036

networks for, 1142

NP completeness in verifying algorithms for, 1145

randomized algorithms for, 1192

and sequential substitution system, 894

and simple model of space, 518

in states of multiway systems, 937

and substitution system, 502

Souls

as defining features of life, 1178

Sound

in 2D, 923

and animal communication, 1180

emitted in fracture processes, 995

Sound compression, 1080

lossy, 572

Sound effects

and auditory perception, 1079

Sound representation

for cellular automata, 869

Sound waves

in fluids, 1000

Soundex system, 1100

Sounds

properties of, 1079