Index



MacArthur Foundation, xiii
Mach, Ernst (Austria/Czech., 1838-1916)
     and Mach's Principle, 1047, 1053
     and origins of relativity, 1042
Mach numbers, 997
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- )
     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, 149-155
     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, 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- )
     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 pi 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, 136-144
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, 145-148
     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, 606-620
     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, 772-821
     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- )
     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- )
     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- )
     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