# 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

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