Index



Diabolus in musica (tritone), 917

Diagnosis
and causal networks, 1033

Diagonal arguments, 1128
and Ackermann function, 907
and computational complexity, 1143
and the continuum, 1127

Diagonal bands
in rule 30, 28

Diagonalization
and Church's Thesis, 1125
and growth rates, 1162
and recursive functions, 908

Diameters of networks, 1029

Diamond shape
generated by CAs, 171

Diatoms
forms of, 385, 1011

Dice
and legal randomness, 1068
randomness from, 305, 968, 969, 971

Dicotyledons (plants)
branching in, 1004
symmetries in, 1007

Dictionaries
as lookup mechanism, 622

Dictionary-based encoding, 565, 1071

Difference approximations
see Finite differences

Difference engines, 1107

Difference patterns in CAs, 251
probabilistic estimates of, 953
properties of, 949
for reversible rules, 1018

Difference tables
patterns in, 1091

Difference vectors
in multiway system states, 937

Differential analyzer, 1107

Differential equations
for almost periodic functions, 917
attractors in, 961
compression of time in, 732
and continuous computation, 732, 1129
and curves from curvature, 1009
exact solutions to, 1133
existence of solutions to, 940
and financial markets, 1015
for fluid convection, 971
for GegenbauerC, 1091
for geodesics, 1049
machines for solving, 1107
modelling with, 366
for noisy vacuum tubes, 971
numbers generated from, 916
ordinary, 922
partial, 161-164
renormalization group, 955
second-order CAs and, 1018
and special functions, 1092
and time series, 1083
and universality, 1129
and weather prediction, 1178
see also Partial differential equations

Differential geometry, 1048
and shell growth, 1009

Differential growth
in animals, 421
and folding, 417
history of, 1010
in horns, 413
in shells, 414

Differentiation (biological)
in biological evolution, 386

Differentiation (mathematical)
and computability, 1128

Diffie, Whitfield (USA, 1944- )
and cryptography, 1089
in Preface, xiii

Diffraction
exactly soluble problems in, 1133
and image processing, 1077
path integral theory of, 1061
patterns from, 1082

Diffuse reflection
and surface roughness, 996

Diffusion
and biological growth, 419
in block cellular automata, 463
in continuous CAs, 156
and crystal growth, 993
and harmonic growth, 1008
in model of boiling, 994
non-standard, 1024
of plant hormones, 404
in plant phyllotaxis, 1007

Diffusion equation, 163
derivation of in CAs, 1024
emerging from block CAs, 464
minimal approximation to, 1024
origin of, 922
as parabolic equation, 940
and path integrals, 1057
and random walks, 978
and Schrödinger equation, 1060

Diffusion-limited aggregation (DLA), 979, 994
and biological form, 1004
and lightning, 995
and randomness tests, 1085

Digestive systems
branching structures in, 1008

Digit count sequences, 905

Digit reversal systems, 125-127, 905

Digit sequences, 116-127, 136-142
and 2D substitution systems, 931
amplification of, 308
arbitrary operations on, 1091
and arithmetic coding, 1071
and chaos theory, 149-155, 307-314
in complex bases, 933
of complex numbers, 1094
computable, 1128
and computational reducibility, 743, 747
computing nth elements of, 912
in computing powers, 615
conversion between bases, 1094
correlations within, 902
cryptography with, 1089
and data compression, 560
and diagonal arguments, 1128
evidence for randomness in, 912
and fast evolution rules, 1094
Fibonacci, 560
and formulas for nesting, 608
history of, 902, 1182
and history of chaos theory, 971
and history of computing, 1107
implementation of, 901
in iterated maps, 149
leading elements in, 914
and linear congruential generators, 318
for mathematical functions, 1134
multiplicative, 902
and multiway systems, 207
for negative numbers, 942
nested, 913
non-locality in, 124
in non-periodic tiling pattern, 219
normal, 912
operations in terms of, 731
as origins of nesting, 358
of pi, 136
of pi and universe, 1027
of pi as precursors, 878
on Pioneer 10 plaque, 1189
of powers, 614, 903
as procedures for making numbers, 143
randomness in, 967
of rational numbers, 138
reversal and Walsh functions, 1073
reversal of, 905
see also Digit reversal systems
robustness of, 920
self-delimiting, 560
of square roots, 139
and substitution systems, 891
for transfinite numbers, 1162
and trees, 891
and Turing machines, 760
see also Sequences

