Index



MacArthur Foundation, xiii

Mach, Ernst (Austria/Czech., 1838–1916)
and Mach's Principle, 1047, 1053
and origins of relativity, 1042

Mach numbers, 996

Machiavelli, Niccolò (Italy, 1469–1527)
and rules for military drill, 875

Machine 1447
function computed by, 761
and longest halting times, 1144

Machine 1507
as complicated TM, 1144
function computed by, 761

Machine 596440
as candidate for universality, 709
properties of, 1120

Machine 600720
behavior of, 763
and longest halting times, 1144
properties of, 1145

Machine code
and history of computing, 1109
and implementation of CAs, 866
of programs by Alan Turing, 1013
and register machines, 97

Machine integers
and linear congruential generators, 974

Machine intelligence, 628, 1099

Machine numbers
for Turing machines, 888

Machines
see also Register machines
see also Turing machines

Machining plans
and Voronoi diagrams, 987

Macintosh
and computer interfaces, 1102

Magic Eye random dot stereograms, 1076

Magic squares
as defined by constraints, 945
for SETI, 1190

Magnetic chaos toys, 1183

Magnetic field
compared to gravitational, 530
and gauge invariance, 1045

Magnetic moments
and size of particles, 1044

Magnetic monopoles, 1046

Magnetization
in Ising model, 981
phase transition in, 981

Magnetosphere
radio signals from, 827, 835, 1187

Magnus, Wilhelm (Germany/USA, 1907–1990)
and word problem for groups, 1141

Mainframes (computers)
random generators on, 320, 974

Maintainability of software
and defining complexity, 1069

Majority cellular automaton
and P completeness, 1149

Majorization of functions (growth rates), 1162

Makanin, Gennadií S. (Russia, 1938– )
and sequence equations, 1141
and undecidable word problems, 1141

Malacology (study of molluscs), 1008

Mallow leaves, 1006

Mammoth ivory, 873

Man
see Humans

Management
of machines that think, 629

Management science
and Boolean networks, 936
and defining complexity, 1069
and history of complexity, 862

Mandelbrot, Benoit B. (France/USA, 1924–[2010])
and branching models, 1005
and computer experiments, 899
and financial processes, 1014
and fractal landscapes, 1001
and fractals, 880, 934
and history of complexity, 862
and Mandelbrot set, 934
in Preface, xiii
and random walks, 990

Mandelbrot set, 934
as precursor to my work, 880
and tree space set, 407, 1006

Manicouagan, Canada
circular crater in, 1187

Manifolds
in differential geometry, 1048
discrete approximations to, 1050
undecidability in equivalence of, 1051, 1138

Manneville, Paul (France, 1946– )
and CA classes, 948
and continuous CAs, 922

Manufacturing
causal network systems for, 1032

Many-fingered time, 1035

Many-to-one mappings, 960

Many-worlds models, 1035
for quantum mechanics, 1063

Map
basic example of, 853

MapAt
and implementing proofs, 1155
and representation of TMs, 888

MapIndexed
basic example of, 853
and causal networks, 1033

Mappings
on Cantor set, 869
cellular automata as, 959
complex, 933
functions as, 898
history of iterated, 918
iterated, 149155
from linear congruences, 974
local and linear, 953
many-to-one, 960
piecewise linear, 921

Marconi, Guglielmo (Italy, 1874–1937)
and SETI, 1188

Margolus, Norman H. (USA, 1955– )
and 2D CA simulators, 928
in Preface, xiii

Mark I computer, 1107

Market research
and random sampling, 1192

Markets
price fluctuations in, 429

Markov, Andrei A. (Russia, 1903–1979)
and sequential substitution systems, 894
and statistics of language, 1181
and undecidability, 1136
and word problem for semigroups, 1141

Markov partitions
and digit sequences, 901

Markov processes, 1084
and 3n+1 problem, 904
and finite automata, 958
and game strategies, 1105
history of, 1181
spectra of, 1081
as statistical models, 590

Markov random fields
and texture discrimination, 1077
and visual perception, 584

Markov systems (sequential substitution systems), 894

Marr, David C. (England/USA, 1945–1980)
and visual perception, 1076

Mars
question of life on, 1179, 1180
sending messages to, 1189
as source of radio signals, 1188

Martin, Olivier C. (USA/France, 1958– )
and additive CAs, 951
as coauthor of paper, 881
in Preface, xii, xiii

Martin-Löf, Per E. R. (Sweden, 1942– )
and randomness, 1068

Martingales (gambling systems), 1068

Marxen, Heiner (Germany, 1957– )
and Turing machines, 889

Masers, natural, 1187

Masking
of sounds, 587
visual with textures, 1077

Mass
of elementary particles, 1046
equality of inertial and gravitational, 1047
in relativity theory, 1041
in Schwarzschild solution, 1053
in ultimate theory of physics, 528

Massey, James L. (USA/Switzerland, 1934–[2013])
and Berlekamp–Massey algorithm, 1087

Massively parallel computers
and history of CAs, 877

