Index



Practical computers
and concept of halting, 1137
and discrete models, 369
emulated by CAs, 661
history of, 1107
intuition from, 716
and universality, 644
workings of, 1108

Pragmatic theory of law, 1136

Pragmatics
and theories of communication, 1181

Pre-Socratics
aphorism from, 1196

Precedence
in context-free languages, 1103
in math notation, 1182
of operators in logic, 1173
of operators in WFFs, 1150

Precession
in perihelion of Mercury, 1047

Precipitation
and extraterrestrial rocks, 1179

Predators
avoiding by randomness, 1192
extraterrestrial, 1190
operating not by prediction, 1105

Predestination
and free will, 1135

Predicate logic, 1151
automated proofs in, 1158
axioms based on, 1159
axioms for, 773
as basis for Lincos language, 1189
and CA axioms, 794
combinators and, 1121
as foundation for math, 1149
higher-order, 1167
and proofs about programs, 1168
universality in, 784, 1159

Predicates
in well-formed formulas, 1150

Predictability
in biological evolution, 397
and computational irreducibility, 737
and engineering, 829
and free will, 751
of melting points, 1194
and non-universality, 695
as preventing complexity, 40
and Principle of Computational Equivalence, 6
as requirement for science, 1196
of robots in science fiction, 629
and thermodynamics, 447
of weather, 1177

Prediction
of data, 549
evolving methods for, 1105
and game strategies, 1105

Prefetching
of data in CA implementation, 868

Prefixed number representation, 1070

Prefixes
and pointer-based encoding, 1071

Pregeometry, 1027

Prehistoric structures
identifying purposes of, 1184

Premium bonds (lottery)
randomness in, 969

Prepend (prepend element)
theorems about, 1168

Presburger, Mojzesz (Poland, 1904 - ~1943)
and axioms for arithmetic, 1152

Presburger arithmetic, 1152
algorithms for, 1143

Price fluctuations in markets, 429

Prigogine, Ilya (Belgium/USA, 1917-[2003])
in Preface, xiii
and reaction-diffusion, 1013

Primal sketch, 1076

Primary colors, 577, 1075

Primates
auditory perception in, 1079

Prime (prime numbers)
see Primes

Prime implicants
in Boolean formulas, 1095

PrimePi (prime count), 133, 909
and encoding of lists, 1120
and Zeta, 918

PrimeQ (primality test), 909
encoded as integer equation, 1160
and integer factoring, 1090
randomized methods for, 1192
and shift register periods, 975

Primes
and arithmetic systems, 1115
CA for producing, 640, 1109
and complexity history, 48
distribution of, 133, 909
and doubling system periods, 258
and encoding lists, 1120
and extraterrestrials, 837, 1190
of the form x^2+1, 1162
from fraction system, 1115
and hashing, 1100
history of, 908
largest known, 909
leading digits in, 914
and linear congruence periods, 974
Lucas-Lehmer test for, 911
and multiplicative digits, 902
in ordering of math constructs, 1177
and periods of limited size systems, 256
as precursors to my work, 878
and primitive recursion, 907, 908
and quadratic congruential generators, 975
and register machines, 1114
as rule 60 initial condition, 1091
sequence of, 132-135, 909
simplest CA for producing, 1186
tables of, 910
trapezoidal, 911
as values of polynomials, 1162
and Zeta, 148, 918

Primitive cells
and CA lattices, 929

Primitive operations
in logic, 807, 1096
and natural phenomena, 18
and universality, 642

Primitive polynomials
and shift register periods, 975

Primitive recursive functions, 907
and Church's Thesis, 1125
undecidability in, 1136
and universality, 1121

Princeton (Institute for Advanced Study), xiii

Principal curvatures, 1049

Principia (of Newton), 859

Principia Mathematica (of Whitehead and Russell)
and foundations of math, 1149
and Gödel's Theorem, 1158
logic axioms in, 1151
and orders of logic, 1167
as origin of tag systems, 894

