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 π, 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–[2007])
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 π 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–[2019])
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
β 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 Sierpiński 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 Sierpiński 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 Sierpiński pattern, 931
sounds from, 1080
Bivalve shells, 1008