Coal
and interesting chemicals, 1194
Coarse-graining
and defining randomness, 1068
history of, 1020
in thermodynamics, 448
Coarsening
in cellular structures, 1039
Coastlines
origin of shapes of, 1001
Coats of animals
patterns on, 426
Cobol
and history of computing, 1108
Coccolithophorid
shape of, 385
Cocconi, Giuseppe (Italy/USA/Switzerland, 1914- )
and SETI, 1189
Cochlea
and audio perception, 1079
Cochrane, Canada
and patterns from space, 1187
Cockle shell
growth of, 415
Codd, Edgar F. (USA, 1923-[2003])
and universal CAs, 1117
Code
in notes to this book, 854
see also Programs
Code (hash), 622
Code (machine), 101
Code 10
and my CA history, 882
Code 12
and Ulam systems, 929
Code 20
attractors in, 958
as candidate for universality, 1115
excluded blocks in, 958
halting probability in, 964
persistent structures in, 281, 284
transient lengths in, 964
Code 52
as candidate for universality, 692
phase transition in, 981
Code 52 (2D)
domains in, 980
Code 111 (2D)
domains in, 980
Code 177
randomness from, 64
Code 204 (2D)
self-reproduction in, 824
Code 224 (2D)
see Game of Life
Code 237
nesting in, 65
Code 293 (2D)
domains in, 980
Code 294
localized structures in, 526
Code 295 (2D)
domains in, 980
Code 357
persistent structures in, 282, 286
from simple seed, 69
Code 420
as additive CA, 886
nesting in, 63
Code 468 (2D)
isotropy in, 473
Code 600
repetition in, 62, 69
Code 686
and Ulam systems, 929
Code 686 (2D)
isotropy in, 473
Code 746 (2D)
circular shape from, 178, 334, 979
interior of, 929
isotropy in, 473
Code 843
and computational reducibility, 738
Code 867
examples based on, 868
Code 870
and computational reducibility, 738
Code 912
randomness in, 64
Code 920 (2D)
domains in, 980
Code 942 (2D)
nested pattern from, 171
slices through, 928
Code 948
nesting in, 65
Code 976 (2D)
domains in, 336, 980
phase transition in, 340
Code 1041
complex behavior in, 66
Code 1329
persistent structures in, 282
from simple seed, 62
Code 1599
complex behavior in, 69, 70
and computational irreducibility, 738, 740
and free will, 750
Code 1635
complex behavior in, 66, 67
Code 1659
class 4 behavior in, 238
Code 1749
nesting in, 65
Code 1815
class 4 behavior in, 236
and universality, 692
Code 1893
localized structures in, 526
nested domains in, 360
Code 2007
class 4 behavior in, 237
Code 2040
randomness in, 64
Code 2043
class 4 behavior in, 239
Code 2049
complex behavior in, 66, 68
Code 2058
from simple seed, 69
Code 3702 (2D)
examples based on, 868
Code 29408
shape produced by, 980
Code 174826
shape produced by, 929, 980
Code 175850
shape produced by, 980
Code 1004600
and undecidability, 754, 1137
Code books
and cryptography, 1085
in sound compression, 1080
Codes
error-correcting, 1101
Huffman, 564
Shannon-Fano, 1069
for totalistic CAs, 60
for Turing machines, 888
see also Cryptography
Codewords
in block encoding, 563
in error-correcting codes, 1101
self-delimiting, 1071
Coding theory
algebraic, 1101
and block emulations, 1119
CoefficientList
and Sierpinski pattern, 931
Coffee grains, 986
Cognition
see Thinking
Cogs
characteristic shapes of, 1183
Cohen, Paul J. (USA, 1934- )
and continuum hypothesis, 1155
Coherence
and definition of purpose, 830
and human will, 1136
Coherent states (in quantum theory), 1059
Coherent structures
in QCD, 1061
in turbulent fluids, 997
see also Localized structures
Coiling
in animals, 413
Coin tossing
randomness from, 305, 971
in water, 971
Coincidences
and randomness, 967
Coins
maze patterns on, 873
packing of identical, 349
Cold War
and beliefs about SETI, 1191
Collagen
repetitive structure of, 1003
Collatz problem, 904
see also 3n+1 problem
Collect
analog in Boolean formulas, 1095
Collective behavior
general theory of, 3
Collectives
and defining randomness, 1068
Collisions
and chaos theory, 971
on inspirational cover, 17
law for in rule 110, 964
of planets, 973
in rule 110, 684
of structures in rule 110, 294
and thermodynamic model, 445
Colonization of galaxy, 839
Color
and pictures in this book, 851
vision, 577, 1074
Color charges
and QCD, 1057
Coloration of animals, 426, 1012
Coloring of networks, 1029, 1031
Combinatorial chemistry, 1193, 1194
Combinatorial optimization, 985
Combinatorial physics, 1027
Combinatorial topology, 1051
Combinatorics
posets in, 1041
and substitution systems, 893
undecidability in, 1138
Combinators
behavior of, 712
emulating cellular automata, 1123
emulating rule 110, 713
halting in, 897
history of, 1121
and history of universality, 1110
as idealization of math, 1150
and network systems, 936
as precursors to my work, 879
properties of, 1122
single universal, 1123
and symbolic systems, 102, 898
as symbolic systems, 711
as universal systems, 711
and variables in axioms, 1156
Combinatory algebra, 1172
Comet orbits
and Gaussian distribution, 977
Common subexpressions
in equation solutions, 945
in multilevel logic, 1096
and networks, 1040
and speedups, 1094
Communication
animal, 1180
between computers, 1182
and definition of intelligence, 826
of effects in CAs, 252
with ETs in science fiction, 1191
theories of, 1181
and use of language, 630
Communications systems
and data compression, 549, 560
and layout of networks, 1031
and shift registers, 878
simulations of, 968
and theories of communication, 1181
Commutative
see Orderless
Commutative Boolean functions, 1173
Commutative diagrams
in category theory, 1154
Commutative groups
axioms for, 773, 1153
decidability for, 1160
enumeration of, 805
and forcing by axioms, 1172
incompleteness of theory, 1160
shortest axioms for, 806
total number of, 1172
see also Abelian groups
Commutative monoids
enumeration of, 952
and generalized additivity, 952
Commutative rings, 1153
Commutative semigroups
Cayley graphs of, 938
enumeration of, 805, 1173
word problems in, 1141
Commutativity
of And, 817
and generalized additivity, 952
in operator systems, 801
of Or, 817
proof in Nand axioms, 775
and speedups in evolution, 1095
unprovability in reduced arithmetic, 800
Commuting operations
and causal invariance, 1036
|  | Companding
in sound compression, 1080
Comparative anatomy
and studies of form, 967
Competition
between programs, 1105
in phase transitions, 983
Compile
and CA evolution, 865
Compiled languages, 1109
Compiler generators, 1104
Compilers
for functional languages, 898
optimal code searches in, 1193
and register machines, 1114
Compiling
see Emulation
Complement
and finite set theory, 1171
Complement cellular automaton, 883
Complete bases
for data, 1072
for logic, 1173
Complete graphs
and planarity tests, 1045
Completely connected sets
and discrete packings, 987
Completeness
vs. Incompleteness Theorem, 1159
meanings of, 1152
in multiway systems, 782, 797
of number representations, 1070
in predicate logic, 1152
of real algebra, 1154
see also Universality (computational)
Completeness theorem
for equational logic, 1172
for first-order logic, 1167
Completion
algorithms for, 1037
and automated proofs, 1158
in multiway systems, 782
Complex analysis
and growth shapes, 1010
and S matrix theory, 1057
Complex bases, 932
Complex maps, 933, 933'
Complex numbers
and branching patterns, 1005
cellular automata based on, 886
as defining poset, 1041
and multiway systems, 939
not related to complexity, 1069
as number generalizations, 1168
powers of, 1094
and Sierpinski pattern, 931
Complex plane
nested patterns in, 1093
Complex rules
with simple behavior, 351
Complex systems research
and defining complexity, 1069
history of, 20
organizational structure of, 862
Complexity
adaptive value of, 1002
and animism, 845
applications of, 841
biology as prime example of, 383
in biology vs. thermodynamics, 1003
compared to randomness, 557
definition of, 557-559
and definition of life, 824
explaining in biology, 396
explaining phenomenon of, 735-737
formula size as measuring, 1096
history of definitions of, 1068
of human thinking, 628
of individual integers, 916
ingredients for, 1131
limited by natural selection, 392
as limited in biology, 391
of logic circuits, 1096
and lossy compression, 574
of math formulas, 1068
in mathematics, 772
in models, 364
mystery of in nature, 2
and Principle of Computational Equivalence, 719
of proofs in math, 777
from random initial conditions, 228
in rule 110, 39
and science, 861
as special to humans, 844
and theology, 861
of Turing machine rules, 1119
in Turing machines, 709
and universality, 643
Complexity engineering, 882
Complexity theory
history of, 862
summary of relations to, 13
Complexity theory (computational complexity theory), 1142
Composite heads
in symbolic expressions, 896
Compositeness
of elementary particles, 1044
Composition (music)
with substitution systems, 1080
Compositions
of cellular automata, 886
of functions, 896
of polynomials in iterated maps, 1098
Compound leaves, 1005
Compounds
chemical, 1194
Compressible flow (in fluids)
see Supersonic flow
Compression
audio, 1080
of CA patterns, 562
and computational reducibility, 746, 1134
and computer communication, 1182
of data, 560-576
in extraterrestrial signals, 836
lossy, 572
maximal in block encoding, 1071
in mobile automata, 72, 488
and recognition of meaning, 827
software for, 1069
Compton scattering, 1060
Computability
see Decidability
Computable reals, 1128
Computation
analog, 730, 1128
in cellular automata, 638-641
as conceptual foundation, 5
continuous, 730, 1128
efficiency of, 758
math notation for, 1182
minimal systems for specific, 832
not for definite tasks, 715
notion of, 637-714
reversible, 1018
and thermodynamic behavior, 444
thermodynamics of, 1018, 1020
universality as basis for study of, 674
see also Computing
see also Programs
Computation universality
history of, 1109
see also Universality
Computational complexity theory, 758, 1142
and computational irreducibility, 1132
of computing pi, 912
and defining randomness, 1068
and definition of complexity, 1069
of math function evaluation, 1134
and Principle of Computational Equivalence, 766
summary of relations to, 14
Computational Equivalence, Principle of, 715-846
see also Principle of Computational Equivalence
Computational fluid dynamics, 1000
and Navier-Stokes, 996
Computational geometry
and nearest neighbors, 1101
recursive algorithms in, 1142
and Voronoi diagrams, 987
Computational irreducibility, 737-750
and chemistry, 1193
and complexity, 748
and computational complexity theory, 1148
and epistemology, 1196
and extraterrestrial trade, 1191
and free will, 750
and Gödel's Theorem, 788
history of, 1132
and human responsibility, 1136
and intractability, 758
introduction to, 6
and limits of science, 1135
in mathematics, 779
my discovery of, 881
in operator systems, 815
origins of, 1133
and Principle of Computational Equivalence, 738
in QED, 1060
and three-body problem, 972
ubiquity of, 745
and weather prediction, 1178
Computational learning theory, 1102
Computational neuroscience
and visual perception, 1076
Computational reducibility, 738
in additive CAs, 1094
and associative evolution, 1094
as basis for existing science, 741
and compression, 746
and engineering, 829
and exact solutions, 1133
examples of, 744, 747
in network of theorems, 821
and regularities, 746
Computational science, 44
Computational work
and computational irreducibility, 739
Computer-aided design (CAD)
and discrete surfaces, 1050
Computer algebra
and computer experiments, 899
and Feynman diagrams, 1057
and gravity theory, 1048
see also Algebraic computation
Computer art, 11
Computer-assisted proofs
see Automated theorem proving
Computer experiments
basic, 23
and chaos theory, 899
and computational irreducibility, 1132
and continuous systems, 167
and ergodicity, 1020
and iterated maps, 919
lack of meaningful, 898
and learning about this book, 856
methodology of, 108-113
my first on CAs, 880
my need to do more, 20
on natural selection, 1002
problems with chaos in, 919
and solitons, 899
and symbolic computation, 899
and theorems, 899
for this book, 46, 111, 854
Computer graphics
and discrete surfaces, 1050
and history of modelling, 992
and models of plant growth, 1005
and models of shell shapes, 1008
and nesting, 934
and substitution systems, 893
surface roughness in, 996
textures in, 1077
use of randomness in, 841, 1192
Computer interfaces
graphical vs. language, 631
history of, 1102
Computer languages
and context-free grammars, 939
and history of computing, 1108
and human thinking, 627
influence on thinking of, 1181
logic primitives in, 1173
and P equivalence, 764
redundancy in, 1086
and universality, 642
see also Languages (computer)
Computer programs
in notes, 853
see also Programs
Computer science
education and this book, 855
structure of algorithms in, 990
summary of relations to, 10, 863
undecidability in, 1138
Computer simulations
see Simulations
Computerized data taking, 992
Computers
communication between, 1182
and definition of intelligence, 822
and discoveries in this book, 46
free will for, 1135
future of, 1196
future technology of, 841
historical cost of using, 45
and history of CAs, 876
physical components in, 1195
quantum, 1147
randomness in, 970
and rule-based systems, 860
and universality, 642
used in creation of book, 854
Computing
causal invariance in distributed, 1035
history of, 1107
intuition from, 40, 46, 872
number representations in, 1070
see also Computation
|
Send a Message
