Index
Pi (π)
approximations to, 912
block frequencies in digits, 594
Buffon's needle and, 1192
computation of nth digits in, 912
continued fraction for, 143, 914
difficulty of evaluating, 1134
digit sequence of, 136
as early example of complexity, 48
frequencies of digits in, 912
generating as purpose, 1185
and history of randomness, 967
and random networks, 963
rational approximations to, 1134
from rational integral, 916
as rule 60 initial condition, 1091
and SETI, 836, 1190
Π2 questions, 1126
Πn sets, 1139
Piaget, Jean (Switzerland, 1896–1980)
and animism in children, 1195
Piano
CA cells as keys on, 869
frequencies on, 1079
Pictures
as alternative to notation, 853
deductions from, 577
printing of in this book, 852
Pie charts
of classes of behavior, 948
Piecewise linear maps, 921
Piecewise linear spaces (cell complexes), 1050
Piezoelectricity
as element in technology, 1195
Pigmentation patterns (of organisms), 422–429
communication through, 1181
and complexity in biology, 384
randomness in, 970
in similar organisms, 389
Pilot waves (hidden variables), 1058
Pinball
and randomness from initial conditions, 312
Pinecones
phyllotaxis in, 409
Pingala (India, ~200 BC)
and Fibonacci numbers, 890
Pingala's method
for computing powers, 1093
Pink (1/f) noise, 969
see also 1/f noise
Pioneer 10 spacecraft, 1189
Pions (in particle physics), 1057
Pipelining
in CA implementation, 868
Pippenger, Nicholas J. (USA/Canada, 1947– )
and NC computations, 1149
Pitch
in auditory perception, 585
Pitting (hoppering) in crystals, 993
Pitts, Walter H. (USA, 1923–1969)
and neural networks, 880, 1099
and universality, 1110
Pixels
in bitmaps, 1108
displays made from, 46
and printing of this book, 852
PKZIP (compression program), 1069
Planar Feynman diagrams
and QCD, 1040
and quantum gravity, 1054
and random networks, 1039
Planarity
vs. dimension for networks, 1038
generalizations of, 1045
and network evolution, 515
particles and in networks, 526
Planck, Max K. E. L. (Germany, 1858–1947)
and quantum theory, 1056
Planck length
and discrete space, 1027
in early universe, 1056
Planck's constant, 1061
Plane geometry
axioms for, 774
Plane waves
in QCD, 1061
superpositions of, 984
Planes
in linear congruential patterns, 974
Planetary nebulas, 1187
Planets
as approximate spheres, 1187
extrasolar, 1179
formation of, 455
new and gravity theory, 1047
orbits and role of God, 861
rules for motion of, 860
as systems modelled, 366
in three-body problem, 973
Plankton
forms of, 1011
Planning
and defining intelligence, 1178
Plant breeding
as randomized algorithm, 1193
Plant geography
and branching types, 1004
Plants
classification of, 1004
diversity of pollen in, 1011
growth compared to animals, 420
growth of, 400–413
and history of substitution systems, 893
hormones in, 404
hybrids of, 1193
as models for extraterrestrials, 1190
as origin of ornament, 872
shapes of and math, 859
symmetries of, 1007
Plaque
on Pioneer 10 spacecraft, 1189
PLAs (Programmable Logic Arrays), 1095, 1097
Plasma dynamics
and electric breakdown, 995
and natural radio emissions, 1187
and pulsar signals, 1188
Plato (Greece, 427–347 BC)
and microcosm, 1196
and mimesis, 1178
and the nature of space, 1028
and primes, 909, 910
and purpose in nature, 1185
Platonic solids
proof of in Euclid's Elements, 1176
Platonism
as foundation of math, 1176
Play
in audio representation of cellular automata, 869
Player pianos
and history of universality, 1110
as programmable machines, 1107
Plot3D
metric for surface in, 1048
Plouffe, Simon (Canada, 1956– )
and computation of π, 912
in Preface, xiii
Pluperfect numbers, 911
Plus (+)
combinator for, 1122
and NC computations, 1149
primitive recursive definition of, 907
see also Addition
PN (pseudonoise) sequences, 1084
see also Shift registers
Podolsky, Boris (USA, 1896–1966)
and EPR experiment, 1058
Poetry
and Fibonacci numbers, 891
rules in, 875
Poincaré, J. Henri (France, 1854–1912)
and 3-body problem, 972
and cell complexes, 1050
and chaos theory, 971
and iterated maps, 918
and notion of complexity, 1068
and Poincaré recurrence, 1022
Poincaré disk (negatively curved space), 1049
Poincaré recurrence
in cellular automata, 267
and thermodynamics, 1022
Point defects, 1045
Point location
and Voronoi diagrams, 987
Pointer-based encoding, 565
implementation of, 1071
and memory, 1100
Pointers
and hashing, 622, 1100
in implementation of CAs, 866
Poisson's equation
and Einstein equations, 1052
Poker test, 1085
Polar plots
and shapes of leaves, 1006
Polarization
and Bell's inequalities, 1064
as spin direction, 1046
Poles (in complex plane)
undecidability of, 1177
Polish notation
for expressions, 896
in logic, 1173
Political boundaries
as visible from space, 1187
Political history
and human languages, 1103
Politzer, H. David (USA, 1949– )
and particle masses, 1047
in Preface, xiv
Pollard, John M. (England, 1941– )
and integer factoring, 1090
Pollard rho method, 1090
Pollen
and Brownian motion, 302
and circle packings, 985
forms of, 385, 1011
Polling
as application of randomness, 1192
Pólya, George (Hungary/Switzerland/USA, 1887–1985)
and zeta function zeros, 918
Polyadic groups, 1171
Polycrystalline materials, 993
PolyGamma (polygamma functions)
from sums, 917
Polygenes, 1003
Polygons
and constructible reals, 1129
produced by 2D CAs, 929
regular allowing tilings, 943
in Voronoi diagrams, 987
Polyhedra
as Plato's model for space, 1028
as shapes of dice, 971
as shapes of pollen grains, 1011
in Voronoi diagrams, 987
PolyLog (polylogarithms)
and computing nth digits, 912
and Feynman diagrams, 1060, 1133
as special functions, 1092
POLYLOGTIME
and P completeness, 1149
Polymers
hydrocarbon, 1194
as self-avoiding walks, 978
smell of, 1105
Polynomial algebra
axioms for, 1153
Polynomial equations
and algebraic numbers, 916
and EllipticTheta, 1092
lack of universality in, 731
solutions to, 912
see also Quartic equations
see also Quintic equations
Polynomial factoring
see Factor
Polynomial growth
in substitution systems, 890
Polynomial space (PSPACE), 1142
Polynomial time (P) computations, 762, 1142
and cryptography, 1086
and defining randomness, 1068
PolynomialMod
and additive CAs, 951, 1094
and rule 90, 870
and shift registers, 975
PolynomialReduce
for Boolean minimization, 1096
PolynomialRemainder
and lists with flat spectra, 1081
Polynomials
and additive CAs, 610, 951
canonical forms of, 1037
and continued fractions, 914
and difference tables, 1091
digit sequences from, 914
as generalizing numbers, 1168
generating primes with, 909
iterated, 1098
iteration to find roots of, 1101
machines for computing, 1107
as models, 1083
and nested patterns, 610
sets of values taken on by, 1161
and shift registers, 975
universal, 1161
Polyominoes, 943
Polytopes
in color space, 1074
and trivalent networks, 1029
Pomeau, Yves (France, 1942– )
and cellular automaton fluids, 999
in Preface, xiii
Pompeii
maze patterns at, 873
Pond snail shell
growth of, 415
Ponzano, Giorgio E. (Italy, 1939– )
and spin networks, 1055
Popcorn
segregation of sizes in, 986
Popper, Karl R. (Austria/New Zealand/England, 1902–1994)
and free will, 1135
Popping
in natural radio emissions, 1187
Population count (DigitCount), 902
Population studies
and history of complexity, 861
and history of statistics, 1082
Pores in sphere packings, 986
Posets (partially ordered sets), 1040
as example in lattice theory, 1153
Position
and aggregation models, 978
basic example of, 853
and nested patterns, 931
Positional information
in embryo development, 1010
Positional notation
for numbers, 116, 1182
Positivism
and character of math, 1176
and Frege, 1149
and logic as a foundation, 860
and math in science, 859
and theories of communication, 1181
Post, Emil L. (USA, 1897–1954)
and axiom systems in logic, 1170
and models of computation, 879
and models of math, 1150
and multivalued logic, 1175
and multiway systems, 938
and origins of universality, 1110
and Post Correspondence Problem, 1139
and tag systems, 879, 894
and truth tables, 1170
and undecidability, 1136
and undecidability of word problem, 1141
and underivability of logic axioms, 1170
and universality, 1125
Post Correspondence Problem (PCP), 757, 1139
density of difficult instances of, 1147
Post tag systems
see Tag systems
Postmodernism, 1196
Post's problem
and intermediate degrees, 1130
PostScript (page description language)
and computer communication, 1182
and production of this book, 852
Power
see Powers
Power cellular automata, 1093
Power-free sequences (repetition-free sequences), 944
Power laws
for crushed rock, 995
and fractal dimensions, 933
in spectra, 969
for turbulent fluid flow, 997
Zipf's law as example of, 1014
Power lines
radio emissions from, 1188
Power of axiom systems
and ordinal numbers, 1163
Power spectra
of natural processes, 969
properties of, 1080
see also Spectra
Power towers
and Ackermann function, 906
and symbolic systems, 897
Power trees, 615
PowerMod
and randomized primality testing, 1192
and RSA cryptography, 1090
Powers
combinator for, 1122
of complex numbers, 1094
computation of, 615, 1093
computational reducibility in, 749
digit sequences of, 119, 614, 749
encoded as integer equation, 1161
fractional parts of, 121, 903
and linear congruential generators, 318
with nearby values, 1166
in ordering of math constructs, 1177
and primitive recursion, 907
see also Arrow function (nested power)
Powers of 2
cellular automaton for, 614, 749
Powers of 3
cellular automaton for, 661
digits in, 119, 903
and linear congruential generators, 318
Powers of 3/2
in continuous CAs, 157
digits in, 903
Powersets
and cardinality of reals, 1127
in finite set theory, 1171