Digital computation
compared to analog, 730, 1128

Digital electronics
as avoiding noise, 302
and practical computers, 1108

Digital filters (FIR)
and sequential CAs, 1035

Digital image processing
see Image processing

DigitCount, 902
and 3n+1 problem, 904
and additive CAs, 1092
basic example of, 854
and computational reducibility, 747
in densities from rule 90, 953
as inverse recursive sequence, 906
and nested networks, 1037
and operator representations, 916
and recursive sequences, 131, 906
and rule 90 pattern, 870
and solution of logistic map, 1098
and Thue-Morse sequence, 890

Dilation, time
see Time dilation

Dilation (in mathematical morphology), 1077

Dimensional analysis
and fluid flow, 996
and Kolmogorov spectrum, 997
and Planck length, 1027

Dimensions
above 3 and reality in math, 860
of attractors in CAs, 958
in axioms of geometry, 1154
definitions of, 1030
differential geometry of non-integer, 1051
fractal, 933
general effects of, 170
in network systems, 936
of networks, 478, 533
of physical space, 515
of posets, 1041

Dimer problem, 959

Diminished fifth
curve of, 146

Diophantine equations
and algorithmic randomness, 1067
assuming randomness in, 1165
and axiom systems, 1166
as constraint systems, 944
cubic, 1164
enumeration of, 1165
Hilbert's Tenth Problem and, 1161
history of, 1164
largest solutions for quadratic, 1164
linear and polynomial time, 1146
and Moire patterns, 1078
and multiway systems, 1157
NP completeness and quadratic, 1146
table of, 790
and undecidability, 787, 1138
universal, 786, 1164

Diophantus (Egypt, ~246 - ~330 AD)
and Diophantine equations, 944

Diploid cells
and randomness in biology, 970

Dirac, Paul A. M. (England, 1902-1984)
and history of quantum mechanics, 1056

Dirac delta functions, 1081

Dirac equation
discretization of, 1060
as simple model, 1025

Directed acyclic graphs (DAGs)
causal networks as, 1033

Directed network systems, 1040

Directed percolation (probabilistic cellular automaton), 591, 976

Directional entropies
in cellular automata, 960

Directional reversibility
in cellular automata, 1017

Dirichlet domains, 987
and CA lattices, 929

Disassemblers (decompilers), 1184

Discharge tubes
randomness from, 969

Discontinuities
and catastrophe theory, 1009
and phase transitions, 981

Discontinuous functions, 901, 918

Discord
perfect (tritone), 917

Discrete packings, 987

Discrete space, 472
history of in math, 1050
history of in physics, 1027
and quantum gravity, 1055

Discreteness
and atomism, 876
averaging out of, 327
in computer programs, 976
in models vs. continuous, 368
origins of, 337
and Principle of Computational Equivalence, 729
in space, 984

Discretization
of PDEs, 924

Discrimination
learning of in neural nets, 1102

Disjunction
as name for Or, 1173

Disjunctive Normal Form (DNF), 616, 1095
lower bounds on Xor in, 1143
multilevel, 1096
and proof lengths in logic, 1175
and proofs of axiom systems, 1170

Disk (computer) traffic
randomness from, 970

Disks
packing of, 350

Dislocations
patterns of in fracture, 375

Dispersion relations
and repetitive behavior, 988

Display hacks
for nested patterns, 932
as precursors to my work, 879

Displays
of 3D cellular automata, 927
and history of computing, 1108
lines on digital, 916
studying CAs using, 46

Dissipative structures
and history of complexity, 862
and reaction-diffusion, 1013

Distances
defined by geodesics, 1048
defined on networks, 478
general properties of, 1030
non-symmetric and torsion, 1052

Distribute
and powersets, 1171

Distributed computing
and causal invariance, 1035
and computer experiments, 899

Distributive laws (in logic), 817

Distributivity
and additive CAs, 952

Districting
and Voronoi diagrams, 987

Dithering, 1077

Divaricate patterns on shells, 423

Divergence in chaos theory, 153, 307, 921

Divergent series
in QED, 1060

Diversity
of animal shapes, 421
in biological organisms, 395
in branching patterns, 402
of leaf shapes, 401