Principle of Computational Equivalence, 715-846
antecedents to, 1125
and computational complexity theory, 766
and computational irreducibility, 738
and concept of microcosm, 1196
and continuity, 729
and epistemology, 1196
and future of computers, 841
and future of technology, 1196
and Gödel's Theorem, 782
historical perspectives on, 844-846
and human uniqueness, 844
implications for ontology, 1197
implications for philosophy, 1196
implications for technology, 840
initial conditions violating, 1129
introduction to, 5
and mathematicians, 1125
and mathematics, 772
and modelling, 728
and natural selection, 1002
and operator systems, 815
and origin of complexity, 736
outline of, 716-719
and philosophy of science, 1197
and postmodernism, 1196
process of understanding, 856
and quantum measurement, 1064
and thermodynamics, 444
and ubiquity of intelligence, 822
and universe as intelligent, 1191
validity of, 726-735

Principle of Entropy Increase
character of as principle, 1126
see also Second Law of Thermodynamics

Principle of Equivalence (for gravity), 530

Principle of Least Action, 1185

Principle of Least Effort
and Zipf's law, 1014

Principle of Natural Selection
character of as principle, 1126
see also Natural Selection

Principle of Permanence, 1168

Principle of Relativity
character of as principle, 1126
see also Relativity theory

Printing
color gamut in, 1074
and halftoning, 1077
rosettes in 4-color, 1078
of this book, 852

Prions, 988

Prisoner's Dilemma, 1104

Probabilistic cellular automata, 325, 591, 976
classification of, 948
and continuous CAs, 922

Probabilistic estimates
in cellular automata, 953
in multiway systems, 937

Probabilistic models, 588
aggregation systems as, 332
and external randomness, 299
Probabilistic CAs, 299
of written languages, 1181

Probabilistic substitution systems, 1084

Probabilities
in block encoding, 1071
and entropies, 959
as intermediate truth values, 1175
origin of, 1083
in quantum computers, 1147
in quantum theory, 541, 1058

Probability distributions
and fractal dimensions, 934
for random walk, 977

Probability theory
and defining randomness, 1067
foundations of, 967

Problem-solving
and defining intelligence, 1178

Procedural computer languages, 627

Procedures
see Programs

Process charts (flowcharts)
and causal networks, 1032

Processors
in practical computers, 1108

Product
and spectra, 1081
see also Multiplication

Production systems
and computer languages, 1104
and formal languages, 939
see also Multiway systems
see also Sequential substitution systems

ProductLog
and concatenation sequences, 913

Program counter
in register machines, 98

Program machines (register machines), 97-102, 896

Programmability
and history of math, 1177
of machines, 1107
and universality, 642

Programmable logic arrays (PLAs), 1095, 1097

Programmed cell death, 419

Programmed trading systems, 431

Programming
and proofs of universality, 698
and study of programs in the notes, 854

Programming languages
see Languages (computer)

Programming paradigms
in Mathematica, 853

Programs
behavior of simple, 23-39
and biological systems, 383
compared to constraints, 342
compared to nature, 297
continuous, 1129
discreteness in, 976
as foundation for science, 3
history of concepts related to, 860
and human thinking, 628
making models based on, 368, 992
in notes to this book, 853, 854
in practical computers, 1108
proving theorems about, 1168
random, 23, 101
as reproducing the universe, 465
see also Algorithms
see also Cellular automata, etc.
see also Computation

Projection method
for Penrose tilings, 932

Prolog (computer language), 1158

Pronunciation
lookup based on, 623

Proof theory
and number theory, 1166

Proofs, 775
as application of rules, 875
of axiom system correctness, 1170
and computer experiments, 899
and definition of math, 860
encoded by ordinals, 1163
general frameworks for, 1177
of halting for TMs, 1145
importance of relative to theorems, 1177
inference rules in, 1151
lengths of, 1143
lengths of in logic, 1175
of NP completeness, 1145
of P!=NP, 1146
role of in current math, 1156
searching for, 1157
of shortest axiom for logic, 811
structures of, 1155
of undecidability, 1137
of undecidability of PCP, 1140
and universal language of Leibniz, 1109
of universality, 664-673, 722, 1127
of universality by computer, 1115
of universality of Life, 1117
of universality of rule 110, 678-689, 1116

Propagation
of class 4 structures, 281
of effects in CAs, 252, 950
of effects in PDEs, 923

