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

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