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), 422429
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

Pisot numbers, 903, 1081

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

Planar networks, 195, 1038

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