# Index

D0L systems, 82-85

see also Substitution systems, neighbor-independent

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

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