Massless particles
and speed of light, 1041
spin states of, 1046

Master equations
in cellular automata, 953

Matching
of networks, 1038
and paramodulation, 1156
of parentheses, 1091
of strings, 1038, 1101

MatchQ (test for matching)
and constraint systems, 941

Material equivalence
as name for Equal, 1173

Material implication
as name for Implies, 1173

Materialism
and free will, 1135

Materials
fracture in, 994
search-based discoveries of, 1193

Mates
and bird songs, 1180

Mathematica
algorithms in discovered by searches, 1193
analysis of internal code of, 1003
and authoring system for book, 852
avoidance of data types in, 898, 1154
axiom systems in, 1150
as basis for discoveries, 46
cellular automata in, 867
chaos experiments with, 919
computation of π with, 911
computation of PrimePi in, 909
computation of PrimeQ in, 909
and computer communication, 1182
and computer experiments, 113, 899
and concept of halting, 1137
confluence of rules in, 1037
creation of, 20
and creation of this book, xii
and creation of this index, 852
curves of math functions in, 145
and definition of math, 859
design of for human use, 1177
diversity of universality in, 644
evaluation order in, 898, 906
as example of language, 1109
and examples in education, 1133
and experimental math, 899
function names in index, 852
general notes about, 853
generic inequality of symbols in, 1169
grammar of, 631
history of my work on, 864, 881
and human thinking, 627
as idealization of math, 1150
infinite loops in, 1137
and math insight vs. proofs, 1156
mathematical functions in, 1092
mathematical notation in, 1104
minimal model for, 102
name of, 859
as necessary skill, 856, 857
as notation for computation, 1182
notations for logic in, 1173
NP completeness in, 1143
number of names in, 1103
number representation in, 1070
operator precedence in, 1150
patterns
see Patterns (in Mathematica)
patterns and network evolution, 1037
patterns and operator systems, 898
and pictures in this book, 851
proofs and design of, 1158
pure functions in, 1121
random programs in, 1183
randomness generation in, 317, 973
scoping of variables in, 1152
and sequential substitution systems, 894
size compared to genomes, 383
structure of, 1103
and structure of proofs, 1155
symbolic expressions in, 896
theorem proving and, 1158
theorems about, 1168
thinking in, 1104
ultimate theory of physics in, 468
undecidability in, 1138
as universal system, 642
universality in, 1110
and use of digit sequences, 902
use of hashing in, 1100

Mathematica Book, 853
writing style in, 849

Mathematical constants, 136144

Mathematical equations
as foundation for science, 1
in history of science, 44
see also Equations

Mathematical formulas
and computational irreducibility, 737
and engineering, 829
as results of models, 368
and science education, 1133

Mathematical functions, 145148
as computable, 1128
difficulty of evaluating, 1134
evaluated by CAs, 639
evaluation of as P computations, 1142
interpretation of TMs as, 1144
see also Standard mathematical functions

Mathematical impossibilities, 1137

Mathematical induction, 1152

Mathematical logic
combinators in, 898
and defining complexity, 1068
and DNF, 1097
history of, 1150
and history of universality, 1110
and intermediate degrees, 734
and neural networks, 1099
and problem of free will, 1135
structure of proofs in, 1151
undecidability in, 1138
unfamiliarity of notation in, 853
see also Foundations of mathematics

Mathematical models
history of, 992
and Principle of Computational Equivalence, 728

Mathematical morphology, 1077

Mathematical notation, 1182
grammar of, 1104
influence on thinking of, 1181
for logic, 1173
vs. Mathematica, 853
relations vs. axioms in, 1169

Mathematical physics
functions of, 145

Mathematical theories
distributions of theorems in, 1175

Mathematicizing power
and Church's Thesis, 1126

Mathematics
analysis using, 606620
applied to biological form, 1004
axioms in, 773
as central in education, 855
and continuity of space, 472
definition of, 859
in economic systems, 1015
and extraterrestrial intelligence, 837, 1189
as foundation for science, 1
and history of complexity, 862
history of in science, 5, 859
and human intelligence, 822
idealizations of, 795, 1149
implications for, 772821
invention vs. discovery in, 1176
and models of thinking, 629
new results in this book in, 863
notation in, 853
numbers in, 116
ordering of constructs in, 1177
and PDEs, 161
in physics, 433
vs. physics, 821
self-limiting of, 792
set theory in education, 1154
in social sciences, 9
summary of relations to, 7, 863
and systems with constraints, 221
types of theorems in, 1176
use of rules in, 875
see also Foundations of mathematics

MathieuC (Mathieu function)
asymptotic oscillation of, 917

MathLink
and CA programs, 865
and computer experiments, 899
and creation of this book, 854

Mating
and defining species, 1003

Matiyasevich, Yuri (Russia, 1947– )
and Diophantine equations, 1161
in Preface, xiii
and word problem for semigroups, 1141

Matrices
and 2D substitution systems, 933
and cryptanalysis, 602
as generalizing numbers, 1168
Hadamard, 1073
mappings of, 921
and non-commutative rings, 1153
random, 977
satisfying constraints, 945
and solving linear systems, 940

