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), 997
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- )
     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
C (programming language)
     and chaos experiments, 919
     as example of language, 1109
     and history of computing, 1108
     and my first CA experiments, 864
     my use of, 854, 899
     programs for CAs, 865
     and register machines, 101
C curve
     from 1D substitution system, 892
     from 2D substitution system, 190