Index



Anagni, Italy
and Cosmati mosaics, 873

Analog computers
and chaos theory, 971
and Gibbs phenomenon, 899
and history of computing, 1107
and history of numbers, 902
linkages in, 1129
Shannon's general purpose, 1129
sound output from, 1080
theoretical power of, 730, 1128

Analog electronics
and form of radio signals, 1188

Analogy
in human thinking, 627

Analysis
by extraterrestrials, 836
definition of, 549
and NP completeness, 771
and Principle of Computational Equivalence, 722
processes of, 547635
and recognizing meaning, 826
statistical, 588596
traditional idealization of, 736
using mathematics, 606620

Analysis (mathematical)
axioms for, 774, 1155
non-standard, 1172

Analysis of variance (ANOVA), 977

Analytic continuation
of cellular automata, 1092
of mathematical functions, 1092
in quantum field theory, 1061

Analytic number theory
axioms needed for, 1166

Analytical engine, 1107

Analytical results
and computational reducibility, 1133

Analyticity
of S matrices, 1057
in three-body problem, 972
see also Continuity

Anatomy
and studies of form, 967

Anaxagoras (Greece, ~500 – ~428 BC)
and purpose in nature, 1185

And (^)
as associative function, 1094
axioms for, 803
axioms in terms of, 1151
and Boolean formulas, 1095
confluence of, 1037
emulated by CAs, 662, 1112
encoded as integer equation, 1160
and junctional calculus, 1170
in multivalued logic, 1175
and P completeness, 1149
and satisfiability, 1146
theorems involving, 817
truth tables for, 802, 806
words in languages for, 1173

Angelfish
pigmentation pattern of, 426

Angle bisection
in decorative constructions, 873

Angles
of CAs on lattices, 473
in differential geometry, 1048
of images on retina, 1076
Moire patterns from, 1078
of stems in plants, 408

Angular momentum
intrinsic of particles, 1046
quantization of, 1056
and spin networks, 1055

Anharmonic oscillator
lack of solution to, 1133

Animal behavior, 1011
and game theory, 1104
randomness in, 970

Animal breeding
as randomized algorithm, 1193

Animals
branching in, 1008
camouflage of, 1077
color vision in, 1075
communication among, 1180
evolution of plans for, 395
evolution of prediction in, 1105
free will in, 752, 1135, 1136
growth of, 413422
growth of farm, 1010
intelligence in, 825, 1178
as models for extraterrestrials, 1190
objects created by, 1184
overall forms of, 417
perception in, 827
pigmentation patterns of, 422429
and security systems, 1183
shapes of and mathematics, 859
similarity of forms in, 421
territories of, 987
use of randomness by, 1192

Animism, 845, 1195

Anisotropy
in aggregation systems, 978
in code 746, 979
of patterns on lattices, 980
of random walks, 977

Annualized models
and iterated maps, 918

Anomalies (quantum field theory)
as basic quantum effects, 1059
and high-mass particles, 1047

Anomalous magnetic moments, 1057, 1060

Anonymous functions
and lambda calculus, 1121

Anosov maps, 921
periodic points of, 955

ANOVA (analysis of variance), 977

Ant pheromones, 1194

Antarctica
Mars meteorite from, 1179

Anteaters
patterns on, 1013

Antennas
nesting in shapes of, 1183

Anthropic Principle, 1026
and teleology, 1185

Anthropology
and history of complexity, 862
and theories of communication, 1181

Anti-reflection in acoustic diffusers, 1183

Antibodies
randomness in, 970, 1184

Antichains (in posets), 1041

Antidiffusion equation, 923

Antikythera device
and history of computing, 1107
identifying purpose of, 1184

Antimatter
rarity of and T violation, 1019

Antiparticles
and T violation, 1019
and vacuum fluctuations, 1062

Antlers
growth of, 1008

Ants
artificial, 931

Aphorisms, 1196

Apical meristems (in plants), 409

APL (computer language), 1104

Apollo astronauts, 1180

Apollonian packing, 986
vs. Cosmati pattern, 873
and network evolution, 1037

Apollonius (Turkey/Egypt, ~262 BC – ~190 BC)
and circle packing, 986

Apoptosis (cell death), 419

Applications
to biology, 383428
to financial systems, 429432
general issues about, 857
to mathematics, 772821
to physics, 369382, 433545
summaries of, 711
to technology, 840843

Apply
basic example of, 853
for computing factorial, 1110

