Index
Strange attractors
for differential equations, 961
vs. thermodynamics, 1020
see also Chaos theory
see also Class 3 behavior
Strategies
for combinatorial optimization, 985
in game theory, 1104
for theorem proving, 1158
Strawberries
phyllotaxis in, 409
Stream ciphers, 598
and randomness generators, 975
Streamlined objects in fluid flow, 998
Streams
and landscape structure, 1001
Streetlamps
visible from space, 1187
Stress-energy tensor
in Einstein equations, 1052
Stress patterns
around cracks, 995
Stretching
and randomness, 306
String concatenation systems (correspondence systems), 757, 1139
String figures
as constructed by rules, 875
String matching, 1101
String rewriting systems, 88, 894
and Church's Thesis, 1125
and history of universality, 1110
as idealization of math, 1150
see also Multiway systems
see also Sequential substitution systems
String theory (in physics)
and models of particles, 1044
and nature of space, 1028
not related to strings of elements, 1033
particle types in, 1047
and quantum gravity, 1054
and quantum history, 1058
as ultimate theory of physics, 1025
StringJoin
and correspondence systems, 1139
StringLength
and correspondence systems, 1140
StringPosition
and generalized substitution systems, 1033
StringReplace
and multiway systems, 937
vs. sequential substitution systems, 894
and substitution systems, 889
StringReplacePart
and generalized substitution systems, 1033
and multiway systems, 937
Strings
of balanced parentheses, 989
matching of in memory, 621
in multiway systems, 937
non-overlapping, 503, 1033
overlaps in, 503
undecidability of problems about, 1138
Strings (physical)
in musical instruments, 1079
Stripes
origin of on animals, 429
and transition in rule 184, 338
Striping (bitslicing)
and implementing CAs, 866
Stroke (Sheffer)
as notation for Nand, 1173
Strong coupling
and path integrals, 1061
Strong interactions (in particle physics), 1025, 1057
Strouhal number, 998
Structural landforms, 1001
Structural stability
and history of chaos, 971
Structuralism
and theories of communication, 1181
Structurally-stable defects, 1045
Structure-property relationships for chemicals, 1194
Structure theorems
and integrals, 1177
Structure transformations
in symbolic systems, 102
Structures
in class 4 systems, 281–296
form of in architecture, 967
theory of in math, 1150
see also Localized structures
Student t-distribution
found by Monte Carlo methods, 1192
Stunted trees
as additive cellular automata, 878
Sturgis, Howard E. (USA, 1936–1990)
and register machines, 896
Sturmian sequences, 1081
and block frequencies, 1084
and Fibonacci substitution system, 890
SU(2)
and spin, 1046
and spinors, 1059
SU(2) ⊗ U(1) model, 1025
SU(3)
as gauge group in QCD, 1057
SU(n)
and 1/n expansion, 1040
and discrete quantum theory, 1060
Subclasses
within class 4 CAs, 948
Subdivision
and data compression, 568
Subdivision systems (substitution systems), 82
2D, 187
Subformula property
and arrangement of proofs, 1155
Subgraph matching
and network evolution, 1038
NP completeness of, 1145
Subjective contours in visual perception, 578
Sublimation
as phase transition, 981
Subordinate clauses, 1104
Suborganisms
and biological evolution, 1002
Subsequences
frequencies of, 1084
repeating, 1072
Subset relation
as generating posets, 1041
Subshifts of finite type (finite complement languages), 941
2D generalizations of, 959
and excluded blocks in CAs, 958
and repetitive states in CAs, 954
Substitution
and structure of proofs, 775, 1155
see also ReplaceAll
Substitution ciphers, 1085
Substitution systems, 82–87
2D, 187–192
and animal growth, 420
and attractor structures, 959
as basic origin of nesting, 357
and billiard trajectories, 971
and CA encodings, 1119
and causal networks, 497
and computational reducibility, 1134
and continued fractions, 914
d-dimensional, 932, 1091
and data compression, 568
and digit sequences, 891
in embryo development, 1009
emulated by CAs, 659, 1111
emulated by TMs, 765
emulating CAs, 666
with equal block frequencies, 594
and evaluation chains, 1095
finite automata for patterns from, 1091
formulas for patterns from, 608
and genealogical trees, 1002
as generators of digit sequences, 913
geometrical, 189–192
see also Geometrical substitution systems
that get to any string, 1035
history of, 893
implementation of, 889
implementation of generalized, 1033
initial conditions from, 272
in iterated run-length encoding, 905
and lines on rasters, 916
as model of crushing, 986, 996
in music, 875, 1080
neighbor-dependent, 85–87
neighbor-dependent 2D, 192, 935
neighbor-independent, 82–85
neighbor-independent 2D, 187
network, 508–515
for non-periodic tiling, 942
order of replacements in, 501
and paths, 892
and pattern-avoiding sequences, 944
and plant branching, 400, 1005
probabilistic, 1084
random, 969
random initial conditions in, 949
randomness in, 88
relation to cyclic tag systems, 895
relation to iterated maps, 921
relation to multiplication, 903
relation to tag systems, 93
for rule 90 pattern, 609
for rule 150 pattern, 609
sequential, 88–92
see also Sequential substitution systems
and shapes of leaves, 401
and sine curves, 147, 917
space of possible, 406
spectra of, 586, 1080
and systems based on constraints, 942
and texture generation, 1077
and visual perception, 583
and Walsh functions, 1073
see also Multiway systems
SubsuperscriptBox
and nested patterns, 932
Successor function
in arithmetic axioms, 1152
Succulents
phyllotaxis in, 409
Sugars
and definition of life, 825
Sum
numbers generated from, 917
Sum (totalistic) rules, 60
Sumerians
art of, 43, 873
and constellations, 1187
Summaries of data, 548
Sun
bending of light by, 1048
circular shape of, 861, 875
radiation from and weather, 1177
radio signals from, 1187
as source of radio noise, 1187
Sun Microsystems, xiii, 854, 881
Sundial shell
growth of, 415
Sundman, Karl F. (Finland, 1873–1949)
and three-body problem, 972
Sunspots
1/f spectrum of, 969
radio noise from, 1187
Superconductors
phase transition in, 981
phyllotaxis-like patterns in, 1007
Supercooling
and crystallization, 992
Superelliptic Diophantine equations, 1164
Superexponential growth
and real algebra, 1154
in TM running times, 763
Superfluidity
in neutron stars, 1188
phase transition in, 981
Supergravity theories
and space vs. contents, 1028
Superimposing grids at different angles, 1078
Supernatural being
as creator of complexity, 3, 861
and free will, 752
see also God
Supernovas, 1188
Superposition
in cellular automata, 952
and nested patterns, 955
and PDEs, 923
and quantum computers, 1148
in quantum theory, 541, 1058
of waves, 988
Supersonic flow, 377
in CA fluids, 1000
past cylinders, 999
and Navier–Stokes equations, 996
sonic booms from, 984
see also Shocks
Superstitions
and animism, 1195
Superstrings
see String theory
Supersymmetry
as basis for models, 1025
particles in models with, 1043, 1047
and quantum gravity, 1054
and vacuum fluctuations, 1062
Supervised learning, 1102
Surface tension
and crystal growth, 993
and packing, 988
in radiolarians, 1011
and soap foams, 1039
Surfaces
of crystals, 993
curvature of, 1049
discretization of, 1050
geodesics on, 531, 1049
metrics for, 1048
and repeatable randomness, 976
roughness of, 996
see also Solids
Surjectivity
in cellular automata, 280, 959
undecidability of, 1138
Surreal numbers
as generalizing numbers, 1168
and runs of digits, 914
Suture lines
in skulls, 1010
Swell on oceans
as repetitive behavior, 988
Swindale, Nicholas V. (England/Canada, 1951– )
and pigmentation patterns, 1012
Switch engine (in Game of Life), 965
Switching circuits
and Boolean functions, 1097
and causal networks, 1033
Syllogisms, 875, 1151
and quantifiers, 1152
Symbiosis
and biological evolution, 1002
Symbolic algebra
and computational reducibility, 1132
see also Algebra
Symbolic computation
and proof in operator systems, 801
see also Computer algebra
Symbolic descriptions
and discreteness in programs, 976
Symbolic dynamics
and arithmetic coding, 1071
and cellular automata, 960
and history of CAs, 878
and history of iterated maps, 919
and origin of substitution systems, 893
Symbolic expressions
and computer communication, 1182
in Mathematica, 1103
to represent integers, 1121
structure of, 896
Symbolic formulas
for cellular automata, 869
and computability, 1128
and history of universality, 1109
for iterated maps, 1098
see also Exact solutions
Symbolic integration, 1177
Symbolic logic
see Logic
Symbolic notation, 1182
Symbolic programming
in Mathematica, 853
Symbolic representation
of infinity, 788
Symbolic systems, 102
based on networks, 898
combinators as, 711
confluence in, 1036, 1113
emulating CAs, 668, 1113
history of, 898
implementation of, 896
and operator systems, 1172
test for universality of, 1123
tree representation of, 897
and valuation functions, 916
Symmetric cellular automata
in 1D, 886
in 2D, 928
Symmetric differences
and second-order CAs, 1018
Symmetric graphs, 1032
Symmetric matrices
in neural networks, 1102
Symmetry
in aggregation systems, 979
in alkane molecules, 1194
between space and time, 485
in biological organisms, 1007
and CA discrete space, 1027
and constraints on network rules, 509
of crystals, 993
of exact solutions, 1133
in fossil organisms, 1179
and general study of form, 967
and isotropy on lattices, 980
and maximum periods, 950
in ornamental art, 872
of particles in physics, 528
and phase transitions, 981, 983
in plants, 1007
in quasicrystals, 994
of random biological patterns, 1013
in snowflakes, 992
and sphere packings, 987
and state transition graphs, 962
of tilings, 943
Synapses, 1075
and memory, 1102
randomness in, 970
Synchronic linguistics, 1181
Synchronization
in practical computing, 1035
in the universe, 486
Synchrotron radiation, 1187
Synergetics
and history of complexity, 862
and reaction-diffusion, 1013
Synoptic weather maps, 1178
Syntax
CA as checker of, 1109
for computer communication, 1182
and context-free languages, 1103
of formal languages, 939
of math, 1150
and semiotics, 1181
Synthesis (chemical), 1194
Synthesizers (audio)
waveforms in, 1079
Syracuse problem (3n+1 problem), 904
Syrinxes of songbirds, 1180
System identification, 550, 1083
Systems theory
definitions of complexity in, 1069
and history of complexity, 862
summary of relations to, 15
Systolic arrays
and history of CAs, 877
Szmielew, Wanda M. (Poland/USA, 1918–1976)
and commutative groups, 1160
Szudzik, Matthew P. (USA, 1973– )
and axioms for logic, 1151
in Preface, xii