# Index

Neumann, Bernhard H. (England/Australia, 1909– )

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