Aquinas, Thomas (Italy, 1225–1274)
and argument by design, 861

AR (automated reasoning)
see Automated theorem proving

Arab-Norman style, 873

Arabic script, 43, 874

Arc length, 418, 1048

ArcCos
and tent map, 919

Archeology
and extraterrestrials, 1190
identifying purposes in, 1184
recognizing artifacts in, 1183
recognizing purposes in, 829

Arches
characteristic shapes of, 1183

Archimedean solids
and trivalent networks, 1029

Archimedes (Sicily, 287–212 BC)
and pi, 911
and use of mathematics, 859

Architecture (building)
as affecting perception, 1106
ornament in, 872, 873
rules in, 874
study of form in, 967, 1010

Architecture (computer), 869

ArcSin
and logistic map formulas, 1098

ArcTan
and shift map, 919

Area
and axioms for geometry, 1154

Area law
for Nand expressions, 1097

Arecibo radio telescope, 1190

Argonne National Laboratory
and theorem proving, 1158

Argument by design
and complexity, 861
and teleology, 1185

Arguments of functions
currying of, 896, 1122
and Hilbert's 13th problem, 1128
and primitive recursion, 908

Aristotle (Greece, 384–322 BC)
and complexity, 861
and definition of life, 1178
and embryology, 1010
and gnomons, 1008
and history of logic, 1099
and logic in science, 860
and nature of space, 1028
and origins of randomness, 967
and purpose in nature, 1185
and theoretical biology, 1003

Arithmetic
algorithmic randomness in, 1067
axioms for, 773, 1152
of Babylonians, 859
as basis for science, 44
cellular automaton based on, 614
emulated by set theory, 1160
and history of proof, 1149
and intelligence, 1178
non-locality of, 124, 731
non-standard models of, 800, 1169
and origin of math, 792, 859
Presburger, 1143, 1152
processes of, 117
recursive functions and, 907
rules in, 875
universal equation in, 786
universality in, 784
see also Peano arithmetic

Arithmetic coding, 1071

Arithmetic hierarchy
and oracles, 1139

Arithmetic operations
and computational power, 730
performed by CAs, 639

Arithmetic progressions
and Ramsey theory, 1068

Arithmetic puzzles, 875

Arithmetic recurrences, 123
and register machines, 100

Arithmetic systems, 122124
emulating register machines, 673, 1114
history of, 1115
and Turing machine 600720, 1145
see also 3n+1 problem

Arithmetization of metamathematics, 1158

ARMA processes
spectra of, 1082
and texture discrimination, 1077

Armadillo skin
texture of, 385

Array computers
and history of CAs, 877

Arrow function (nested power)
and Ackermann function, 906
and symbolic systems, 103

Arrowheads
characteristic shapes of, 1183

Art
as affecting perception, 1106
applications to, 841, 872
astronomical systems like, 835
and cellular automata, 872, 929
examples of ornamental, 43
and form of extraterrestrials, 1191
recognition of, 839, 874
shell patterns in, 1012
and simple rules, 42, 872
study of form in, 967, 1003, 1010
summary of relations to, 11
and visual perception, 1076

Arthropods
growth of, 1011

Artichoke
phyllotaxis in, 409

Artifacts
on astronomical scales, 834
compared to nature, 3
created by animals, 1184
in data, 1184
on Earth from space, 1187
historical forms of, 1183
problem of recognizing, 828, 1183
in turbulence computations, 996
universe as, 1191

Artificial intelligence (AI), 628, 1099
and complexity history, 862
and defining intelligence, 1178
and extraterrestrial intelligence, 839
and free will, 1135
predicate logic and, 1152
summary of relations to, 12
and theorem proving, 1157
and visual perception, 1076

Artificial life
and biological form, 1004
and natural selection, 1001
summary of relations to, 12

Artificial organs, 842

Artificial snowflakes, 992

Artificial tissues, 842

ASCII versions (InputForm)
of programs in notes, 854

ASICs (Application-Specific Integrated Circuits), 1097

Asparagus
phyllotaxis in, 409

AspectRatio
and GoldenRatio, 891

Assembler
and my early programs, 854, 864
and register machines, 101, 1114

Associative algebras, 801
as generalizing numbers, 1168

Associative calculi
see Multiway systems

Associativity
3-argument analog of, 1171
of And and Or, 817
in Boolean functions, 1173
cellular automata based on, 886
and fast evolution, 1094
and generalized additivity, 952
in operator systems, 801
as source of self-similarity, 956
see also Flat

