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