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
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 π, 136
of π and universe, 1027
of π 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, 996
Drainage patterns
and landscape structure, 1001
see1187
Drake, Frank D. (USA, 1930– )
and SETI, 1189
Drake equation, 1191
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