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

Notes (musical), 585, 1080

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