Index
Mesh generation
and discrete spaces, 1050
and Voronoi diagrams, 987
Mesons (in particle physics), 1057
spins of, 1046
Mesoscopic systems
and quantum theory, 1058
Metabolism
and definition of life, 1178
Metamathematics, 1150
empirical, 1176
and Gödel's Theorem, 1158
Metaphysics
implications for, 1196
Metastable states
and phase transitions, 341
and quantum measurement, 1063
Meteorites
and origin of life, 1179
Meteorology
and history of chaos theory, 971
Meter
speed of light and defining, 1041
Meter in poetry
rules for, 875
Methane, 1194
Method of lines
for PDEs, 924
Methodology
of computer experiments, 108
and definition of math, 860
development of my, 21
of math in science, 859
for studying sequences, 1091
in this book, 1193
Metric
in differential geometry, 1048
for Lorentzian spaces, 1051
for numerical data, 1101
Riemann tensor expansion of, 1049
in space of CA rules, 948
in space of CA states, 869
in unified field theory, 1028
volume density from, 1050
Metric spaces
networks as, 1030
Metric tensors, 1048
Metrics
for complexity of software, 1069
Michelson, Albert A. (USA, 1852–1931)
and experimental math, 899
and Michelson–Morley experiment, 1041
Michelson–Morley experiment, 1041
Microcanonical ensemble
for 2D Ising model, 982
Microcosm, 1196
Microorganisms
random motion of, 970
Microprocessors
randomness instructions in, 970
Microsoft Windows
and creation of this book, 854
Microspine
pattern from, 385
Microwave background radiation
see Cosmic microwave background
Middle A
frequency of, 1079
Middle Ages
animism in, 1195
concept of microcosm in, 1196
understanding of nature in, 876
Middle-square method, 975
for molecular dynamics, 864
Midwest
field patterns in, 1187
Mie scattering
as exactly soluble, 1133
Military camouflage, 1077
Military cryptography, 1085
and shift registers, 878, 1088
Military drill
use of rules in, 875
Military GPS (P-code), 1086
Military secrets
and history of complexity, 49
Military SETI, 1188
Military vehicles
use of randomness by, 1192
Millen, Jonathan K. (USA, 1942– )
and code 20 CA, 877
Miller, Stanley L. (USA, 1930–[2007])
and origin of life, 1179
Miller–Rabin algorithm (for PrimeQ), 1192
Millipedes
locomotion patterns of, 1011
Mimesis, 1178
Mind
see also Brain
see also Thinking
Mind-body problem, 1197
Minds
of extraterrestrials, 1191
and free will, 1135
in inanimate objects, 822
and theories of communication, 1181
Mineralogy
and forms of crystals, 993
Minimal surfaces
computing forms of, 1009
and deformable packings, 988
vs. Einstein equations, 1052
and general study of form, 967
and radiolarians, 1011
as shapes of exoskeletons, 1011
Minimal systems
for particular purposes, 1186
for particular sequences, 1186
see also Shortest programs
Minimal theories, 1186
Minimality
and recognition of purpose, 831
Minimization
of Boolean formulas, 617, 1095
of energy, 940
of finite automata, 957
as model of drainage, 1001
of multilevel logic, 1096
and variational principles, 1185
Minkowski, Hermann (Germany, 1864–1909)
and relativity theory, 1042
Minkowski space, 1051
and quantum field theory, 1061
as solving Einstein equations, 1053
Minors (in networks), 1045
Minotaur
home of the, 873
Minsky, Marvin L. (USA, 1927–[2016])
and discreteness of space, 1027
in Preface, xiii
and register machines, 896, 1115
and simple Turing machines, 879, 889, 1143
and tag systems, 1120
and universal Turing machine, 1115, 1119
Miracles
and ultimate theory of physics, 1025
Mirror
as amplifier, 310
Mises, Ludwig E. von (Austria/USA, 1881–1973)
and free will, 1135
Mises, Richard von (Austria/USA, 1883–1953)
and defining randomness, 1068
Missiles
radar pulses used by, 970
MIT
and my work on CAs, 880
and Paterson worms, 930
and precursors to my work, 879
and work on nesting, 934
Mitotic cell division, 970
Mixed states (in quantum theory), 1062
Mixing
of initial conditions in rule 30, 976
Mobile automata, 71–77
2D, 931
2D and causal networks, 1033
active cell motion in, 887
causal-invariant systems for, 1033
causal networks from, 1033
emulated by CAs, 657, 1111
emulating CAs, 664, 1112
experiments on, 112
generalized, 76
implementation of, 887
implementation of generalized, 887
on networks, 1040
random initial conditions in, 949
reversible, 1018
and time in universe, 486
Möbius transformations
and complex maps, 933
and continued fractions, 914
and elliptic functions, 1093
Mod (modulo)
and algebraic forms for CA rules, 885
basic example of, 854
and computational reducibility, 747
computed by rule 132, 638
and cyclic addition systems, 950
difficulty of evaluating, 1134
emulated by continuous functions, 1129
encoded as integer equation, 1160
and formulas for repetition, 607
and idealized billiards, 1022
and primitive recursion, 907
in rolling motion, 971
TMs to compute, 1144
Mod 1
uniform distribution, 904
see also FractionalPart
Mod 2 rule, 25
see also Rule 90
Mod k rules, 870, 952
see also Additive cellular automata
Modal logic, 1158
Model theory (in mathematical logic), 1172
of operator systems, 805
and Peano arithmetic, 1169
Models
based on grammars, 1084
based on programs, 860
compared to reality, 991
complexity of, 1068, 1083
of data, 550
and epistemology, 1196
general issues about, 363–369, 857
history of making, 992
of mathematics, 776
mechanistic for physics, 1026
origins of physical, 1025
personal experiences of, 991, 992
and Principle of Computational Equivalence, 728
probabilistic, 588
programs as more than, 434
rarity of new, 368
undecidability in, 1138
of universe, 466
see also Ultimate theory of physics
see also Simulations
Modems
data compression in, 1070
Modes
in PDEs, 988
Modesty
and clarity of explanation, 849
Modular addition, 255, 950
state transition graphs for, 961
Modular functions
difficulty of evaluating, 1134
and nested patterns, 1093
Modular groups, 933
Modular multiplication, 257, 950
state transition graphs for, 961
ModularLambda
and nested patterns, 1093
Modulo arithmetic
system based on, 255
see also Mod
Modus ponens, 1150, 1151
and equational axioms, 1151
and equivalential calculus, 1170
and implicational calculus, 1170
MoebiusMu
difficulty of evaluating, 1134
and distribution of primes, 910
and maximal periods, 950
Moire patterns, 1078
Molding profiles
as examples of patterns, 874
Molds
and self-reproduction, 1179
Molecular biology
and complexity in biology, 390
and recognition of purpose, 1184
Molecular chaos assumption
and H theorem, 1020
Molecular dynamics
and cellular automaton fluids, 378
computer simulations of, 999
fluid equations from, 996, 999
and fracture processes, 995
and inspirational book cover, 864
as precursor to my work, 879
Molecules
and Brownian motion, 302
defining life, 1178
in fluids, 376
idealized in CA fluids, 379
and quantum theory, 1056
in smell, 1105
unpredictable properties of, 1194
vibrational modes of, 1081
Mollusc shells
see Shells
Molluscs
classified by shell patterns, 1012
pigmentation patterns of, 389
Moments of data, 1083
Moments of inertia
and isotropy, 980
Momentum
basic mechanism for, 537
Momentum conservation
in 2D cellular automata, 1024
in cellular automaton fluids, 379
in Einstein equations, 1052
in network evolution, 529
in physics, 1022
Monadic pure predicate logic, 1152
Monads
models for space with, 1028
Monasteries
ornamental art from, 873
Monocotyledons (plants)
branching in, 1004
symmetries in, 1007
Monoids
axioms for, 773
enumeration of, 805
and generalized additivity, 952
and multiway systems, 938
vs. semigroups, 1153
universality of, 1159
Monolith in 2001, 1183
Monopodial branching (in plants), 400
Monotheism
and rejection of animism, 1195
and teleology, 1185
Monster Group, 938
and sphere packings, 987
Monte Carlo methods
aggregation systems as, 332
as application of randomness, 1192
for CA conservation laws, 1022
and computational irreducibility, 1132
and digit reversal, 905
in Ising models, 982
in lattice gauge theories, 1061
and probabilistic models, 1083
quasi-randomness in, 1085
for satisfying constraints, 344
and stochastic models, 968
Moon
circular craters on, 1187
circular shape of, 861, 875
computing orbit of, 313, 1107
sending signals to, 1189
supposed life on, 1180, 1190
and three-body problem, 972
times of rising of, 973
Moore, Cristopher (USA, 1968– )
and P completeness, 1149
Moore, Edward F. (USA, 1925–[2003])
and 2D cellular automata, 928
Moore neighborhood (for 2D cellular automata), 177, 928
Moorish (Islamic) art, 874
Moral responsibility, 1136
Moral theories
and free will, 1135
Moray eel
pigmentation pattern of, 426
Mordell conjecture, 1164
Mordell equation, 1165
Morning glory leaves, 1006
Morphisms
in category theory, 1154
of words, 82–87
see also Substitution systems
Morphogenesis (in biology), 400–422, 1003
undecidability in models of, 1138
Morphogenesis (of landscapes), 1001
Morphogens, 1004
Morphology
of biological systems, 386
history of, 1004
mathematical, 1077
Morphometrics, 1010
Morrison, Philip (USA, 1915–[2005])
and SETI, 1189
Morse, H. C. Marston (USA, 1892–1977)
and substitution systems, 893
Morse code, 1069
Morse–Thue sequence, 83
see also Thue–Morse sequence
Mortality problem for matrices, 1138
Mosaics, 873
Moseley, Henry (England, 1801–1872)
and shell shapes, 1008
Mosses
growth of, 1004
Motion
absolute, 1042
of class 4 structures, 281
concept of in physics, 521
Motivation
Occam's razor for, 1025
and thinking, 629
Motor skills
memory for, 1102
Mountains
patterns of, 1001
Mouse motion
miles of in creating this book, xiv
as source of randomness, 970
Movie effects
and substitution systems, 893
MP3 sound compression, 1080
Mu-law sound encoding, 1080
μ operator (in general recursion), 907, 1121
Muchnik, Albert A. (Russia, 1934–[2019])
and intermediate degrees, 1130
Mud
and spontaneous generation, 1179
Mug (circular reflector)
caustics from, 984
Mules
as not self-reproducing, 1178
Mullins, William W. (USA, 1927–2001)
and dendritic growth, 993
Multichannel analysis
in SETI, 1189
Multifractals
generalized dimensions for, 959
and history of fractals, 934
Multilayer logic, 1096
Multinomial (multinomial coefficients)
and additive CAs, 1092
patterns generated by, 870
Multiplication
CAs based on generalized, 886
computation of, 1093
in digit sequences, 118
lower bound on, 1143
NC algorithms for, 1142
number of steps required for, 1134
performed by CAs, 661, 1112
recursive algorithm for, 1142
see also Times
Multiplication systems, 257
reversibility in, 1018
state transition graphs for, 961
Multiplication tables
CAs based on, 614, 886
consistent with axioms, 805
for groups, 945, 1172
see also Operator systems
Multiplicative digit sequences, 902
Multiplicative processes
and lognormal distribution, 977
MultiplicativeOrder
and additive CAs, 951, 1133
and cyclic multiplication, 950
difficulty of computing, 1147
and digits of rationals, 912
and linear congruence periods, 974
as period in doubling system, 257
and quantum computers, 1148
Multipole moments
and isotropy, 980
Multiregister machines, 1114
Multiresolution analysis, 1074
Multispin coding (bitwise optimization)
and cellular automata, 866
Multivariate hypergeometric functions, 916, 1092
Multiverse (many-worlds), 1035, 1063
Multiway systems, 204–209
based on numbers, 939
and branching of time, 504
canonical forms in, 1036
causal invariance in, 507
vs. causal networks, 1037
and cell division in animals, 1009
and chemical synthesis, 1194
compared to sequential substitution systems, 204
completion algorithms for, 1037
computational reducibility in, 1134
confluence in, 1036
convergence in, 1036
emulated by predicate logic, 1159
emulated by TMs, 765
emulating multicolor, 1115
equivalences in, 1172
frequency of behavior in, 938
generating Euclidean spaces, 1036
and Gödel's Theorem, 782
halting problems for, 1137
history of, 938
limited size versions of, 939
as models of math, 776
multidimensional, 939
and NP completeness, 1145
vs. operator systems, 1169
and quantum mechanics, 771
random initial conditions in, 949
randomness in, 205
reversible, 1018
sampling of as axiom systems, 795
searching for paths in, 1157
simulation as NP problem, 1142
spacetime networks from, 1036
states generated by, 207
and string matching, 1101
terminating and confluence, 1036
in terms of operators, 1172
undecidability in, 1136, 1137
word problems in, 1141
Multiway tag systems, 1141
and correspondence systems, 1140
Munching foos
as precursors to my work, 879
Munching squares program, 871
Municipal districting
and Voronoi diagrams, 987
Muon
mass of, 528, 1046
models of, 1044
as type of particle, 1043
Murray, James D. (England/USA, 1931– )
in Preface, xiii
and reaction-diffusion, 1013
Muscles
CA models for, 878
control of, 625, 1099
as excitable medium, 1013
patterns of cells in, 385, 1007
randomness in twitching of, 1011
Music
and auditory perception, 585
in bird and whale songs, 826, 1180
chords in, 917
and extraterrestrials, 1191
frequencies in, 1079
grammatical rules in, 875, 1181
and math thinking, 1177
scores from programs, 1080
on Voyager spacecraft, 1190
Musical chairs
randomness in, 968
Musical instruments
and nonlinear oscillators, 971
shapes of, 1183
Mutations (biological)
effects of, 390
Mutual information
and defining complexity, 1069
Mycoplasma bacterium, 1179
Myhill, John R. (USA, 1923–1987)
and firing squad problem, 1035
Myhill–Nerode theorem (minimal finite automata), 957
Mysticism
and combinatorics, 1082
and non-Western thinking, 1196
and universal objects, 1127