Index
n-body problem
gravitational, 1021
n Log[n] algorithms
and associative evolution, 1095
in automaton minimization, 957
in evaluating powers, 1093
in Fourier transforms, 1074
for multiplication, 1142
for π, 912
for PrimeQ, 1090
in sorting, 1142
in Walsh transforms, 1073
see also Computational complexity theory
Nakaya, Ukichiro (Japan, 1900–1962)
and snowflakes, 992
Name-value pairs, 1182
Named theorems in logic, 817
Names
of functions as symbolic expressions, 896
in the index, 852
lookup by sound, 623
of variables in math logic, 1150
Nand (⊼)
axioms for, 803, 808, 1151
emulated by Life, 1117
expression trees, 619, 1096
forms for cellular automata, 619
interesting theorems for, 819
lengths of proofs involving, 1175
as motivating combinators, 1121
in multivalued logic, 1175
as operation on sets, 1171
and reversible logic, 1098
single axiom for, 808
tautologies based on, 781, 1157
theorems for, 1175
truth table for, 802
as universal function, 807, 1096, 1173
and universality, 1119
words in languages for, 1173
Nanotechnology, 1193
cellular automata and, 841, 869
and human future, 1196
and new forms of perception, 1106
summary of relations to, 15
Napier, John (Scotland, 1550–1617)
and binary numbers, 902
Natural equations (curves defined by curvature), 1009
Natural language
see Languages (human)
Natural language query systems, 1100
Natural order
for Walsh functions, 1073
Natural selection
Biological evolution, 415
difficulties in simulating, 1002
as engineering, 842
vs. engineering, 393
and extraterrestrial life, 1180
as force of limited power, 392
and games, 1104
history of, 1001
and leaf arrangements, 408
as non-math theory, 859
as not producing complexity, 392
of orbits in solar system, 973
as origin of complexity, 383, 861
and pigmentation patterns, 423, 1012
as predictive theory, 397
and Principle of Computational Equivalence, 1002
and purpose, 831, 1185
and shapes of leaves, 404
and shapes of shells, 417, 1008
and shell patterns, 425
summary of relations to, 14
and teleology, 1185
vs. thermodynamics, 1003
value of intelligence in, 1191
Natural theology
and history of complexity, 861
and intelligent universe, 1195
Nature
compared to artifacts, 40, 828, 967
computations in, 716
mimicked by technology, 1193
undecidability in, 1138
universality in, 718
Nature
article of mine in, 882
Nature's God, 1196
Nautilus shell
chamber structure of, 1008
growth of, 414
shape of, 385
Navier–Stokes equations, 996
and computational fluid dynamics, 1000
vs. Einstein equations, 535
next-order corrections to, 996
simplified versions of, 997
singularities in, 923
as subsonic approximations, 996
in two dimensions, 999
Navigation beacons
radio signals from, 1188
NC (computational complexity class), 1142, 1149
and Boolean minimization, 1096
NDFA (non-deterministic finite automaton), 957
see also Finite automata
NDSolve
and curves from curvature, 1009
difficulty of evaluating, 1134
and PDEs, 924
and Sitnikov problem, 973
and three-body problem, 972
NDTM
see Non-deterministic Turing machines
Nearest-neighbor algorithms, 1101
Nebulas
patterns in, 835, 1187
Necklaces
and maximal periods, 950
and shift rules, 963
Needle
Buffon's for π, 1192
Needle-like crystals, 372
Negation
in multivalued logic, 1175
in multiway systems, 796
notion of, 780, 1158
Negative bases, 902
power CAs and, 1093
Negative numbers
representation of, 902, 942
Negatively curved space, 531
and automatic groups, 1141
and chaos theory, 971
divergence of geodesics on, 1049
and hyperbolic networks, 1049
Negotiations
and price determination, 430
Neighbor-dependent substitution systems, 85–87
Neighbor-independent network rules, 509, 1037
Neighbor-independent substitution systems, 82–85
Neighborhoods
possible in cellular automata, 929
symmetry classes of, 928
Neon discharge tubes
randomness from, 969
Nerve cells, 1075
determinism in, 1135
as excitable media, 1013
and feature extraction, 623
in inner ear, 1079
and mollusc shell patterns, 1012
monitoring with sound, 1080
repeatable randomness in, 976
and song generation in birds, 1180
structure of and free will, 751
in visual system, 578
and Weber's law, 1014
Nest
basic example of, 853
and branching patterns, 1006
constructing expressions with, 897
and lambda calculus integers, 1121
and recursive functions, 1121
Nested expressions, 102
Nested radicals, 915
Nested sequences
block frequencies in, 594, 1084
compression of, 566
as initial conditions, 272, 956
pointer-based encoding of, 1071
shown in scan lines, 892
Nested tilings, 219
Nesting
and 1/f noise, 969
in 2D cellular automata, 171
in 2D substitution systems, 187
in additive cellular automata, 955
in animal skeletons, 420
at phase transitions, 983
and auditory perception, 586
as basis for algorithms, 1141
in biological systems, 384
in bitwise functions, 871
in cellular automata, 25, 57
and circle packings, 986
and computational reducibility, 741
in continuous systems, 1130
in Cosmati mosaics, 873
in curves from curvature, 1009
in cyclic tag systems, 96
and defining arithmetic, 1164
in digit count sequences, 905
in digit sequences, 117, 913
display hacks for, 871, 932
in eddies in fluids, 997
in elliptic functions, 1093
in erosion patterns, 1001
in firing squad problem, 1035
in flocks of birds, 1011
in forms of artifacts, 1183
formulas for, 608
in Game of Life, 965
with general associative rules, 956
history of, 934
and history of math, 735
in Ising model, 983
in iterated maps, 921, 961
and lack of universality, 694, 734
in lists, 931, 989
in mobile automata, 73
in multiway systems, 207, 937
and musical scores, 1080
in networks, 197, 509
in Newton iteration, 1101
and Nim, 939
as only recently familiar, 1106
origins of, 357–360
in ornamental art, 872
in pattern-avoiding sequences, 944
in patterns of cracks, 995
and Principle of Computational Equivalence, 722
from projections of lattices, 932
in quasicrystals, 994
from random initial conditions, 273
recognizing visual, 582
in recursive sequences, 130
in rule 45, 701
in rule 90, 25, 270
in sequential substitution systems, 91
in snowflakes, 371
in sorting networks, 1142
in structure of attractors, 959
in substitution systems, 83
in symbolic systems, 104
in systems based on numbers, 988
in Turing machines, 79, 1119
and visual uniformity, 1078
in Walsh functions, 1073
in Weierstrass functions, 918
see also Fractals
NestList
basic example of, 853
in CA evolution, 865
and random walks, 977
understanding operation of, 1177
NestWhile
and computation of π, 912
and concatenation sequences, 913
and context-free parsing, 1103
and encoding of lists, 1121
and general recursion, 907
NestWhileList
and length prefixed numbers, 1070
and network distances, 1031
Nets of polyhedra, 476
Network constraint systems, 483, 1032
and self-assembly, 1011
Network systems, 193–203
dimensions in, 936
implementation of, 935
random initial conditions in, 949
sequential, 936
Networks
algebraic systems based on, 1172
approximating flat space, 477
approximating spheres, 1049
for attractors, 276
and Boolean functions, 619, 1096, 1097
of CA emulations, 1118
causal invariance for, 515
and Cayley graphs, 1032
cellular automata on, 930, 936
chemical analogies for, 1040
and chemical properties, 1195
and chemical synthesis, 1194
chromatic number of, 1029
circumference of, 1029
colored, 1029, 1039
coloring of and dimension, 1031
coloring of and planarity, 1040
conditions for planarity of, 1045
connectedness of, 1039
of contacts between circles, 986
from continuous space, 533
from continuous systems, 1031
continuum limits of, 1030
and cosmological horizon problem, 1055
curvature in, 532
and cybernetics, 862
de Bruijn, 940
defined by constraints, 482
diameter of, 1029
as difficult to understand, 1177
dimensions of and growth rates, 478
eigenvalues of distance matrix for, 1031
evolution of, 508–515
face distribution in random, 1038
Feynman diagrams as, 1060
girth of, 1029
growth rates on, 1031
homogenous, 1032
implementation of, 1031, 1037
layouts of, 193, 476, 1031
localized structures in, 525, 1045
and Markov processes, 590, 1084
mobile automata on, 1040
as models of space, 475–480
molecules as, 1194
from multiway systems, 209
Nand, 1096
nested, 197
non-overlapping, 515
non-planarity in planar, 527
NP completeness of equivalence of, 1146
NP completeness of matching in, 1038, 1145
NP completeness of path finding in, 1146
number of replacements for, 1038
numbers of trivalent, 1029
overlaps in, 515
planar, 1038
planarity in evolution of, 515
and quantum information, 544
random, 963, 1038
random causal, 1052
random replacements in, 1038
random walks on, 1030
relations between types of, 1037
replacements in directed, 1040
reversible evolution of, 1040
rules for getting to any, 1038
of shift register states, 1089
of signs in languages, 1181
sorting, 1142
state transition, 961
substitution systems, 508–515
symbolic representation of, 1040
symbolic systems based on, 898
and systems theory, 862
of theorems in math, 820, 1176
trivalent as covering all, 476
trivalent examples of, 476
trivalent in 3D, 1030
see also Boolean networks