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 equations, 944, 1141

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, 281296
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, 8287
2D, 187192
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, 189192
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, 8587
neighbor-dependent 2D, 192, 935
neighbor-independent, 8285
neighbor-independent 2D, 187
network, 508515
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, 8892
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

Sycamore leaves, 401, 1006

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