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 1 (unary), 560, 1070

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

Bayesian inference, 595, 1083

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

Beat notes, 146, 1079

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

Behaviorism, 1099, 1135

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, 383399, 10011003
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, 400422
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, 383428
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