# 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, 547-635

and recognizing meaning, 826

statistical, 588-596

traditional idealization of, 736

using mathematics, 606-620

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, 413-422

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, 422-429

and security systems, 1183

shapes of and mathematics, 859

similarity of forms in, 421

territories of, 987

use of randomness by, 1192

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, 383-428

to financial systems, 429-432

general issues about, 857

to mathematics, 772-821

to physics, 369-382, 433-545

summaries of, 7-11

to technology, 840-843

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

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, 122-124

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, 997

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

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 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