Index



Mesh generation
and discrete spaces, 1050
and Voronoi diagrams, 987

Mesons (in particle physics), 1057
spins of, 1046

Mesopotamian art, 43, 873

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

mu operator (in general recursion), 907, 1121

Muchnik, Albert A. (Russia, 1934- )
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

Multivalued logic, 814, 1175

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, 957'

Mysticism
and combinatorics, 1082
and non-Western thinking, 1196
and universal objects, 1127

Mythology
as models, 992
and origin of complexity, 861