# Index

Epicureans

and atomism, 876

and complexity, 861

and contents of space, 1028

Epicurus (Greece, 341–270 BC)

and randomness, 967

Epicycles

as examples of models, 992

Epistemology

and computational irreducibility, 1132

and Gödel's Theorem, 1167

implications for, 1196

and models vs. reality, 365, 991

EPR (Einstein-Podolsky-Rosen) experiment, 1064

epsilon_0 (transfinite ordinal), 1162

and unprovability in arithmetic, 1163

epsilon-delta arguments, 1177

Equal ( == )

calculus of expressions, 1170

in multivalued logic, 1175

non-universality of, 1174

truth tables for, 802

Equality testing

randomized methods in, 1192

Equational logic

automated proofs in, 1158

proofs in, 1172

Equational systems

vs. modus ponens, 1151

operator systems as, 801

see also Operator systems

Equations

antidiffusion, 923

axioms as, 1153

computation based on, 731

and concept of purpose, 1185

as constraints, 940

and defining mathematics, 860

as defining numbers, 916

in different axiom systems, 812

difficulties in models with, 368

difficulties of solving, 1129

in history of science, 44

integer

see Diophantine equations

linear, 940

ordinary differential, 922

partial differential, 161-164

sequence, 1141

for sequences, 944, 1141

for snowflakes, 372

of state and gravity, 1053

for strings, 944, 1141

time vs. space in, 1032

undecidability of integer, 787

see also Burger's equation

see also Differential equations

see also Diffusion equation

see also Diophantine equations

see also Dirac equation

see also Einstein equations

see also Functional equation

see also Hodgkin-Huxley equation

see also KdV equation

see also Klein-Gordon equation

see also KPZ equation

see also Kuramoto-Sivashinsky equation

see also Laplace equation

see also Lorenz equations

see also Maxwell's equations

see also Navier-Stokes equations

see also Nonlinear Schrödinger equation

see also Partial differential equations

see also Polynomial equations

see also Quartic equations

see also Quintic equations

see also Schrödinger equation

see also Sine-Gordon equation

see also Transcendental equations

see also van der Pol equation

see also Wave equation

Equiangular spirals

generated from curvature, 418

in shells, 1008, 1008'

Equidistribution

and concatenation sequences, 913

of digit sequences, 912

of sequences, 903

statistical test for, 1084

in three-squares problem, 910

Equilibrium

approach to, 449

in chemical reactions, 984

in early universe, 1055

in Ising model, 982

and quantum measurement, 1063

in random networks, 1038

in self-gravitating systems, 1021

in thermodynamic systems, 450

Equivalence

between logic expressions, 775

in context-free languages, 1138

of NP-complete problems, 1145

in operator systems, 801

Principle of Computational

see Principle of Computational Equivalence

topological of manifolds, 1051

undecidability in problems of, 1138

see also Universality

Equivalence operations

and confluence, 1036

Equivalence principle, 530, 1047

and gravitational energy, 1054

and particle production, 1062

Equivalential calculus, 803, 1170

possible models of, 805

theorems in, 813

Eratosthenes (Egypt, 276–195 BC)

and prime sieve, 909, 909'

Erector sets

and history of CAs, 876

Erf (error function)

in diffusion equation, 1024

Ergodic theory

history of, 1020

Ergodicity

in dynamic spin systems, 982

of hard sphere gas, 1022

and Lissajous figures, 917

and rule 37R, 457

in search process, 347

vs. Second Law, 1020

Ermentrout, G. Bard (USA, 1954– )

and patterns on shells, 1012

ERNIE (randomness generator), 969

Erosion

and landscape structure, 1001

in mathematical morphology, 1077

Error-correcting codes, 1101

and data compression, 1069

found by searches, 1193

and Hadamard matrices, 1073

and quantum computers, 1148

and sphere packings, 986

and Voronoi diagrams, 987

Error-diffusion algorithm, 1077

Errors of measurement

and history of statistics, 1082

and origin of randomness, 967

Escapements

characteristic shapes of, 1183

Escher, Maurits C. (Netherlands, 1898–1972)

and ornamental art, 874

Esperanto (artificial language), 1103

Espresso, 1097

Essential incompleteness, 1159

Essential singularities

in QED perturbation theory, 1060

Essential undecidability, 1159

Estimation

of entropies, 959

in statistics, 1083

Ethane, 1194

Ether (physics)

atoms as knots in, 1044

as content of space, 1028

discrete model for, 1027

history of, 1024

and theory of light, 1041

Ethernet

randomization in, 1192

Ethics

and free will, 750

and responsibility, 1136

Euclid (?Egypt, ~300 BC)

and axioms for geometry, 1154

and foundations of math, 1149

and math in science, 859

and mathematical induction, 1152

and nature of space, 1028

and perfect numbers, 911

and primes, 909

theorem network of, 1176

and theory of lunes, 873

Euclidean geometry

systematic proofs in, 1177

Euclid's algorithm

and ContinuedFraction, 915

and GCD, 1093

