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 (sigma), 1127

Pairwise sorting algorithms, 1142

Palatine Chapel, 873

Paleolithic art, 43, 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

Palindrome systems, 125-127

Palindromes
in period-doubling sequences, 892

Palm trees
growth of, 1004, 1004'
phyllotaxis in, 409

Pandas
patterns on, 426, 1013

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 equations, 925, 940

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

Perceptrons, 1076, 1099, 1102

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

Phoenician art, 43, 873

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

Physiology
and free will, 1135
see also Biology