# Index

Space

continuity of in geometry, 1154

curved, 531

defining dimension of, 1030

and defining motion, 521

history of discrete, 1027

locality in, 518

and matter, 474, 1028

and motion of particles, 529

with negative curvature, 1049

as a network, 475-480, 530-537

as stable background, 517

in ultimate theory of physics, 468, 472-486, 516-524

see also Geometry

Space (outer)

features of Earth from, 835, 1187

Space complexity, 1142

Space-filling curves

and the continuum, 1127

and defining dimension, 1030

and image compression, 1072

parametrization of, 935

and paths of caterpillars, 1011

and storage of strings, 1101

and substitution systems, 893

Space groups, 929

Space networks, 475-480

evolution of, 508-515

Spacecraft

complex trajectories for, 1183

as first contact with extraterrestrials, 1190

and general relativity, 1048

landings on Moon of, 1180

plaques on, 1190

self-reproducing, 876

supposed sightings of alien, 1180

Spacefiller (in Game of Life), 965

Spacelike hypersurfaces, 1041

and initial value general relativity, 1053

Spacelike slices, 1041

in causal networks, 516

Spaceship gun (in Game of Life), 965

Spaceships (in Game of Life), 964

and emulating Nand, 1117

Spacetime

curvature in, 534

see also Gravity

see also Space

Spacetime code, 1027

Spacetime entropies, 960

and repetitive behavior, 954

and rule 30 encryption, 1087

Spacings

of random matrix eigenvalues, 977

of zeros in sine functions, 917

of zeros in zeta function, 918

Spain

ornamental art in, 873, 874

Spanning trees

and drainage patterns, 1001

Sparks

as source of randomness, 302, 969

Sparse computation

in Game of Life, 949

Spatial entropy, 958

Spearman, Charles E. (England, 1863-1945)

and defining intelligence, 1178

Special functions (of mathematical physics), 1092

and computational reducibility, 1132

curves from, 145

difficulty of evaluating, 1134

Special-purpose devices

for cellular automata, 868

and shift registers, 974

Special relativity

see Relativity theory

Species (biological), 1003

Spectra

of cellular automata, 1082

and defining randomness, 1068

in natural systems, 969

of nested 2D patterns, 1082

of nested mechanical systems, 1081

of noise, 968

of number theory functions, 911

properties of, 1080

of random walks, 977

and recognizing chaos, 972

of substitution systems, 586, 1080

of Weierstrass functions, 918

Spectra (atomic)

and quantum history, 1056

Spectral test

for linear congruential generators, 974

Spectrum (radio)

uses of, 1188

Speculative markets, 430, 1015

Speech

compression of, 1080

generation of in brains, 826

and hidden Markov models, 1084

recognition of, 1100

as recognizable radio signal, 1188

sounds of, 585, 1079

Speed of light, 1041

and causal networks, 520

expansion of universe at, 1056

and information transmission, 518

invariance of, 523

and quantum effects, 543

and speed of gravity, 1047

Speed of sound, 997

Speed-up theorems, 1134

Speedups

and computational irreducibility, 743

in multiway systems, 1176

in Turing machines, 764

Spell-checking systems, 1100

Spelling

and soundex system, 623

Spencer Brown, George (England/USA, 1923- )

and axioms for logic, 1175

and Laws of Form, 1173

Sperm, 970

Sphere packing, 986

and codes, 1101

and cores of proteins, 1003

difficulty of, 349

and isotropy of lattices, 980

and lattices, 930

and pollen grains, 1011

and radiolarians, 1011

random, 986

Spheres

configurations of charges on, 1146

d-dimensional, 1091

and defining scalar curvature, 534

lattice points inside, 910

vs. Lorentzian spaces, 1051

networks approximating, 480

volumes of, 1050

Spherical networks, 1049

SphericalHarmonicY

and isotropy measures, 980

Spider webs

as animal artifacts, 1184

patterns in, 1011

Spike trains (for neurons), 1075

