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

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

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