Matrix mechanics, 1056

Matrix memories, 1101

MatrixPower
and CA entropies, 958
and correlation functions, 1082
and Fibonacci, 890
and substitution systems, 890
and undecidability, 1138

Matter
as distinct from space, 1028
in Einstein equations, 1052
as generating curvature, 532, 536

Mauritania
Richat structure in, 1187

Max (maximum)
as associative, 1094
related to Or, 952

Maximal periods
of cellular automata, 950, 1088
of linear congruences, 974
of random generators, 318
of shift registers, 975
and symmetries, 950

Maximal principles
variational principles, 1185

Maximum entropy method, 1083

Maximum likelihood, 589, 1083

Maximum-of-t test, 1085

Maxwell, James Clerk (Scotland/England, 1831–1879)
and chaos theory, 971
and electromagnetism, 1041
and fluttering of paper, 971
and gauge invariance, 1045
and Maxwell's demon, 1021
and statistical mechanics, 1019
and stochastic models, 968

Maxwell's demon, 1021

Maxwell's equations
as examples of PDEs, 161
and relativistic invariance, 1041
as simple physical models, 1025

May, Robert M. (Australia/USA/England, 1936– )
and chaos theory, 971

Maze designs, 873, 875

Maze-like patterns, 1013
from 2D cellular automata, 427
in code 746, 334
in visual cortex, 1075

Mazoyer, Jacques (France, 1947– )
and firing squad problem, 1035

McCarthy, John (USA, 1927–[2011])
and theorems in Lisp, 1168

McCulloch, Warren S. (USA, 1898–1972)
and neural networks, 880, 1099
and universality, 1110

McCulloch–Pitts models, 1099
and finite automata, 958

McCune, William W. (USA, 1953–[2011])
and axioms for groups, 1153
and axioms for logic, 1151

Mean curvature, 1009

Mean field theory
for cellular automata, 953
and rate equations, 984
for self-avoiding walks, 978

Meander patterns (mazes), 873

Meanders (in rivers), 1001

Meaning
of axiom systems, 797
and intelligence, 826
in languages, 1181
in programs, 1182
and regularity, 1183
of the universe, 1027

Measure entropy
for cellular automata, 959
computing, 1084
spacetime, 960

Measure theory
and defining randomness, 1067

Measurement
in quantum theory, 542, 1062
in thermodynamics, 448, 1020

Measures
and fractal dimensions, 934
and spectra, 1081

Mechanical automata, 1183

Mechanical calculators, 1110

Mechanical computers, 1107

Mechanical devices
as not universal, 643

Mechanical perception, 1105

Mechanical processes
for real numbers, 1129

Mechanical systems
for cyclic tag systems, 895
proofs in, 1157
randomness in, 969
and repetitive motion, 829
self-reproducing, 1179

Mechanical toys
randomness in, 969

Mechanics
and history of mathematics in science, 859

Mechanisms
captured in models, 367
compared to purposes, 830
in programs and nature, 297
for randomness, 299

Mechanistic explanations
for complexity in nature, 861
in physics, 860, 1026

Medians
and robust statistics, 1083

Medical applications, 9, 842

Medicinal plants
leaf shapes for, 1005

Medieval logic, 1151

Mediterranean
patterns of lights around, 1187

Meet (in lattice theory), 1153

Meier, Willi (Switzerland, 1948– )
and cryptanalysis of rule 30, 1087

MeijerG (Meijer G function)
and Integrate, 1177

Meinhardt, Hans (Germany, 1938–[2016])
and patterns on shells, 1012
in Preface, xiii
and reaction-diffusion, 1013

Meiosis, 970

Melting
of ice, 372
as phase transition, 981

Melting points
of alkanes, 1194
difficulty of computing, 1194

MemberQ (list membership test)
in aggregation systems, 978

Memo functions, 869, 906

Memory (animal)
in lower organisms, 623
and shell patterns, 1012

Memory (computer)
emulated by CA, 663
and history of computing, 1108
in practical computers, 1108
and PSPACE completeness, 1142

Memory (extraterrestrial)
in Black Cloud, 1190

Memory (human), 1102
and free will, 753, 1136
and future technology, 1195
and human intelligence, 823
and human thinking, 621
inanimate analogs of, 1178
visual, 623
and weather prediction, 1177

Memory-based encoding, 565

Menger, Karl (Austria/USA, 1902–1985)
and nested patterns, 934

Mental functions, 1099
see also Brain

Menu interfaces, 1102
vs. languages, 631

Mercury
advance of perihelion of, 1047

Meredith, Carew A. (Ireland, 1904–1976)
and axioms for logic, 1175

Meredith axioms
for logic, 808, 1175

Merging
in multiway systems, 937

Meristems (in plants), 409, 1004

Mersenne, Marin (France, 1588–1648)
and primes, 909

Mersenne primes
and perfect numbers, 911

Mertens Conjecture, 910