# 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