as iterative algorithm, 1141

running time of, 1147

Euler, Leonhard (Switzerland/Russia/Germany, 1707–1783)

and continued fractions, 914, 915

and a cubic Diophantine equation, 1165

and differential geometry, 1009

and equations for geodesics, 1049

and Fermat's Last Theorem, 1166

and number theory, 878

and perfect numbers, 911

and primes, 909

Euler circuits

and polynomial time, 1146

EulerGamma (Euler's constant)

and Egyptian fractions, 915

and growth of DivisorSigma, 910

as not from rational integral, 916

as transcendental number, 912

EulerPhi (totient)

and cycles in shift rules, 963

and cyclic multiplication, 950

and encoding of lists, 1120

and GCD pattern, 1093

and RSA cryptography, 1090

and shift register periods, 975

Euler's formula

for planar networks, 1038

and spherical networks, 1049

Europa

and extraterrestrial life, 1179

Evaluation schemes

and recursive sequences, 906

Evens and Odds game, 1105

Event horizons

and black hole formation, 1053

and particle production, 1062

and time and computation, 1130

Events

causal network of, 488

Evil

and free will, 1135

Evoked potentials, 1098

Evolution theory

summary of relations to, 14

see also Biological evolution

Exact solutions, 1133

for additive CAs, 610, 951

and computational irreducibility, 1132

for dimer problem, 959

for hard hexagon model, 959

for Ising model, 982

for iterated map periodic points, 955

for Kondo model, 1057

lack of for 3-body problem, 972

for logistic map, 1098

and math functions, 610

for multiway systems, 1168

to Navier-Stokes equations, 996

for shift map, 919

for Turing machines, 1144

see also Closed forms

Excess (flicker) noise, 969

see also 1/f noise

Excitable media, 1013

Excluded blocks

from 1D constraints, 941

in cellular automata, 278, 958

in code 20, 958

Excluded middle

law of in logic, 817, 1158

Exclusion principle (in quantum theory), 1059

Executive toys

and chaos theory, 1183

plasma-filled globes as, 995

Exhaustive search, 217, 343

and cryptanalysis, 604

and mechanism vs. purpose, 838

for optimal programs, 842

Existence of solutions

to constraints, 940

to Navier-Stokes equations, 997

in PDEs, 923

Exists

in predicate logic, 1151

and r.e. sets, 1139

Exogenous randomness, 301-314

in cellular automata, 947

Exoskeleton in arthropods, 1011

Exp (exponential function)

and canonical ensemble, 982

continued fractions for, 144

difficulty of evaluating, 1134

digits of values of, 141

in Gaussian distribution, 976

as non-computable, 1128

and path integrals, 1061

Expand

Boolean analog of, 1095

Expansion of universe, 1055

and arrow of time, 1021

and cosmological term, 1052

and Einstein equations, 1053

and network evolution, 530

and particle production, 1062

and relativity history, 1048

and thermodynamics, 455

Experience

and perception, 547, 634

Experimental design

and Hadamard matrices, 1073

Experimental mathematics

foundations of, 793

and foundations of math, 821

history of, 899

practical methods in, 1090

summary of relations to, 14

this book as work of, 863

see also Computer experiments

Experiments

and computational irreducibility, 748

crucial for this book, 23-39

detecting fraud in, 1184

experience of modelling and, 991

and learning from this book, 856

problems with chaos, 919

repeatable randomness in, 326, 976

and thermodynamic initial conditions, 444

ExpIntegralEi (exponential integral)

and Egyptian fractions, 915

Explicitness

in design of *Mathematica*, 1177

importance of, 880

Exploratory computer experiments, 46

Exponent

of groups, 1172

Exponential distribution

in laws for human behavior, 1014

of mobile automaton periods, 887

Exponential divergence

in chaos theory, 921

Exponential growth

in biology, 1010

in combinators, 713, 1123

in Makanin's algorithm, 1141

of modes in PDEs, 988

in multiway systems, 207

in primitive recursion, 908

in proof sizes, 1155

in substitution systems, 82, 890

in Turing machines, 762, 1144

Exponential system

periods in, 257

Export

and image compression, 1074

Expressions

number of Nand, 1175

numbering of, 1170

representing integers, 916

representing numbers, 143

structure of symbolic, 896

in symbolic systems, 102

EXPTIME (exponential time), 1143

Extended objects in quantum field theory, 1057

ExtendedGCD

and linear congruential cryptanalysis, 1089

and linear Diophantine equations, 944, 1164

Extensive quantities

in cellular automata, 1022

Extrapolation of data, 549

Extrasolar planets, 1179

Extraterrestrial intelligence, 822

history of, 1180

messages to send, 1189

and perception, 550

perception by, 635

search for, 1188

Extraterrestrial life, 825, 1179

Extreme value distribution

as general result, 977

for random walks, 978

Extrinsic curvature

and Einstein equations, 1052

and initial value general relativity, 1053

Eyes

appearance of data to, 577

of flies, 385

randomness in saccades of, 1011, 1192