Index



A_4 (tetrahedral group), 1032

A_5 (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, 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, 997
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- )
and inspirational book cover, 864
and molecular dynamics, 879, 999
in Preface, xiii

Alekseev, Vladimir M. (Russia, 1932-1980)
and 3-body problem, 973

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

Ammonite septa, 385, 1008

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