Assyrian military drill, 875

Asteroids
and chaos theory, 973

Astrology, 1135

Astronauts
quarantine of, 1180

Astronomical clocks, 1184

Astronomy
Babylonian, 859
extraterrestrial artifacts in, 834
geometrical patterns in, 1187
Greek, 861
and history of computing, 1107
and history of statistics, 1082
measurement errors in, 967
and prehistoric structures, 1184
radio phenomena in, 1187
randomness in, 313
and time in universe, 1021

Asymptotic freedom in QCD, 1057, 1062

Asymptotic growth rates, 1162
difficulty of finding, 1146

Asymptotic series
in perturbation theory, 1060

Asymptotic states
and quantum field theory, 1130

Asynchronous cellular automata
see Sequential cellular automata

Atanasoff, John V. (USA, 1903–1995)
and early electronic computers, 1107

Atmosphere
2D fluid flow in, 999
of extrasolar planets, 1179
and origin of life, 1179
and randomness in lightning, 995
turbulence in, 1001
and weather patterns, 1177

Atomic models
of crystal growth, 993
of fracture, 995

Atomic physics
6j symbols in, 1055
and quantum theory, 1056

Atomic-scale devices, 841, 1193

Atomic-scale features
and future forms of perception, 1106

Atomic-scale mapping of wear, 1184

Atomism
and elementary particles, 1044
as general theory, 1125
history of, 876

Atoms
arrangement of in crystals, 369
and chaos theory, 310
and concept of programs, 860
early models of, 1026
and history of complexity, 861
and history of quantum theory, 1056
as knots in the ether, 1028
in models of space, 1028
as source of randomness, 967
and thermodynamics, 445, 1019

ATP
and definition of life, 825

Attractors, 275
effective reversibility on, 1018
in finite systems, 961
in iterated maps, 961
and memory, 625
nested structure of, 959
and phase transitions, 341
in root finding, 1101
and structures in PDEs, 1129
in systems based on numbers, 961
in Turing machines, 961
in visual perception, 1076

Auctions
game theory and, 1105

Audio representation
for cellular automata, 869
for data, 1080

Auditory cortex, 1079

Auditory perception, 585588

Augustine (Algeria, 354–430 AD)
and free will, 1135

Aurora
and natural radio emissions, 1187

Australia
straight road in, 1187

Authentication
and hashing, 1100

Autoactive decay processes, 905

Autocorrelations
in shift registers, 1084
and spectra, 1080
in textures, 1076

Automata
see also Cellular automata
see also Finite automata
see also Mobile automata

Automated theorem proving, 1157
for axioms of logic, 811
and chemical synthesis, 1194
and group axioms, 1153
and paramodulation, 1156
and proof frameworks, 1177
proofs not useful from, 811, 1156
for Robbins axioms, 1151
of universality, 1115, 1127

Automatic groups, 1141

Autoplectic processes (intrinsic randomness generation), 973

Auxins (plant hormones), 1004

Auxology
and recursive growth, 877, 929

Avalanches
in sandpile models, 989
in snow, 993

Average-case difficulty, 1143

Averaging
in diffusion equation, 1024
and Gaussian distributions, 976
as source of continuity, 327
as source of uniformity, 353

Avoidable patterns (repetition-free sequences), 944

Axelrod, Robert M. (USA, 1943– )
and prisoner's dilemma, 1104

Axiom of choice, 774, 1154
and additive functions, 953

Axiom of infinity, 1154

Axiom of replacement, 1154

Axiom schemas, 1156, 1176

Axiom systems
based on multiway systems, 1173
for basic logic, 808
for cellular automata, 794, 1168
and defining complexity, 1068
effect of expanding, 1159
enumeration of, 809
for extended set theory, 1167
forcing an operator in, 1172
general structure of, 1150
vs. generators and relations, 1169
interpreting algebraic, 1153, 1159
model theory of, 1172
for multivalued logic, 1175
and operator evolution systems, 898
for operator systems, 801
and P=NP, 1146
proving correctness of, 802, 1170
sampled by mathematics, 795
table of in mathematics, 773
theorems holding in simple, 812
and Turing machines, 1145
and universality proofs, 1127
as way to handle infinity, 788

Axiomatic quantum field theory, 1057, 1065

Axiomless formulations
of logic, 1156

Axons
of nerve cells, 1075