Propellers
characteristic shapes of, 1183

Proper time (in relativity theory), 1042, 1051

Proportion
theory of in art, 872

Propositional logic, 1151
axioms for, 773, 803
see also Logic

Prosody (study of verse)
and Fibonacci numbers, 891

Protein folding
and biological evolution, 1003
and NP completeness, 1146
and optimization, 988
randomness in, 1184

Proteins
as biological artifacts, 1184
made from genes, 1002
and nanotechnology, 1193
shapes of, 1003
statistics of sequences in, 1184
symmetries in shapes of, 1007

Protestantism
and free will, 1135

Protists
pattern in, 385
see also Radiolarians

Protocols
for computers, 1182

Protons
decay of, 1025
size of, 472, 1044

Protoplasm, 1178

Protozoa
as fairly optimal organisms, 398

Prouhet, Eugène (France, 1817-1867)
and Thue-Morse sequence, 893

Prouhet-Thue-Morse sequence
see Thue-Morse sequence

Prusinkiewicz, Przemyslaw (Poland/Canada, 1952- )
and branching in plants, 1005

Pseudocode
avoidance by use of Mathematica, 853

PseudoInverse
and matrix memories, 1101

Pseudonoise (PN) sequences, 1084
and CDMA signals, 1188
see also Shift registers

Pseudorandom generators, 317
historical use of, 968
and history of complexity, 49
as precursors to my work, 879
randomness tests on, 1085
see also Intrinsic randomness generation
see also Random number generators

Pseudospectral methods for PDEs, 924

PSPACE (polynomial space) computations, 1142

PSPACE completeness
of automaton minimization, 957
and periods of CAs, 1147

Psychiatry
and history of complexity, 862

Psychoactive drugs
and spider webs, 1184

Psychology
and defining intelligence, 1178
history of, 1099, 1135
mentions of undecidability in, 1136
systems to emulate, 629
and visual perception, 1076

Psychophysics, 1076
experimental difficulties in, 1077

Ptolemy (Egypt, ~100 - ~170 AD)
and math in science, 859
and models based on rules, 860

Public-key cryptography, 1086
and quadratic congruential generators, 975

Publication counts
for axiom systems, 1153
for cellular automata, 878

Publication dates
conventions for, 851

Publicon
and authoring this book, 852

Puffer train (in Game of Life), 965

Pulsar (in Game of Life), 964

Pulsar puffer (in Game of Life), 965

Pulsars
and general relativity, 1048
and history of SETI, 1189
on Pioneer 10 plaque, 1189
radio emissions from, 1188
thought to be intelligent, 835

Pulse code modulation (PCM), 1188

Pumping lemmas (for formal languages), 944

Punched cards
and history of computing, 1107
and history of universality, 1110

Pure functions
and lambda calculus, 1121
see also Function

Pure gravity, 1053

Pure mathematics
foundations of, 1150

Pure states (in quantum theory), 1062

Purpose
in archeology, 1184
in biological evolution, 387
compared to mechanism, 831
and defining randomness, 1068
definition of, 829
for extraterrestrials in science fiction, 1191
and free will, 1136
of natural systems, 1185
Occam's razor for, 1025
in physics, 1185, 1187
possible, 1185
of science, 861
technology as achieving, 843
of whale songs, 1180

Putnam, Hilary W. (USA, 1926- )
and Diophantine equations, 1161

Puzzles
based on rules, 875
and constraints, 210
and intelligence, 822, 1178
patterns in, 1104
training animals to solve, 826
use of base 2 in, 902

Pylos tablet
maze pattern on, 873

Pyramids
rules for building from stone, 874
Sierpinski, 172

Pythagoras (Italy, ~560 - ~480 BC)
and math in science, 859, 860
and perfect numbers, 911
and rules in music, 875

Pythagorean theorem
sending signals based on, 1189

Pythagorean triples
and Moire patterns, 1078
as satisfying constraints, 945

Pythagoreans
and aliquot sums, 910
and irrationality of Sqrt[2], 912
and music, 1080
and numerology, 1025
and primes, 908

Python
pigmentation pattern of, 426