repeatability of, 976

Spin (in quantum theory), 1046

and Bell's inequalities, 1064

of elementary particles, 1043

in quantum computers, 1147

Spin-flip transitions, 1187

Spin foams, 1055

Spin glasses

and Boolean networks, 937

and computational irreducibility, 1132

ground states of, 944

NP completeness in, 1146

Spin networks, 1055

and discrete space, 1027

and loop quantum gravity, 1054

Spin-statistics connection, 1046

Spin systems

vs. cellular automaton fluids, 999

and computational irreducibility, 1133

and discrete quantum mechanics, 1060

as systems based on constraints, 944

undecidability in, 1138

see also Ising model

see also Lattice gases

Spines on shells, 1008

Spinning

as source of randomness, 970

Spinning top

as exactly soluble, 1133

Spinodal decomposition, 980

Spinors, 1046

as basic quantum feature, 1059

as formulation of general relativity, 1048

Spinoza's God, 1196

Spiral galaxies, 1021

Spiral waves

in reaction-diffusion CAs, 1013

Spirals

in animal horns, 413

in constraint searches, 941

and general study of form, 967

in hopper crystals, 993

vs. nesting, 357

in plant phyllotaxis, 408

in shells, 1008

as space-filling curves, 935

and substitution systems, 192

Spirits

and animism, 845, 1195

Spirograph-like patterns

in astronomy, 1187

Splashes, 377

as art, 839

as fluid phenomena, 1000

repetitive patterns in, 988

Splicing

in DNA sequences, 1184

Splines, 1084

Split (split list)

basic example of, 853

and cyclic tag systems, 895

and iterative run-length encoding, 905

and minimal finite automata, 957

and nested patterns, 931

and run-length encoding, 1070

in sparse Life, 949

and Turing machine 1507, 1144

Spontaneous generation (of life), 1179

Spontaneous magnetization

in Ising model, 981

Spontaneous organization, 223

Spontaneous symmetry breaking

and particle masses, 1047

in phase transitions, 983

Sporadic groups, 945

Spores

as origin of life, 1179

Spots

origin of on animals, 428

Spread spectrum communications, 1086, 1188

Springs

characteristic shapes of, 1183

nested arrangements of, 1081

Sqrt (square root)

and computational reducibility, 747

computing, 141, 913

and constructible reals, 1129

continued fractions for, 144

cryptanalysis of, 1089

digit sequences under, 731

digits of, 139

and generating function for rule 150R, 1018

as growth rate for mobile automaton, 72

as growth rate for rule 225, 885

as growth rate for TM, 888

and Julia sets, 933

machine for computing, 1107

nested, 915

and random walks, 977

randomness in digits of, 967

register machine for, 1114

and standard deviation of Gaussian, 977

see also Quadratic irrationals

see also Sqrt[n] for specific n

Squags (Steiner quasigroups), 1171

enumeration of, 805

Squalls

as origins of randomness, 301

Square-free sequences, 944

and cyclic tag systems, 895

Square lattices

cellular automata on, 170

isotropy on, 980

random walks on, 329

TMs on, 184

Square roots

of cellular automata, 956

Squares

numbers as sums of, 135, 910

Squaring

cellular automaton for, 639, 1109

digit sequences under, 731

and quadratic congruential generators, 975

repeated for powers, 615, 1093

sequences, 1090

Turing machines for, 1144

see also Quadratic residue sequences

Squaring the circle, 1137

Squashy objects

packing of, 988

Squid

visual system of, 1075

Staatliche Museum, Berlin, 873

Stability

in financial systems, 430

of matter, 1059

from randomness, 266

topological, 1045

Stable state

from random initial conditions, 224

Stacks

and context-free languages, 939

Stadium

and quantum chaos, 1056

in whimsical description, 850

Staffelbach, Othmar J. (Switzerland, 1952- )

and cryptanalysis of rule 30, 1087

Staircases

in block emulations, 1118

characteristic shapes of, 1183

