# 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, 459–464

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– )

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, 400–412

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– )

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 pi), 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