# Index

B particles

time reversal violation for, 1019

Babbage, Charles (England, 1791–1871)

and computers, 1107

and universality, 1110

Babylonian mathematics

and calculation, 1149

and computing pi, 911

and computing Sqrt, 913

current influence of, 792

and definition of math, 859

and labelling in geometry, 1182

and math in science, 859

numbers in, 901

and primes, 908

rules in, 875

Babylonians

and constellations, 1187

military drill of, 875

and rule 30 artifacts, 42

Bachelier, Louis (France, 1870–1946)

and randomness in markets, 1014

Bachet's problem (operator representations), 916

Back-biased zener diodes, 970

Backpropagation

in neural networks, 1102

Backtracking

in 3n+1 problem, 904

in cellular automata, 1089

and proof searching, 1157

in rule 30, 605

in satisfying constraints, 941

in tiling problems, 217

Backus, John (USA, 1924– )

and computer languages, 1104

Backus-Naur form, 1104

Backward evolution in CAs, 435

Bacon, Roger (England, ~1219 – ~1292)

and math in science, 859

Bacteria

genetic programs of, 1002

smallest self-replicating, 1179

Bag model

as mechanistic model, 1026

Bak, Per (Denmark/USA, 1947-[2002])

and self-organized criticality, 989

Baker, Alan (England, 1939– )

and Diophantine equations, 1164

Baker's method

and Diophantine equations, 1164

Baker's transformation (tent map), 150

Balance equations (rate equations), 984

Balanced binary trees, 897, 898

Balanced delimiters, 989

Ball rolling

in bistable system, 341

as source of randomness, 970

Balladonia-Caiguna road, 1187

Ballistics tables

and history of computing, 1107

Balls

cyclic tag systems made with, 895

packing of, 349, 986

Bamboos

growth of, 1004

Banach-Tarski result

in set theory, 1154

Bands

in Moire patterns, 1078

Bandwidth

in perception, 1079

of radio signals, 1188

Banks, E. Roger (USA, 1944– )

and 1D universal CA, 1115

and 2D universal CA, 1117

Barnacles

patterns on, 385

Barnsley, Michael F. (England/USA, 1946– )

and parameter space sets, 1006

and pictures of ferns, 1005

Base 2 (binary), 116

and chaos experiments, 919

history of, 902

as natural notation, 1182

in practical computers, 1108

Base 6

powers of 3 in, 614, 903

Base 10 (decimal), 116

and chaos experiments, 919

powers of 2 in, 614, 749

Base 16 (hex)

digits of pi in, 912

Base 60

and history of numbers, 902

Base -2 notation, 902

Bases (number), 116

complex, 932, 933

conversions between, 1094

Fibonacci, 560, 892, 902

generalized, 902

locality of powers in, 1093

and normal numbers, 912

and substitution systems, 891

Basic forms

in image compression, 574

Basic language

and history of computing, 1108

and register machines, 101

Basins of attraction

boundaries of, 1101

for cellular automata, 276

and phase transitions, 341

Basis functions

in data compression, 574

Basket star

nested pattern in, 1008

Batcher, Kenneth E. (USA, 1935– )

and sorting networks, 1142

Bats

auditory system of, 1079

Battles

instabilities in infantry, 1014

Bays, Carter (USA, 1940– )

and 3D class 4 CAs, 949

bcc (body-centered cubic), 930

and deformable packing, 988

Voronoi diagram, 987

BDDs (binary decision diagrams), 1097

Beacons

extraterrestrial, 836

Beam buckling

and chaos theory, 971

Bearings

characteristic shapes of, 1183

Beatty sequences, 890

Beauty

see Art

Beaver dams

as animal artifacts, 1184

Beehives (in Game of Life), 964

Beehives (made by bees), 1011

Beeler, Michael D. (USA, 1944– )

and 2D Turing machines, 930

Begriffsschrift

of Frege, 1149

Beilstein database, 1194

Bell, Alexander Graham (USA, 1847–1922)

and speech sounds, 1080

Bell, David I. (USA/Australia, 1953– )

and structures in Life, 965

Bell, John S. (England/Switzerland, 1928–1990)

and quantum mechanics, 1058

Bell curve (Gaussian), 977

Bell Laboratories, xiii

Bell's inequalities, 1064

history of, 1058

in quantum field theory, 1065

Belousov, Boris P. (Russia, 1893–1970)

and oscillatory chemical reactions, 1013

Bénard convection, 1000

as repetitive behavior, 988

Bendix, Peter B. (USA, 1946– )

and Knuth-Bendix procedure, 1037

Benford, Frank (USA, 1883–1948)

and leading digits, 914

Benford's Law, 914

and powers, 903

Bennett, Charles H. (USA, 1943– )

and logical depth, 1069

in Preface, xiii

and reversibility of computation, 1020

and sphere packing, 985

Bentley, Wilson A. (USA, 1865–1931)

and snowflakes, 992

Berger, Robert (USA, 1938– )

and non-periodic tilings, 943

and undecidability in tiling, 1139

Berlekamp, Elwyn R. (USA, 1940– )

and Berlekamp-Massey algorithm, 1087

Berlekamp's algorithm (for Factor), 1192

Bernoulli, Daniel (Netherlands/Switzerland, 1700–1782)

and molecular theory of gases, 1019

BernoulliB (Bernoulli numbers)

difficulty of evaluating, 1134

BesselI (modified Bessel function)

and continued fractions, 914

and Egyptian fractions, 915

