Index
P = NP problem, 765
and SETI, 1190
and systems in nature, 770
undecidability of, 1146
P (polynomial time), 1142
p-adic numbers
as generalizing numbers, 1168
P-code for GPS, 1086
P completeness, 1149
Packard, Norman H. (USA, 1954– )
and CA classes, 948
as coauthor of paper, 882
in Preface, xiii
Packings
of bits in CA implementation, 866
of deformable objects, 988
discrete, 987
history of circle, 985
and shapes of cells, 1007
of spheres, 349
PadLeft
and initial conditions, 866
Painlevé, Paul (France, 1863–1933)
and Painlevé functions, 1092
Painlevé functions
and 2D Ising model, 982
and nonlinear ODEs, 1092
and random matrices, 977
Paintings
and concept of intelligence, 838
Pair annihilation
and nested patterns, 358
nesting from, 989
Pair correlations
and isotropy measures, 980
Pair production
in vacuum fluctuations, 1062
Pairing functions (σ), 1127
Pairwise sorting algorithms, 1142
Palatine Chapel, 873
Palermo, Sicily, 873
Paley, Raymond E. A. C. (England/USA, 1907–1933)
and Walsh transforms, 1073
Paley, William (England, 1743–1805)
and natural theology, 861
Paley family
of Hadamard matrices, 1073
Paley order
for Walsh functions, 1073
Palindromes
in period-doubling sequences, 892
Palm trees
growth of, 1004
phyllotaxis in, 409
Pangolins
patterns in scales of, 1007
Panini (India, ~500 BC)
and grammars, 875
Pantheism, 1196
and physics as intelligence, 1192
Paper
crumpling of, 996
fluttering of, 971
Paperfolding
and dragon curve, 932
rules in, 875
sequences from, 892
Parabolic reflectors
characteristic shapes of, 1183
Paraboloids
geodesics on, 531
plant stem tips as, 1007
Paradoxes
and Gödel's Theorem, 1159
and history of math, 1149
in set theory, 1154
and undecidability proofs, 1137
Paraffins, 1194
Parallel bit operations, 866
Parallel computation
in cellular automata, 1109
and creation of this book, 854
difficulty of understanding, 1177
and history of CAs, 876
and implementing CAs, 868
and machine intelligence, 1100
of mathematical functions, 1134
and memory lookup, 622
and my work on CAs, 46
and NC, 1142
and network evolution, 1035
and P completeness, 1149
randomized methods in, 1192
of repetition periods, 1147
vs. sequential, 765
in sorting networks, 1142
and work on CA fluids, 999
Parallel postulate
in Euclidean geometry, 1154
Parallel transport (in curved spaces), 1049
on networks, 1051
Parallel universes
and branching in time, 1035
Parallel updating
in CA programs, 866
perceived by observer, 487
Parameter estimation, 1083
Parameter space sets
for activator-inhibitor systems, 428
for animal shapes, 421
for CA patterns, 956
for CA rules, 948
for continuous CAs, 158, 243, 922
for iterated maps, 921
and Mandelbrot set, 934
for shell growth, 415
for shell shapes, 1008
for trees, 405–407, 1006
and universal objects, 1127
Parametric differentiation
as framework for integrals, 1177
Parametric surfaces
in shell models, 1008
Paramodulation
as step in proof, 1156
Parasitism
and biological evolution, 1002
Parastichies (phyllotaxis spirals), 1007
Parentheses
language of balanced, 939, 1103
pattern from balanced, 1091
pattern of balanced, 989
and single combinators, 1123
Paris, Jeffrey B. (England, 1944– )
and unprovable statements, 1163
Paris-Harrington theorem
unprovability of, 1163
Parity function (Xor)
DNF for, 1096
from rule 132, 638
Parity sequence, 83, 890
see also Thue–Morse sequence
Parity violation, 1019
difficult to get from gravity, 1054
Parrots
communication with, 1180
Parsley
shape of cow, 385
Partial differential equations (PDEs), 161–164
for 3D tearing-free growth, 1010
compression of time in, 732
computation with, 732
conservation laws in, 1023
derived from CAs, 1024
Einstein equations as, 1053
emulating cellular automata, 1129
existence of solutions to, 940
for fluid flow, 996
and fracture processes, 995
higher-dimensional, 923
higher-order, 940
and history of CAs, 877
isotropy in, 980
and noisy cellular automata, 976
nonlinear studied by Turing, 1012
origin of, 923
and quantum field theories, 1061
in quantum theory, 1056
for reaction-diffusion, 1012
repetitive behavior in, 988
and self-reproduction models, 876
for solidification fronts, 993
for surfaces from curvature, 1009
and universality, 1129
Partial fractions
as framework for integrals, 1177
Partial functions
general recursive as, 907
in Turing machines, 1143
Partial quotients
in continued fractions, 914
Partially additive rules
repetitive behavior in, 954
spacetime entropies for, 960
Partially ordered sets (posets), 1040
as example in lattice theory, 1153
Particle accelerators
and discovery of particles, 1044
time dilation in, 524
Particle counting
and history of CAs, 877
Particle detectors
Monte Carlo studies of, 1192
Particle physics
my work in, 17, 864
relativistic invariance in, 1043
time reversal violation in, 1019
Particle production
in vacuum field theory, 1062
Particle showers
as examples of nesting, 988
multiway system models for, 938
stochastic models for, 968
Particles
thermodynamic behavior with, 443
see also Defects
see also Elementary particles
see also Localized structures
Partition
and 1D constraints, 940
basic example of, 853
and counting blocks, 1022
and implementation of CAs, 867
and recursive multiplication algorithm, 1142
Partition function
and phase transitions, 981
PartitionsP (number of partitions)
and number of commutative groups, 1172
Parton model
as mechanical model, 1026
Pascal, Blaise (France, 1623–1662)
and arbitrary number bases, 902
and his calculator, 1107
and Pascal's triangle, 870
Pascal's triangle
and associative CAs, 956
for continuous moduli, 922
and encodings of arithmetic, 1164
history of, 870
and nested patterns, 610, 870
as precursor to my work, 878
and prosody, 875
Passerines (songbirds)
songs of, 1180
Passwords
as random seeds, 970
Patch entropies, 960
Patches of texture, 578
Patching
of programs, 872
Patent
related to rule 30, 973
Paterson, Michael S. (England, 1942– )
and 2D Turing machines, 880, 930
Paterson worms
as precursors to my work, 880
Path independence
see Confluence
Path integrals
history of, 1057
in quantum field theory, 1061
for quantum gravity, 1054
and random networks, 1039
and statistical mechanics, 1061
Path metric spaces
networks as, 1030
Paths
representing substitution systems, 892
Paths in multiway systems
convergence of, 1036
independence on, 507
and non-determinism, 765
Paths in symbolic systems
dependence on, 898
Pattern-avoiding sequences, 944
as extraterrestrial signals, 1190
vs. Ramsey theory, 1068
Pattern formation
in biology, 422–428
history of, 947
and history of complexity, 862
in physics, 369–382
from randomness, 223
see also Cellular automata, etc.
Pattern matching
and game strategies, 1105
see also Matching
Pattern recognition, 549
Patterns (in Mathematica)
with __ as NP-complete, 1143
basic examples of, 854
and human thinking, 1103
and implementing CAs, 867
and network evolution, 1037
and proof strategies, 1156
Patterns (visual)
perception of, 577
Patterns of pigmentation, 422–429
PCE
see Principle of Computational Equivalence
PCP (Post Correspondence Problem), 757, 1139
PCs (personal computers)
and history of computing, 1108
my use of, 854
PDEs, 161–164
see also Partial differential equations
PDF
and production of this book, 852
PDP-1 computer
and history of CAs, 877
and munching squares, 871
PDP-7 computer
and history of CAs, 877
Peacock
pigmentation pattern of, 426
Peacock, George (England, 1791–1858)
and generalization in math, 1168
Peaks
in spectra, 586
Peano, Giuseppe (Italy, 1858–1932)
and axioms for arithmetic, 1152
and foundations of math, 1149
and math notation, 1182
and space-filling curves, 893
Peano arithmetic
axioms for, 773, 1152
emulating with groups, 1159
encoding proofs by ordinals, 1163
and Fermat's Last Theorem, 1166
and finite axiomatizability, 1176
and Gödel's Theorem, 1159
and Goodstein sequences, 1163
non-standard models for, 1169
and proofs of universality, 1127
undecidability of consistency of, 1168
see also Arithmetic
Pebbles
coming to surface of sand, 986
and origin of word "calculus", 925
prehistoric computing with, 1107
Peephole set (parameter space set for trees), 407, 935, 1006
Pegboards
randomness in, 312, 968
Peirce, Charles S. (USA, 1839–1914)
and axioms for logic, 1151
and Nand, 1173
and theories of communication, 1181
Pell equation, 944
and equation for Power, 1161
properties of, 1165
and quadratic Diophantine equations, 1164
Pendulum
attractor for, 275
Penny Matching game, 1105
Penrose, Lionel S. (England, 1898–1972)
and mechanical self-reproduction, 1179
Penrose, Roger (England, 1931– )
and discreteness of space, 1027
and Penrose tiles, 932, 943
and polyomino tilings, 943
in Preface, xiii
and spin networks, 1055
Penrose tilings, 932
cellular automata on, 930, 1028
diffraction patterns of, 1082
see also Quasicrystals
Pentagons
in deformable packings, 988
and Fibonacci numbers, 891
and GoldenRatio, 891
as inducing curvature, 532
lattices from, 930
see also Five-fold symmetry
Pentodes
and Nand operation, 1173
Perception, 547–635
atomic-scale, 1195
auditory, 585–588
in biological evolution, 1105
and branching in time, 505
and extraterrestrial intelligence, 836
and familiarity of features, 1105
higher forms of, 632–635
and Principle of Computational Equivalence, 722
and recognizing meaning, 826
relations to NP completeness, 771
of time in universe, 487
traditional idealization of, 736
Percolation
and Boolean networks, 937
as model of drainage, 1001
as phase transition, 983
and structure of class 4, 948
Percussion instruments, 1079
Perfect cuboid
as unsolved problem, 1166
Perfect fifth (musical chord)
curve of, 146
perception of, 1079
Perfect numbers, 911
and iterated aliquot sums, 911
in ordering of math constructs, 1177
unsolved problem about, 1166
and zeros of sequence, 135
Perfect shuffles, 974
Perfumes
odors in, 1105
Period 3 in iterated maps, 955
Period-doubling sequence
in iterated maps, 921
spectrum of, 1081
from substitution sequence, 892
Periodic behavior
origins of, 354–356
see also Repetitive behavior
Periodic points
enumeration of, 958
enumeration of in CAs, 954
in shift rules, 963
Periodic structures
see Localized structures
Periods
see Repetition periods
Periods (number type), 916
Periostracum, 1011
Peristalsis
as repetitive process, 1011
Periwinkle shell
growth of, 415
perl (computer language), 894
Permanence
Principle of, 1168
Permanents
and NP completeness, 1145
Permutation test, 1085
Permutations
and group theory, 1153
and reversible block CAs, 1023
and reversible mobile automata, 1018
in sestina rhymes, 875
Perpetual motion machines
in quantum field theory, 1062
in thermodynamics, 447
Perrin sequence (generalized Fibonacci sequence), 891
Perron numbers, 958
Persian (Islamic) art, 874
Persian gardens
and nested patterns, 874
Persian religions
and free will, 1135
Persistent structures
in class 4 systems, 281–296
see also Localized structures
Personal computers (PCs)
and history of computing, 1108
my use of, 854
Perturbation series
computational difficulty in, 1146
and computational irreducibility, 1133
in quantum electrodynamics, 1056, 1060
Perturbations
continual in CAs, 947
and effect on turbulence, 996
in initial conditions, 250
and randomness generation, 323
sensitivity of complexity to, 1002
Peru
mazes in, 873
Petals (in flowers)
arrangement of, 409
growth of, 412
Petersen network
examples of drawing, 476
Petri nets
and causal invariance, 1035
and causal networks, 1033
Petroleum, 1194
PGP cryptographic system, 1086
Phase factors
and gauge invariance, 1045
Phase-locked loops, 1188
Phase space
of cellular automata, 278
for finite-size systems, 961
Phase transitions, 981, 983
in cellular automata, 339
in continuous CAs, 948
discreteness from, 337
and inflationary universe, 1055
in Ising model, 982
melting in alkanes as, 1194
from molecular dynamics, 999
and nesting, 989
in one dimension, 983
in percolation, 983
in probabilistic CAs, 591, 976
and randomness tests, 1085
and scale invariance, 955
undecidability of, 1138
and uniformity, 354
Phases
and localized structures, 990
of matter as analogy for cellular automaton classes, 235
separation of in 2D CA, 336
Phelan, Robert J. (USA, 1933– )
and minimum area packings, 988
Pheromones
alkanes as, 1194
and animal communication, 1180
ϕ (phi)
see GoldenRatio
Philippines
as source of shells, 1011
Philosopher's stone
and alchemy, 861
as universal object, 1127
Philosophy
discussion of math in, 860
and human thinking, 1099
and idea of math in science, 859
implications for, 1196
of language, 1181
and pragmatic theory of law, 1136
and quantum mechanics, 1058, 1135
structure of proofs in, 1151
summary of relations to, 10, 863
and theories of communication, 1181
and universe as intelligent, 1195
and visual perception, 1076
writing style in, 849
Philosophy of science
issues of modelling in, 991
and methodology of this book, 1197
Phonemes
in sound compression, 1080
Photoconductivity
as element in technology, 1195
Photoelectric effect
in quantum theory, 1056
Photographs
and concept of intelligence, 838
Photons
and Bell's inequalities, 1064
history of, 1056
randomness from, 970
as source of decoherence, 1063
as type of particles, 1043
and vacuum fluctuations, 1062
zero mass of, 1046
Photorealistic graphics
textures in, 1077
Photoshop (software)
and image processing, 1077
Phrases
in human languages, 1103
Phyla of organisms, 1003
Phyllotaxis, 408–412, 1006
purpose invented for, 387
Physical constants
numerology for, 1025
Physicists
and Church's Thesis, 1126
and defining life, 1178
and effectiveness of math, 860
and free will, 1135
and measuring complexity, 1069
note for, 1043
and quantum measurement, 1058
and SETI, 1180
and study of complexity, 862
and studying hearing, 1080
Physics, 369–382, 433–545
avoidance of complexity in, 862
and Church's Thesis, 1126
compared to math, 821
conserved quantities in, 1022
continuous systems in, 729
fundamental, 433–545
and laws of human behavior, 1135
learning compared to science in this book, 856
vs. mathematics, 1026
mechanistic explanations in, 860
methods applied to biology, 1003
my early work in, 18
notions of purpose in, 1185
as origin of PDEs, 923
and Principle of Computational Equivalence, 720
quantum, 537, 1056–1065
reversibility of laws of, 435, 1019
satisfying constraints in, 349
success of math in, 859
summary of relations to, 8, 863
textbooks and Second Law, 1020
ultimate theory of
see Ultimate theory of physics