# 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 `x`

, 1162^{2}+1

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

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 `Sqrt[2]`

, 912

and music, 1080

and numerology, 1025

and primes, 908

Python

pigmentation pattern of, 426