# 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

Pi_2 questions, 1126

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