Divide (/)
and NC computations, 1149
in terms of digits, 139

Divide-and-conquer algorithms, 1094, 1141

Divination (fortune-telling), 1135

Divine proportion (GoldenRatio), 890

Divisibility
as defining poset, 1041
of numbers, 132
see also GCD

Division in groups, 1153

Divisors
and cycles in shift rules, 963
distribution of, 909
and maximal periods, 950

DivisorSigma (number of divisors), 135, 910
iteration of, 911

DLA
see Diffusion-limited aggregation

DNA
1/f noise in, 969
in Arecibo radio message, 1190
and definition of complexity, 1069
and definition of life, 825, 1178
as evolutionary artifact, 1184
extraterrestrial messages in, 1184
fingerprinting, 970
and genetic programs, 1002
and nanotechnology, 1193
NP completeness in, 1146
random changes in, 970
use of randomness in, 1192

DNF
see Disjunctive Normal Form

Do (Do loop)
for computing factorial, 1110

Documentation length
as definition of complexity, 1069

Dodecahedron
in deformable packings, 988
elongated, 930
network of, 476, 1049
rhombic, 929, 986, 987
rhombo-hexagonal, 930
trapezoid-rhombic, 986

Dogs
and sense of smell, 827

Dolphins
communication by, 1180
and sense of fluid motion, 827

Domains
in 2D cellular automata, 335
effective rules for in CAs, 980
and repetitive behavior, 356

Domino problems, 211-221
approximate solutions to, 345
enumeration in, 959
undecidability in, 1139
see also Tilings

Don't care elements (in Boolean formulas), 1095

Doodles
rule-based, 875

Dot (dot product)
as associative function, 1094
and differential geometry, 1048

Dot-coms
as speculative stocks, 1015

Double-angle formulas
and iterated maps, 1098

Double exponential growth
in primitive recursive functions, 908

Double negation
law of, 817

Doubling
using cellular automata, 832
using combinators, 1122

Doubling map
and chaos theory, 149, 306
computational difficulty in, 1147
periods in, 257
see also Shift map

Draft lottery
randomness of, 969

Drag coefficients, 998
for airplanes, 997

Dragon curves, 189, 893, 932

Drainage patterns
and landscape structure, 1001
see1187

Drake, Frank D. (USA, 1930- )
and SETI, 1189

Drake equation, 1191

Drawing lots, 968, 1192

Drawing straws, 968

Drexler, K. Eric (USA, 1955- )
and nanotechnology, 1193

Drill (military)
use of rules in, 875

Drip tips of leaves, 1005

Drop (drop elements)
basic example of, 853

Droplets
in 2D cellular automata, 980

Drops
in water streams, 984

Drugs
and brain function, 1099
from cone shells, 1011
origins of current, 1194
random trials of, 1192
searching for, 842, 1193
and spider webs, 1184

Drums
as sending signals, 827
sound from, 1079

DSolve
see also Differential equations
see also Partial differential equations

Duality
between And and Or, 1151
between evolution and causal network, 496
between particles and extended objects, 1044
in string theory, 1029

Ductile materials, 994

Duhem, Pierre M. M. (France, 1861-1916)
and chaos theory, 971

Dummy variables
in predicate logic, 1152

Dunes (sand)
repetitive patterns of, 1187

Dungeons & Dragons
shapes of dice in, 971

Duplication formulas (functional relations)
and function evaluation, 1134
and logistic map formulas, 1098

Dürer, Albrecht (Germany, 1471-1528)
and parametrizing growth, 1010

Dust
as seed for crystals, 369, 992

Dutch
logic operations in, 1173

Dyadic order
for Walsh functions, 1073

Dyadic pure predicate logic, 1152

Dynamic programming
and CA implementation, 869
and recursive sequences, 906

Dynamic spin systems, 982

Dynamic triangulation
and quantum gravity, 1054

Dynamical symmetry breaking, 1047

Dynamical systems theory
and 1D constraints, 941
and cellular automata, 960
and continued fractions, 915
and digit sequences, 901
finite automata in, 958
and history of CAs, 877
and history of chaos theory, 971
and history of complexity, 862
and my work on CAs, 880
and ODEs, 922
and spectra in, 1081
summary of relations to, 14