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
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 x2+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–[2016])
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
Sierpiński, 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 √2, 912
and music, 1080
and numerology, 1025
and primes, 908
Python
pigmentation pattern of, 426