Index
Neumann, Bernhard H. (England/Australia, 1909–[2002])
and axioms for groups, 1153
Neural networks, 1102
for bird songs, 826
for design optimization, 1193
and finite automata, 958
history of, 1099
and history of CAs, 878
and history of statistics, 1083
and history of universality, 1110
and memory, 624
and my work on CAs, 880
as rule-based systems, 860
and undecidability, 1138
and visual perception, 1076
Neurons
in brain, 1098
in cybernetics, 862
properties of, 1075
repeatable randomness in, 976
see also Nerve cells
Neurotoxins
from cone shells, 1011
Neurotransmitters, 1099
Neutral traits, 399
Neutrinos, 1043
identified with gravitons, 1054
limit on number of, 1047
and parity violation, 1019
for SETI, 1189
and speed of light, 1041
Neutron diffusion
Monte Carlo of, 968, 1192
Neutron stars
radio signals from, 835, 1188
New Age movement
and animism, 1195
New moons, 973
New Zealand
circular shape in, 1187
Newcomb, Simon (USA, 1835–1909)
and leading digits, 914
Newell, Allen (USA, 1927–1992)
and automated proofs, 1157
Newspapers
reporting canals on Mars, 1180
Newton, Isaac (England, 1642–1727)
and 2-body problem, 972
and calculus, 901
and color vision, 1075
and computational irreducibility, 1132
and invariance of mechanical laws, 1041
and law of gravity, 1047
and math in science, 859, 860
and nature of space, 1028
in quote by Kant, 861
and theology, 861
Newtonian physics
and determinism, 967
Newton's Laws
character of as principle, 1126
Newton's method
attractor basins in, 1101
for computing square roots, 913
and gradient descent, 985
and iterated maps, 918
as iterative algorithm, 1141
NeXT (computer)
and creation of this book, 854
Nicod, Jean (France, 1893–1924)
and axioms for logic, 1151
Night sky
observed darkness of, 455
and Olbers' paradox, 1021
Nilpotent groups
Cayley graphs of, 1032
Nim (game), 939
Nine-neighbor CA rules, 927
NIntegrate
difficulty of evaluating, 1134
NK models (random Boolean networks), 936
NLS equation, 925
NMR
and quantum computers, 1148
Noise
effect of on transition to turbulence, 996
effect on CAs of, 325, 976
in electronic devices, 302, 968
in natural radio emissions, 1187
produced by crack propagation, 374
radio in galaxy, 836
and time series, 1083
in vacuum tubes, 971
see also Randomness
Nomography (Hilbert's thirteenth problem), 1128
Non-Abelian groups
CAs based on, 887, 956
and charge quantization, 1046
in gauge theories, 1045, 1057
see also Groups (mathematical)
Non-Abelian plane waves, 1061
Non-Archimedean fields
as generalizing numbers, 1168
Non-commutative geometry
and general relativity, 1048
Non-compact groups
and tachyon spin, 1046
Non-computability
of entropies, 958
of fractal dimension, 933
see also Undecidability
Non-computable patterns
from constraints, 943
Non-computable reals, 1128
Non-constructibility
and additive functions, 953
in set theory, 1154
Non-determinism
and multiway systems, 939
Non-deterministic finite automata, 957
Non-deterministic polynomial time (NP), 1142
Non-deterministic Turing machines
and aggregation systems, 979
emulated by CAs, 766, 1146
Non-equilibrium thermodynamics
and history of complexity, 862
Non-Euclidean geometry, 1149
and abstraction in math, 792
and history of space, 1028
Non-locality
and Bell's inequalities, 1064
in digit sequences, 730
Non-measurable sets, 1154
Non-overlapping networks, 515
Non-overlapping strings, 503, 1033
and completion algorithms, 1037
total number of, 1036
Non-periodic crystals (quasicrystals), 994
Non-periodic tilings, 219
Non-standard analysis, 1172
and axioms of analysis, 1155
Non-standard arithmetic, 800, 1169
Non-standard integers
as generalizing numbers, 1168
Non-verbal communication, 1181
Non-Western thinking, 1196
Noncontradiction law
in logic, 817
Nonlinear differential equations
and history of complexity, 862
for ModularLambda, 1093
and special functions, 1092
Nonlinear dynamics
summary of relations to, 15
Nonlinear feedback shift registers, 1088
and cryptography, 1085
and history of CAs, 878
as precursors to my work, 879
see also Shift registers
Nonlinear field theories
topological defects in, 1045
Nonlinear maps
in complex plane, 933
on the interval, 918
Nonlinear models
and time series, 1083
Nonlinear oscillators
arrays of, 921
and history of chaos, 971
Nonlinear Schrödinger equation, 925
Nonlinear wave equations, 165, 923
Nonlinearity
and computational irreducibility, 1133
and equation solving, 940
and interactions in field theory, 1061
in PDEs, 923
Noodles
and chaos theory, 306
Nor (⊽)
as universal function, 807, 1173
words for in languages, 1173
Nordahl, Mats G. (Sweden, 1958– )
in Preface, xiii
and universal CAs, 1115
Normal algorithms (sequential substitution systems), 894
Normal coordinates
and Riemann tensor, 1049
Normal distribution
see Gaussian distributions
Normal forms
in multiway systems, 1036
see also Canonical forms
Normal modes
of nested systems, 1081
Normal numbers, 912
and concatenation sequences, 913
and defining randomness, 1068
Normal ordering (in quantum field theory), 1062
Norms of tensors, 1050
Nose (human), 1105
Not (¬)
in multivalued logic, 1175
and satisfiability, 1146
table for, 806
theorems involving, 817
words in languages for, 1173
Notation
for chemical compounds, 1194
in logic, 1173
mathematical, 1182
for numbers, 1182
for operators, 1182
for symbolic expressions, 896
used in this book, 852
Noughts-and-crosses (tic-tac-toe), 939
Nouns
in human languages, 1103
in mathematical notation, 1182
Novikov, Petr S. (Russia, 1901–1975)
and word problem for groups, 1141
NP (non-deterministic polynomial time), 1142
NP completeness, 766, 1145
and approximate solutions, 984
and automated proofs, 1157
in Boolean minimization, 1096
in cellular automata, 767
and combinatorial optimization, 985
and cryptography, 1086, 1089
density of difficulty in, 1147
of finding addition chains, 1095
of finding discrete packings, 987
of finding network genus, 1045
of finite PCP, 1139
of knot equivalence, 1046
in Mathematica, 1143
and network evolution rules, 1038
and proof lengths in logic, 1175
and proof searching, 1157
and quantum computers, 771, 1148
relation to undecidability of, 769
in rule 30, 770
of satisfiability, 768
and systems in nature, 1146
of tensor simplification, 1048
of tiling problems, 942, 984
Nqthm (theorem prover), 1158
NSolve
difficulty of evaluating, 1134
NTSC television signals
bandwidth of, 1079
Nuclear explosions
and computer simulations, 1133
and extraterrestrial contact, 1190
patterns of, 377
Nuclear physics
and quantum theory, 1056
Nucleation of crystals, 992
Nucleus (atomic)
discovery of, 1044
forces in, 1057
spins of, 1046
NullSpace
and CA conservation laws, 1022
Number classes
and transfinite numbers, 1162
Number conservation
in cellular automata, 458
in cellular automaton fluids, 379
Number representations, 142
and data compression, 561
length prefixed, 1070
in symbolic systems, 897
Number theory, 135
and acoustic diffusers, 1183
analytic, 909
and cryptography, 1090
and Diophantine encodings, 1160
and Diophantine equations, 1164
evaluating functions from, 1134
experimental math in, 899
functions in, 1092
history of, 909
and history of complexity, 862
and history of iterated maps, 919
and linear congruential generators, 974
network of theorems in, 820
and origin of substitution systems, 893
and Peano axioms, 1152
and quadratic congruential generators, 975
spectra in, 1081
and Turing machine 600720, 1145
undecidability in, 791, 1138
unsolved problems in, 1166
Numbering
of CA rules, 866, 883
of TM rules, 888, 1143
Numbers
bases of, 116
chaos theory and, 309
and computational reducibility, 743
equivalence problem for, 916, 1138
generalizations of, 1168
historical notation for, 1182
history of, 901
models based on, 365
natural distributions of, 1070
normal, 912
operator representations for, 916
prime, 132
and Pythagoreans, 859
recognition of, 1089
systems based on, 115–168
tree representations for, 916
Numbers games, 969
Numerical analysis
and chaos experiments, 919
and continuous CAs, 921
for differential equations, 924
and repeatability, 898
Numerical computation
artifacts in, 1184
characterizing difficulty of, 1143
in fluid flow, 996
of gravitational fields, 1053
and history of computing, 1108
and weather prediction, 1178
Numerical data
lookup of, 1101
Numerical integration
Monte Carlo methods in, 1192
searches for optimal algorithms in, 1193
Numerology, 1025
Nuts
segregation of mixed, 986