Standard deviation

of Gaussian distribution, 976

Standard mathematical functions, 1091

computational reducibility of, 744

and continuous computation, 731, 1128

curves from, 145

and digit cryptography, 1089

and exact solutions, 1133

vs. normal numbers, 912

patterns from, 747, 870

and rational integrals, 916

and three-body problem, 972

see also Mathematical functions

Standard Model (of particle physics), 1025

elementary particles in, 1043

and gauge theories, 1045

origins of mass in, 1047

StandardForm

issues in designing, 1182

for programs in notes, 854

Star forts

nested architecture of, 874

Star Trek

extraterrestrials in, 1191

Starfish

shape of, 385

symmetries in, 1007

Stars

as approximate spheres, 1187

formation of, 455, 1021

in general relativity, 1053

as parts of giant artifacts, 834

with planets, 1179

suitable for extraterrestrials, 1191

in three-body problem, 973

total light from in night sky, 1021

State space

of cellular automata, 275, 869, 959

State transition graphs

for cellular automata, 961

for Markov processes, 1084

for shift registers, 1089

States

of cellular automata, 865

in quantum theory, 1056

States of matter

as analogy for CA classes, 235

Stationary phase approximation

in path integrals, 1061

Statistical estimates

in cellular automata, 953

Statistical fluctuations

and shot noise, 968

Statistical independence

and Central Limit Theorem, 976

Statistical mechanics

book about as early inspiration, 17, 864

and complexity in science, 861

and defining randomness, 1067

emergence of simple laws in, 1025

and existence of formulas, 1132

and financial markets, 1015

foundations of and randomness, 967

Gaussian distributions in, 977

history of, 1020

and history of statistics, 1082

models for fracture from, 995

Monte Carlo methods in, 1192

origins of irreversibility in, 441

and path integrals, 1061

and pattern formation, 947

phase transitions in, 981

summary of relations to, 16

use of in studying CAs, 961

Statistics, 588-596

complexity of models in, 1068

and cryptanalysis, 1085

of data in 2D, 591

and defining randomness, 1067

history of, 1082

of human behavior, 1014

and isocorrelation textures, 1078

and neural networks, 1100

of proteins, 1184

of rule 30 center column, 871

as tests for fraud, 1184

and texture discrimination, 1077

as way to avoid complexity, 861

as way to avoid randomness, 967

of written languages, 1181

Steam engines

linkages in, 1129

and thermodynamics, 1019

Steel

fracture in, 994

Stein, Paul R. (USA, 1924-1990)

and iterated maps, 918

Steiner quasigroups (squags), 1171

Steiner triple systems, 1171

Stems of plants, 400

vs. antlers, 1008

Stereograms

random dot, 1076

Stevens, Peter S. (USA, 1936- )

and patterns in nature, 967

StieltjesGamma

difficulty of evaluating, 1134

Stigmergy (local rules for animals), 1184

and aggregation systems, 1011

Still Lifes (persistent structures in Life), 964

Stimulated emission, 1195

Stimulus-response

as definition of life, 823

and human thinking, 1099

undecidability in, 1138

Weber's law in, 1014

StirlingS1 (Stirling numbers)

pattern generated by, 870

StirlingS2 (Stirling numbers)

pattern generated by, 870

Stirring

as source of randomness, 969

Stochastic analysis, 587, 1081

Stochastic differential equations

and cybernetics, 862

Stochastic models, 968

and external randomness, 299

see also Probabilistic models

Stock market prices, 429, 1014

Stokes, George G. (England, 1819-1903)

and fluid flow past a sphere, 998

Stokes lines

for mathematical functions, 917

Stone, Paper, Scissors game, 1105

Stone Age

art, 839, 874

stone circles, 1184

stone tools, 1183

Stoneham, Richard G. (USA, 1920-1996)

and normal numbers, 912

Stopping problems

see Halting problems

Stored-program computers, 1108

and history of universality, 1110

Storms

as origins of randomness, 301