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, 475480, 530537
as stable background, 517
in ultimate theory of physics, 468, 472486, 516524
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, 475480
evolution of, 508515

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, 996

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–[2016])
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 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, 588596
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

Stonehenge, 829, 1184

Stopping problems
see Halting problems

Stored-program computers, 1108
and history of universality, 1110

Storms
as origins of randomness, 301