Index
A4 (tetrahedral group), 1032
A5 (icosahedral group), 938
Abacus
and history of computing, 1107
and history of numbers, 902
Abacus machines, 97–102
see also Register machines
ABC conjecture
and nearby powers, 1166
Abelian groups
axioms for, 773, 1153
CAs based on, 887, 956
shortest axioms for, 806
word problems in, 1141
see also Commutative groups
Abelian semigroups
see Commutative semigroups
Aboav–Weaire law, 1039
Aboriginal peoples
and animism, 1195
maze logos used by, 873
Absolute infinity, 1162
Absolute motion, 1042
Absorption laws (in logic), 817
Abstract algebra
and models of math, 1150
see also Algebra
Abstraction
and children, 1102
and human intelligence, 823, 1178
in mathematics, 792, 1149
and modelling, 366
for ultimate theory of physics, 468
Abundant numbers, 910
Acceleration
as equivalent to gravity, 1047
and finding geodesics, 1049
particle production by, 1062
and time dilation, 1042
Accounting
detecting fraud in, 1184
Accumulation points
in iterated maps, 961
Ackermann, Wilhelm (Germany, 1896–1962)
and Ackermann functions, 906
Ackermann functions, 906
and Church's Thesis, 1125
and growth rates, 1162
and recursive functions, 907, 908
and symbolic systems, 897
Acorns
phyllotaxis in, 409
Acoustic diffusers
and flat spectra, 1081
Action
Einstein–Hilbert for gravity, 1052
in path integrals, 1061
Activator-inhibitor processes
and animal growth, 419
and animal pigmentation, 427
and plant growth, 409
see also Reaction-diffusion processes
Active cell
in mobile automata, 71
Active media, 1013
and history of CAs, 878
Adaptation
and complexity in biology, 383
and definition of life, 1178
and fluid flow, 823
and human intelligence, 823, 1178
in visual system, 1075
Adaptive algorithms
for numerical integration, 1134
see also Genetic algorithms
Adaptive Huffman coding, 1069, 1071
Addition
cellular automata based on, 952
in digit sequences, 118
NC parallel algorithms for, 1142
representing numbers using, 916
Turing machines for, 760, 1144
see also Plus
Addition chains, 1095
Addition formulas
and logistic maps, 1098
Addition systems, 255
computational difficulty in, 1147
state transition graphs for, 961
Additive cellular automata
with 3 colors, 886
basic examples of, 870
block frequencies in, 594
continuous, 922
cryptanalysis of, 1087
cryptography with, 600
in d dimensions, 1092
difference patterns in, 950
encodings of arithmetic with, 1164
enumeration of, 952
as exactly soluble models, 1133
finding periods in, 1147
fractal dimensions in, 870, 955
generalized, 1018
and generalized additivity, 952
generating functions for, 1091
higher-order, 1018
history of, 878
with limited numbers of cells, 951
and multiplication systems, 1094
NC computations of, 1149
as not universal, 694
self-emulation in, 271
self-reproduction in, 824
self-similarity in, 955
sequential versions of, 1034
and shift registers, 974–975
spacetime entropies for, 960
and spacetime symmetry, 1032
speeding up, 1094
state transition graphs for, 963
and successive differences, 1091
temporal sequences in, 960
and texture generation, 1078
two-dimensional, 824
see also Finite fields
Additive processes
and Gaussian distributions, 976
Additivity
generalized, 952
one-sided, 604, 1088
in quantum mechanics, 1060
and surjectivity, 959
Addressing (computer memory)
and computer architecture, 1108
decoder trees for, 1183
emulating with CAs, 663
Adequate connectives (universal logic functions), 1173
for reversible logic, 1098
Adjacency matrices
and cycles, 958
Adjacency tensors
for hypernetworks, 1029
AEA statements (predicate logic)
sets associated with, 1139
universality of, 1152
Aerial reconnaissance
cellular arrays used in, 1076
and recognizing artifacts, 1183
Aesthetics
of music and bird songs, 1180
of physical models, 1025
of pictures in this book, 11
of ultimate theory of physics, 1026
Aether
see Ether
Affine transformations
and 2D substitution systems, 933
Aggregation systems
continuum behavior in, 331, 978
and crystal growth, 993
enumeration in, 980
generalized, 978
and growth of cities, 1014
implementation of, 978
and insect artifacts, 1011, 1184
as models of drainage, 1001
in one dimension, 979
and tumor growth, 1011
Aging
non-genetic aspects of, 1014
AGM (ArithmeticGeometricMean)
and computation of pi, 912
difficulty of evaluating, 1134
Agriculture
history of statistics and, 1082
visible from space, 1187
Aharanov–Bohm effect, 1059
AI
see Artificial intelligence
Aiken, Howard H. (USA, 1900–1973)
and Mark I computer, 1107
Air
patterns in flow of, 376
viscosity of, 996
Airfoils
characteristic shapes of, 1183
Airplanes
and analogy with birds, 1100
fluid flow past, 996, 996
fracture as issue for, 995
identifying wreckage of, 1183
turbulence in flight of, 1001
AiryAi (Airy function)
asymptotic oscillation of, 917
curve of, 145
Akaike information criterion, 1083
Albertus Magnus (Germany, ~1200–1280)
and mathematics in science, 859
Alcázar of Seville, 874
Alchemy
and history of complexity, 861
and understanding nature, 876
and universal objects, 1127
Alder, Berni J. (USA, 1925–2020)
and inspirational book cover, 864
and molecular dynamics, 879, 999
in Preface, xiii
Alekseev, Vladimir M. (Russia, 1932–1980)
and 3-body problem, 973
aleph0 (aleph zero)
and orders of infinity, 1127, 1162
and symbolic representation, 788
Alexander, James W. (USA, 1888–1971)
and moves on networks, 1038
Alexander moves
and general networks, 1038
and spin networks, 1055
Algae
growth of, 1004
shapes of, 385, 401
Algebra
axioms for, 773
Boolean, 1097
of classes, 1171
history of notation for, 1182
and history of posets, 1041
and history of proof, 1149
history of real, 1153
and models of mathematics, 1150
non-universality of basic real, 784
undecidability in, 1138
universal, 1171
use of predicate logic in, 1152
Algebraic analysis
of additive CAs, 951
Algebraic cellular automata
see Additive cellular automata
Algebraic coding theory, 1101
Algebraic complexity theory, 1143
Algebraic computation
and constraints on formulas, 945
and three-body problem, 972
see also Computer algebra
Algebraic curves
and linkages, 1129
in parameter space sets, 1006
Algebraic equations
compared to Diophantine, 944
and linear recurrences, 906
solution of, 945
and theta functions, 1092
Algebraic forms
of CA rules, 869, 884
Algebraic functions
and nested digit sequences, 913
in three-body problem, 972
and Thue–Morse sequence, 890
Algebraic generating functions
and hypergeometric functions, 1092
Algebraic geometry
and Diophantine equations, 1164
Algebraic logic
see Boolean algebra
Algebraic notation
and history of universality, 1109
origin of, 1182
Algebraic number fields
as generalizing numbers, 1168
Algebraic number theory, 1165
Algebraic numbers, 912
CA entropies as, 958
cryptanalysis of, 1089
and Diophantine equations, 1164
and Fermat's Last Theorem, 1166
and Fibonacci-like sequences, 891
and hard hexagon problem, 959
in hierarchy of numbers, 916
and Penrose tilings, 932
and spectra, 1081
Algebraic quantum field theory (axiomatic field theory), 1057, 1065
Algebraic simplification
and iterated maps, 1098
undecidability in, 1138
Algebraic systems
CAs based on, 886, 956
generators and relations in, 1169
universality of, 784
ways to use axioms in, 1159
Algebraic topology
and origins of category theory, 1154
Algebraic varieties
and additive CAs, 1018
Algol (computer language), 1104
Algorithmic complexity theory, 1143
Algorithmic information
compared to Shannon, 1071
and computational irreducibility, 1132
and defining randomness, 1067
and definition of complexity, 1069
with respect to CAs, 1186
Algorithmic randomness
defining randomness, 554
and quantum measurement, 1064
and randomness generation, 973
Algorithmically simple integers, 916
Algorithms
fast types of, 1141
fastest Turing machine, 761
general structures of, 990
for math functions, 1134
optimal, 1143
see also Programs
Alhambra in Granada, 874
Alien intelligence
see Extraterrestrial intelligence
Aliquot sums, 910
iterated, 911
Alkanes, 1194
Allometry (differential growth), 421, 1010
Alloys
searching for, 1193
Almost integers, 915
alpha helices in proteins, 1003
Alphabetical order
as lookup mechanism, 622
Alternative denial
as name for Nand, 1173
Aluminophosphates
as radiolarian analogs, 1011
Aluminum
dendritic crystals in, 993
AM (amplitude modulation), 1188
Amateur science, 857
Ambiguity problem
for context-free languages, 1138
Amino acid sequences
and evolution, 1003
and protein folding, 988
statistics of, 1184
Ammann, Robert (USA, 1946–1994)
and nested tilings, 942
Amorphous materials, 994
Amphibians
genetic programs of, 1002
pigmentation patterns on, 426
Amplification
and chaos theory, 971
Amplifiers
noise in, 302
Amplitude modulation (AM), 1188
Amplitudes in quantum theory, 541, 1062
continuous nature of, 1148