Index



Black, Fischer (USA, 1938–1995)
and options pricing, 1015

Black Cloud (science fiction), 1190

Black holes, 1053
as dual to particles, 1045
gravity theories without, 1054
Hawking radiation from, 1062
and history of gravity, 1048
and singularities in PDEs, 923
and singularity theorems, 1053
as source of decoherence, 1063
and string theory duality, 1029
and time in computation, 1130

Black–Scholes model, 1015

Blackbody radiation
and quantum theory, 1056

Blinker (in Game of Life), 964

Blinker ship (in Game of Life), 964

Block (in Game of Life), 964

Block (scoping construct)
and notes programs, 854
and sorting networks, 1142

Block cellular automata, 459464
converting to ordinary CAs, 1023
implementation of, 1023
number of rules for, 1023
repetition periods in, 1023
for Schrödinger equation, 1060
and visual perception, 580

Block concatenation systems (correspondence systems), 757, 1139

Block diagrams
and computer interfaces, 1103

Block encoding, 563
maximal compression in, 1071

Block maps
as cellular automata, 878, 961

Blocking transformations
in CAs, 269, 701, 1118
and renormalization, 955

Blocks
conservation laws for, 1022
in error-correcting codes, 1101
frequencies of, 590, 1068, 1084
in rule 30 pattern, 569, 725, 871, 1127
visual patterns of repeating, 582

Blood vessels
branching pattern of, 413

Blotting paper
spreading on as diffusion, 978

Bluff bodies in fluid flow, 998

Blum, Lenore C. (USA, 1942– )
in Preface, xiii
and random generators, 1090

Blum, Manuel (USA, 1938– )
in Preface, xiii
and random generators, 1090

BMP format
compression in, 1070

Boat
fluid flow past, 996
on ocean as random system, 301

Bobrow, Daniel G. (USA, 1935–[2017])
and simple Turing machines, 1143

Body-centered cubic (bcc), 930
and deformable packing, 988
Voronoi diagram, 987

Bohm, David J. (USA/England, 1917–1992)
and discreteness of space, 1027
and hidden variables, 1058

Bohm–Aharanov effect, 1059

Bohr, Niels H. D. (Denmark, 1885–1962)
and quantum theory, 1056

Boiling
as discrete transition, 337
models of, 994
as phase transition, 981, 983

Boiling points
of alkanes, 1195
difficulty of computing, 1194

Boltzmann, Ludwig E. (Austria, 1844–1906)
and statistical mechanics, 1019

Boltzmann equation
and H theorem, 1020
Monte Carlo studies of, 1192

Boltzmann factors
and 1/f noise, 969
and Ising model, 982
and path integrals, 1061

Bones
development of, 1010
facial, 1010
formation of, 420
growth of, 417, 421

Bonnet shell, 415

Book of Changes
and substitution systems, 893

Book of Kells
nested patterns in, 873

Boole, George (England/Ireland, 1815–1864)
and axioms for logic, 1151
and Boolean functions, 1097
and continuous logic, 1175
and model for thought, 1099

Boolean algebra, 1151
as example of lattice theory, 1153
as generalizing numbers, 1168
representations of, 1171
see also Logic

Boolean expressions, 1095
for cellular automata, 616, 869, 884
and defining complexity, 1069
history of, 1097
and learning theory, 1102
lower bounds in, 1143
minimizing, 1095
minimizing as NP-complete, 1145
satisfiability of, 768

Boolean functions
16 basic possible, 806
emulated by CAs, 662
emulated by rule 30, 704
generated by finite automata, 1097
number of, 1096
and quantum computers, 1148
represented by perceptrons, 1102

Boolean hypercube
and layout of networks, 1031

Boolean networks, 936
and Nand expressions, 1096
as precursors to my work, 879

Boomerangs
characteristic shapes of, 1183

Boone, William W. (USA, 1920–1983)
and word problem for groups, 1141

Bootstrap hypothesis (in particle physics), 1044

Bora Bora
symmetric shape of, 1187

Borel, F. E. J. Emile (France, 1871–1956)
and defining randomness, 1068
and normal numbers, 912

Born interpretation (in quantum mechanics), 1058

Borrows
in subtraction, 870

Bose–Einstein condensation, 1058

Bosons
spin-statistics of, 1046

Botany, 400412
classification in, 1004
growth processes in, 400

Bouncing of objects
and randomness, 312, 971

