# 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

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