# 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 pi, 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, 997

simplified versions of, 997

singularities in, 923

as subsonic approximations, 997

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