BesselJ (Bessel function)

asymptotics of, 917

curve of, 145

and Klein-Gordon equation, 922

in Mie scattering, 1133

and transcendental numbers, 912

BesselY (Bessel function of second kind)

in Mie scattering, 1133

Beta (volatility)

of prices in markets, 1015

Beta decay

parity violation in, 1019

and quantum field theory, 1057

beta sheets in proteins, 1003

Bethe lattice

see Tree

Bianchi classification

for Einstein equations, 1053

Bianchi identity, 1049

Bias

randomness to avoid, 841, 1192

Bible

and origins of complexity, 861

randomness generation in, 968

and understanding nature, 876

Bibliographic information

on my papers, 881

in this book, 850

Bibliometrics

for axiom systems, 1153

for cellular automata, 878

Biedenharn-Elliott identity (for 6j symbols), 1055

Bifurcations

and chaos theory, 972

and fluid flow, 998

in rate equations, 984

Big bang model

and basic cosmology, 1055

and thermodynamics, 1021

Billiards model, 971, 1022

and thermodynamics, 446

Billion (as 1,000,000,000), 849

Billowing (in clouds), 1001

Binary alloys, 985

Binary cellular automata, 53

see also Elementary cellular automata

Binary-coded decimal (BCD), 919

Binary-coded ternary, 560, 1070

Binary counter

in non-periodic tiling, 219

pattern made by, 117

Turing machine acting as, 888

see also Digit sequences

Binary decision diagrams, 1097

Binary mixtures of circles, 350, 985

Binary numbers, 116

history of, 902

see also Base 2

see also Digit sequences

Binary operators

axioms for, 805

and generalized additivity, 952

number of, 1171

possible Boolean, 806

Binary power method, 1093

Binary star system

randomness in, 313

Binary trees

balanced, 897, 898

as combinator expressions, 1123

infinite, 196

space of possible, 405, 1006

and symbolic expressions, 897

Binomial (binomial coefficients)

article of mine on, 882

and associative CAs, 956

and balanced parentheses, 989

and Cantor set, 890

and computational reducibility, 747

and continuous CA, 922

and correspondence systems, 1139

encoded as integer equation, 1160

and encodings of arithmetic, 1164

and entropy of particles in box, 1022

equations involving, 945

and Fibonacci, 890

modulo k, 955

and nested patterns, 610

and number of conserving CAs, 1023

and number of expressions, 897, 1175

and primitive recursion, 907

and rule 90 pattern, 870

and Sierpinski pattern, 931

and trinomial coefficients, 1091

Binomial distribution

and basic statistics, 1083

and pegboard, 312

Biological evolution, 383-399, 1001-1003

CA idealization of, 391

compared to technology evolution, 398, 1183

and definition of life, 824

and features of proteins, 1003

and form of DNA sequences, 1184

and intelligence, 822

and leaf shapes, 1005

major new features in, 1003

optimization strategies in, 985

of perception, 634, 1105

and shell shapes, 415

see also Natural selection

Biological growth, 400-422

Eden model for, 978

history of studies of, 1003

see also Growth

Biological systems

compared to physical ones, 967

and definition of complexity, 1069

and extraterrestrial life, 1179

organization through partitioning in, 457

in relativity theory, 1042

and thermodynamic behavior, 453, 1021

Biology, 383-428

and argument by design, 861

attitudes in, 1001

defining features of, 824

vs. engineering, 393, 1004

Gaussian distribution in, 977

history of complexity in, 1001

mathematics in, 859

as molecular engineering, 842

molecules used in, 1194

Occam's razor in, 1025

physics applied to, 1003

probabilistic models in, 1082

purposes of systems in, 1185

randomness applied in, 1192

randomness seen in, 326, 970

regularities in, 384

summary of relations to, 8, 863

undecidability in, 1138

Biomedical applications, 9, 842

Biomedical devices

and nanotechnology, 1193

Biomedical image processing, 1076

Biometric data

randomness in, 970, 1014

Biprism

and non-periodic tiling in 3D, 943

Birds

vs. airplanes, 1100

color vision in, 1075

nests of as artifacts, 1184

patterns in flocks of, 1011

pigmentation patterns of, 426

songs of, 826, 1180

Birkhoff, Garrett (USA, 1911–1996)

and equational logic, 1172

Bismuth hopper crystals, 993

Bistable systems, 341

see also Metastable states

Bit reversal

systems based on, 125

in Walsh transforms, 1073

BitAnd (bitwise And)

in Batcher sort, 1142

in CA implementation, 865

integer equation for, 1160

patterns generated by, 871

and rule 90 pattern, 870

and Sierpinski pattern, 931

and zero boundaries, 951

Bitmaps

compression of, 560

images as, 1108

lines in, 916

BitOr (bitwise Or)

integer equation for, 1160

iteration of, 906

patterns generated by, 871

and representing integers, 916

and weighted randomness, 976

Bitpacking

and cellular automata, 866

Bits

in numbers, 116

in practical computers, 1108

see also Digit sequences

Bitslicing

and cellular automata, 866

Bitwise functions

iterated, 906, 921

and logic in computer languages, 1173

patterns generated by, 871

Bitwise implementation

of cellular automata, 866

of rule 30 center column, 871

BitXor (bitwise Xor)

and Gray code, 901

iteration of, 906

and nim, 939

patterns generated by, 871

and representing integers, 916

and Sierpinski pattern, 931

sounds from, 1080

Bivalve shells, 1008