Boundaries
of 2D CA patterns, 929
and image processing, 1077
motion of in 2D CAs, 335

Boundary cases
in CA classification, 240
and computational difficulty, 1147
and undecidability, 948

Boundary conditions
in CA implementations, 866, 951
random, 947
and shift registers, 1088

Boundary layer (in fluid flow), 996

Boundary value problems
for additive CAs, 601
as constraint satisfaction, 940
in PDEs, 923

Bounded depth logic, 1096

Bounded fan-in logic, 1096

Bourbaki group, 1150

Bowditch figures, 917

Box counting
and dimensions, 933

Boyer–Moore theorem prover, 1158

Brachiopod
form of opened, 385

Brachistochrone
as exactly soluble, 1133

Brackets
balanced sequences of, 897
and symbolic systems, 103

Brady, Allen H. (USA, 1934– )
and 2D Turing machines, 930

Bragg reflection, 1082

Brain
of birds and bird songs, 826, 1180
computational equivalence of, 721, 844
determinism in, 1135
and free will, 750
mathematics and the, 1177
memory in, 624
physiology of human, 1098
repetitive rhythms in, 1011
source of will in, 1136
and speech generation, 826
and universals in language, 1181
visual processing in, 580

Brain coral
maze-like patterns in, 1013

Brainteasers, 1104

Branch cuts (in complex plane)
and equality testing, 1192

Branching
in animals, 413, 1008
history of models of, 1005
in plants, 400, 1004
as producing nesting, 357
in proofs, 1155
and study of form, 967
in substitution systems, 84

Branching processes
and multiway systems, 938

Branching programs
register machines as, 97

Bravais, Auguste (France, 1811–1863)
and phyllotaxis, 1007

Bravais, Louis F. (France, 1801–1843)
and phyllotaxis, 1007

Bravais lattices, 929

Bray, William C. (USA, 1879–1946)
and oscillatory chemical reactions, 1013

Breadth-first recursion
in substitution systems, 1033

Breakdown
as source of randomness, 302, 970
of vacuum, 1062

Breakers
patterns of, 997

Breeding season
bird songs in, 1180
whale songs in, 1180

Bresenham's algorithm, 916

Bricks patterns
and CA updating, 885
as origin of ornament, 872
see also Block cellular automata

Brillouin zones, 987
and CA lattices, 929

British Museum, 873

Brittle materials, 994

Broadband noise, 586
in electronics, 968
and SETI, 1189

Broadcasting
and extraterrestrials, 836

Broadwell, James E. (USA, 1921–[2018])
and CA fluids, 999

Broccoli shape, 385

Broglie, Louis-V.-P.-R. de (France, 1892–1987)
and wave-particle duality, 1056

Bronchioles
branching pattern of, 413, 1008

Bronze Age ornament, 873

Brouwer, Luitzen E. J. (Netherlands, 1881–1966)
and character of math, 1176

Brownian motion
randomness in, 302
see also Random walks

Bruns, E. Heinrich (Germany, 1848–1919)
and three-body problem, 972

Bubbles
as artificial-looking, 828
in boiling, 994
in evolving foams, 1039

Buch, Arnim (Germany, 1969– )
and automated proofs, 1158

Buchberger, Bruno (Austria, 1942– )
and Gröbner basis approach, 1037
in Preface, xiii

Buckling
and chaos theory, 971

Buddhism, 1196

Buffon's needle (for evaluating π), 1192

Bugs
in CA programs, 866
in first universal TM, 1119
intuition from, 46, 872
and proofs about programs, 1168
in proofs of universality, 1117
in purposeful CA, 1185
in random generators, 320
in theorems, 899

Buildings
purposes of early, 1184

Built-in cellular automaton function, 867

Bumpy roads
and chaos theory, 304

Buntrock, Jürgen (Germany, 1958– )
and long-running TMs, 889

Burger's equation, 925

Burgess Shale fossil, 385

Burks, Arthur W. (USA, 1915–[2008])
and cellular automata, 876
in Preface, xiii

Bush, Vannevar (USA, 1890–1974)
and differential analyzer, 1107

Business cycles
iterated maps as models of, 918
theories of, 1015
and time series, 1083

Business systems
and complexity research, 863

Busy Beaver Problem
and growth rates, 1163
for register machines, 896
for symbolic systems, 897
for Turing machines, 889, 1144

Butterflies
opposite wings of, 1013
pigmentation patterns of, 389

Butterfly network, 905

Byzantine style, 873