D0L systems, 82–85
see also Substitution systems, neighbor-independent

D1L systems, 85–87

da Vinci, Leonardo (Italy, 1452–1519)
and fluid turbulence, 997
and geometrical rules, 878
and math in science, 859
and phyllotaxis, 1007
and rule-based pictures, 875
and theory of lunes, 873

Daedalus
as designer of maze, 873

Daisies
phyllotaxis in, 409
regular form of, 385

Damping
and attractors, 957
of fluid perturbations, 381

Dante Alighieri (Italy, 1265–1321)
and rhyming schemes, 875

Dappled patterns
from 2D cellular automata, 428

Darwin, Charles R. (England, 1809–1882)
and Origin of Species, 1001
and origins of complexity, 861

Darwinian evolution, 386
summary of relations to, 14
see also Natural selection

Data
analysis of, 548
artifacts in, 1184
information content of, 1181
recognizing meaning in, 826

Data compression, 560–576
history of, 1069
lossy, 572
practicalities of, 1069
two-dimensional, 567
see also Compression

Data Encryption Standard (DES), 1085
and history of CAs, 960
as randomness generator, 975

Data processing
and history of computing, 1107

Data structures
and network systems, 936

Databases
as analogy for memory, 621
of chemical compounds, 1194

Dataflow systems
and causal invariance, 1035

Dates
conventions for in book, 851

Daubechies wavelets, 1074

Davis, H. Chandler (USA/Canada, 1926– )
and dragon curves, 893

Davis, Martin D. (USA, 1928– )
and Diophantine equations, 1161
in Preface, xiii

Davis-Putnam rules, 1171

Dawn chorus
natural radio signals and, 1187

DCT (discrete cosine transform), 1074

de Broglie, Louis-V.-P.-R. (France, 1892–1987)
and wave-particle duality, 1056

de Bruijn, Nicolaas G. (Netherlands, 1918–[2012])
and maximal sequences, 1089

de Bruijn networks, 940
and CA attractors, 957
and local conservation laws, 1023
for shift registers, 1089
and sorting networks, 1142

de Moivre, Abraham (France/England, 1667–1754)
and Gaussian distribution, 977

de Morgan's law (in logic), 817

Dead languages, 1184

Dead time
in randomness generators, 303

Deadlocks
using randomness to avoid, 841, 1192

Dean's Eye cathedral window, 873

Debugging
intuition from, 872
and proofs about programs, 1168

Decidability, 753
see also Undecidability

Decimal numbers, 116
recurring, 138

Decimation
in additive CA patterns, 955
and self-similarity in rule 90, 870

Decimation systems, 909
and firing squad problem, 1035

Decision analysis
and causal networks, 1033

Decision making
and game theory, 1104

Decision problem
and history of universality, 1110

Decision procedures
see also Algorithms
see also Undecidability

Deck of cards
perfect shuffle of, 974

Decoding
see Cryptanalysis

Decoherence (in quantum mechanics), 1063

Decompilers, 1184

Deconstructionism
and limitations of science, 1196
and postmodernism, 1196
and theories of communication, 1181

Decorative art, 43, 872
see also Art

Decrement function
combinators for, 1122

Decrement-jump instructions
in register machines, 97

Dedekind, J. W. Richard (Germany, 1831–1916)
and axioms for arithmetic, 1152
and categoricity of models, 1172
and primitive recursion, 907
and real numbers, 1153

DedekindEta
difficulty of evaluating, 1134

Deduction
automated mathematical, 1157
of cellular automaton rules, 1089
in mathematics, 775
of rules from data, 592
see also Intelligence
see also Perception

Deep inelastic scattering, 1044

Deep theorem
definition of, 1176

Defects
as localized structures, 990
topological, 1045

Deficient numbers, 910

Definability
of operations in arithmetic, 1163

Definitions
and character of principles, 1126
of existing sciences, 863
of intelligence, 822, 1178
of life, 823, 1178
of mathematics, 859
of purpose, 829

Deformable objects
packing of, 988

Degrees of unsolvability (arithmetic hierarchy), 1126, 1139

Dehn, Max W. (Germany, 1878–1952)
and word problem for groups, 1141

Deism, 1196

Deity
see God

∇ (del)
and isotropy, 980

Delay equations
and road traffic flow, 1014

Delay lines
and history of CAs, 877

Delayed choice experiments, 1059

Delete
and Boolean minimization, 1095
and recursive sequence, 906

DeleteCases
and minimal finite automata, 957
and pattern-avoiding sequences, 944

Delimiters
balanced and nesting, 989

Delta functions
and spectra, 1081

Deltas (of rivers)
nesting in, 988

Democratic hypothesis (in particle physics), 1044

Democritus (Greece, ~460 – ~370 BC)
and atomism, 876
and extraterrestrial life, 1180

Demodulation (substitution)
in proofs, 1155

Dendrimers, 1194

Dendrites
in nerve cells, 1075

Dendritic crystal growth, 371, 993

Dendritic erosion patterns, 1001

Dendritic patterns
in 2D cellular automata, 171
in 2D substitution systems, 188

Denominators
and continuous CA background, 922
minimal in rational numbers, 950

Densest packings, 986

Density
of circle packings, 986
of difficult problems, 1147
in percolation theory, 983
in tag systems, 894
of universal systems, 1126

Density in cellular automata, 265, 953
conservation of, 458
diffusion of in block, 463
estimates of, 953
as non-computable, 1128
phase transition in, 341
undecidability of limiting, 1138

Density perturbations
and sound in fluids, 1000

Dentin
mammoth ivory, 873

Denudation (in landscapes), 1001

Deposition
and landscape structure, 1001
see also Aggregation systems

Depth
for combinator expressions, 1123
and Horton stream order, 1001
and symbolic systems, 897

Depth-first recursion
in substitution systems, 1033

Depth-first traversal
of backtracking trees, 1089

Depths
of logic expressions, 1096, 1148

Derandomization
of randomized algorithms, 1192

Derivations
in formal languages, 1103
in mathematics, 775

Derivative (differential derivative)
as composite head, 896
and relation to DigitCount, 902

Derivatives (financial), 1015

DES (Data Encryption Standard), 1085
and history of CAs, 960
as randomness generator, 975

Desborough Mirror, 873

Descartes, René (France/Netherlands, 1596–1650)
and complexity in biology, 861
and discrete space, 1027
and equiangular spirals, 1008
and snowflakes, 992
and sums of three squares, 910
and theoretical biology, 1003
and Turing test, 1099

Deserts
landscape in, 1001

Design in nature
and origin of complexity, 861
and teleology, 1185

Det (determinant)
and Hadamard matrices, 1073
metric related to volume by, 1050
and NC computations, 1149
and polynomial time, 1146
and testing for dimension, 1031
and zeta functions, 959

Detachment rule
in axioms, 1150
and proofs, 1155

Determinism
and fate, 967
and free will, 750, 1135
and Gödel's Theorem, 1132
vs. probability in models, 588

Deterministic chaos
recognizing, 972
see also Chaos theory

Deterrents, 1136

Deutsch, David (England, 1953– )
in Preface, xiii
and quantum computers, 1147

Development (in biology), 400–428
see also Growth

Developmental constraints
on forms of organisms, 387

Developmental pathways
invariance of in evolution, 395

/dev/random (randomness pool), 970

DFA (deterministic finite automaton), 957
see also Finite automata