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

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

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

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