# Index

Incompleteness, 782

essential, 1159

in multiway systems, 783, 797

of Robinson arithmetic, 1169

see also Gödel's Theorem

Inconsistency

in axiom systems, 781

in multiway systems, 797

Increment function

in combinators, 1122

in register machines, 97

in Turing machines, 1144

Incremental improvement

and natural selection, 392

Incremental programming, 894

Independence

from axioms, 1167

of axioms, 803

from more powerful axioms, 1166

of theorems in logic, 818

Independence results

since Gödel's Theorem, 1163

Indeterminism

and free will, 750, 1135

Index

features of this, 852

names in this, 852

Indian studies of prosody, 875

Indigenous peoples

and animism, 1195

Indo-European languages, 1103

Induction (mathematical)

and automated proofs, 1158

in axioms of arithmetic, 1152

and recursive sequences, 907

in reduced arithmetic, 800

as scheme for proofs, 1177

statements unprovable without, 1169

Induction (scientific)

and experimental math, 899

and ultimate theory of physics, 466

Inequivalence

as name for Xor, 1173

Inertia

and uniformity of space, 1028

Inertial motion, 521

Infeasible computations, 1143

Inference

of cellular automaton rules, 1089

statistical, 589

Inference rules

in proofs, 1151

Infinite acceleration

in 5-body problem, 1130

Infinite evolution

and undecidability, 755

Infinite impulse response

cellular automata as, 1035

Infinite loops

in *Mathematica*, 1137

and proving undecidability, 1137

Infinite objects

and non-standard arithmetic, 1169

Infinite patterns

generated in finite time, 732

Infinite trees

and symbolic systems, 898

Infinitesimals

and computational irreducibility, 1132

as generalizing numbers, 1168

and non-standard analysis, 1172

and PDEs, 161

Infinities

in QED, 1057

Infinity

and the continuum, 1127

forms of, 1162

and symbolic representation, 788

and transfinite numbers, 1162

and undecidability, 788

Inflationary universe, 1026, 1055

Information

in axiom systems, 819

in block encoding, 1071

in cellular automata, 959

and definition of life, 1178

in multicolor encodings, 1111

and radiation in rule 37R, 455

in theorems of logic, 818

and thermodynamics, 1020

Information content

algorithmic, 1067

vs. amount of computation, 1133

of biological organisms, 1002

entropy as, 960

and history of chaos theory, 971

in initial conditions, 920

and lower bounds, 1143

measures of, 1181

Information dimension, 959

Information-preserving data compression, 560

Information theory

algorithmic, 1067

and cryptography, 1086

and data compression, 1069

and defining complexity, 1068

and defining randomness, 1068

and human languages, 1181

Information transmission

and causal networks, 520

in cellular automata, 252

in class 4 systems, 281

and data compression, 1069

and error-correcting codes, 1101

in financial markets, 1015

limited by speed of light, 518

in PDEs, 923, 925

and quantum entanglement, 1065

and universality, 694

Initial conditions

for cellular automaton fluids, 381

and complexity, 41

and computability, 1129

finding as NP problem, 1142

information content in, 920

as input for computations, 637

nested in rule 184, 272

NP completeness of finding, 769

and oracles, 1126, 1129

periodic, 266

persistent structures from, 283

and Principle of Computational Equivalence, 724

random, 223-296

randomness from, 304-314

for rule 110 universality, 689

sensitive dependence on, 153

sensitivity to, 250-252

sets of for Turing machines, 1139

shape dependence on, 179

and thermodynamics, 443

and time travel, 1043

for Turing machines, 710

and undecidability, 756

for the universe, 1026

Initial value problems

in general relativity, 1053

in PDEs, 940

Injectivity

in cellular automata, 959

Ink

and printing of this book, 852

spreading of as diffusion, 978

Inner

and associative CAs, 956

InputForm

for programs in notes, 854

Insanity

and free will, 1136

Inscribed circles, 986

Insert (insert element)

and random networks, 1038

Insertion sort, 1142

Instabilities

in CA evolution, 950

and chaos theory, 153, 971, 972

in crowds of people, 1014

in financial systems, 430

of fluid vortex sheets, 997

in numerical PDEs, 924

in numerical turbulence, 997

in PDEs, 988

and quantum measurement, 542

in reaction-diffusion, 1013

and the Second Law, 1020

in self-gravitating systems, 1021

in splashes, 1000

Instantons

in path integrals, 1057

Instincts

and defining intelligence, 1178

Institute for Advanced Study, xiii

Institutions

and complexity research, 862

role of in science, 857

Instruments (musical)

as nonlinear oscillators, 971

sounds produced by, 1079

Insurance

and history of statistics, 1082

Integer equations, 790, 944

and undecidability, 787

see also Diophantine equations

Integer factoring, 1090

see also FactorInteger

Integer functions

patterns generated by, 870

Integer linear programming

NP completeness of, 1145

Integer sequences, 123, 128-131

IntegerDigits

basic examples of, 854

and computational reducibility, 747

concatenation of, 913

implementation of, 901

and rule 90 pattern, 870

and substitution systems, 889, 891

and sums of three squares, 910

IntegerExponent

and 3n+1 problem, 904

and additive CA attractors, 963

behavior of, 911

and binomial coefficients, 870

and cyclic multiplication, 950

and decimation systems, 909

and period doubling, 892

and a recursive sequence, 906

relation to DigitCount of, 902

and rule 150 pattern, 885

and spectra, 1081

and symbolic systems, 897

TM computation of, 1144

and TM enumeration, 1139

and Turing machine 600720, 1145

and Turing machine for increment, 759

IntegerQ (integer test)

and fraction systems, 1115

Integers

algorithmically simple, 916

as encodings of lists, 1120

and human experience, 1177

number of, 1127

as ordered set, 1152

represented by symbolic expressions, 1121

transfinite, 1162

Integrability

of PDEs, 1023

in three-body problem, 972

Integrals

as exact solutions, 1133

Integrate

and distance in curved space, 1048

impossibilities in, 1137

numbers generated by, 916

systematic methods for, 1177

Integrated circuits

see Chips

Intelligence

analysis using human, 620

and Anthropic Principle, 1026

attributed to universe, 1195

definition of, 822, 1178

in Drake equation, 1191

extraterrestrial, 635, 822

machine, 628, 1099

and Maxwell's demon, 1021

and philosophical implications, 1197

physics as showing, 1191

as special feature of humans, 844

testing of, 1104, 1178

in the universe, 822

see also Thinking

Intelligent design

and complexity, 861

and teleology, 1185

Intentionality

see Purpose

Interdependence

and definition of life, 1178

Interestingness

of chemicals, 1194

in mathematics, 793, 816

of theorems in general, 821, 1176

of theorems in logic, 817

Interfaces (boundaries)

effective rules for in CA, 980

Interfaces (computer)

and concept of halting, 1137

graphical vs. language, 631

history of, 1102

Interference

and quantum computers, 1148

in quantum mechanics, 1059, 1062

of string updates, 503

Interferometer

device like, 311

Intermediate degrees (in computation theory), 734, 1130

Intermediate growth groups, 938, 945

Intermediate steps

in multilevel logic, 1096

in proofs, 811, 1155, 1157

in solving PCP, 1140

Intermittency

and 1/f noise, 969

Internationalism

in mathematical notation, 1182

Internet businesses

and speculative stocks, 1015

Interpolation

of CA patterns, 1092

and fitting models, 1084

Interpretability

axiom system encoding, 816

Interpretation of quantum mechanics, 1058

Interpreted languages, 1109

Interrupts (computer)

as source of randomness, 970

Intersection

and finite set theory, 1171

Interstellar radio communication, 1189

Interstellar space

molecules in, 1179

turbulence in, 1188

Interstices

packings that use, 986

Interval, maps on the

see Iterated maps

Interval arithmetic

and generalizing numbers, 1168

Intractability (computational), 758-771

and cryptography, 1089

Intrinsic curvature, 1049

Intrinsic randomness generation, 315-326

and continuum behavior, 333

early reactions to, 971

in early universe, 1056

experiments showing, 976

in financial systems, 432

in fluid flow, 382

in fluttering, 971

and free will, 752

in Ising models, 982

my first paper on, 882

in quantum systems, 543, 1063

in reversible conserving systems, 462

and Second Law, 450

see also Randomness generators

Intrinsically defined curves, 1009

Introspection

and free will, 1135

Intuition

about objects in nature, 828

and computer experiments, 856

and continuous math, 925

development of my, 21

in human thinking, 627

mathematical and proofs, 1156

mechanism for in brain, 1136

need for new, 39-41

from practical computing, 716, 872

and Principle of Computational Equivalence, 726

and ultimate theory of physics, 468

Intuitionism

as foundation of math, 1176

Intuitionistic logic

and double negation, 1158

and Peano arithmetic, 1152

Invagination

in animal development, 418, 1009

Invariances

and cellular automata state transition graphs, 963

Invariant configurations

in 1D cellular automata, 941, 954

in 2D cellular automata, 942, 954

as attractors, 276

in Game of Life, 964

and satisfying constraints, 348

undecidability of, 1138

Invariant entropy (spacetime entropy), 960, 961

Invariant interval (in relativity theory), 1042

Invariants

and axiom system proofs, 1170

in dynamical systems, 961

for knots, 1046

see also Conserved quantities

Inventions

vs. discoveries in math, 1176

for randomness generation, 969

Inverse problems

and NP completeness, 771

and perception, 551

Inverse square law for gravity, 536, 1047

InverseFunction

and CA encodings, 1118

Invertible cellular automata

see Reversible cellular automata

Involute of circle, 418

Involutions

cellular automata as, 1017

Ion traps

for quantum gates, 1148

Ionosphere

radio emissions from, 1187

IQ (intelligence quotient), 1178

tests, 1104

Iran

ornamental art in, 874

Iraq

ornamental art in, 873

Iris (eye) patterns

randomness of, 1014

Iron Age

ornamental art from, 873

Irrational numbers

and 3D non-periodic tiling, 943

generating additive systems, 953

generating quantum gates, 1148

and idealized billiards, 1022

iterated multiplication by, 903

and musical chords, 1079

in Peano arithmetic, 1162

Irreducibility

see Computational Irreducibility

Irreducible representations (of groups)

and isotropy, 980

and spin, 1046

Irregularities

see Regularities

Irreversibility

in data compression, 572-576

and memory, 625

in physical systems, 441-457

and quantum measurement, 1063

Ising, Ernst (Germany/USA, 1900–1998)

and Ising model, 981

Ising model, 981

exact solution of 2D, 1133

ground state of, 944

and history of CAs, 876

lack of exact 3D solution, 1133

and lattice gas models, 999

and my work on CAs, 880

and P completeness, 1149

phase transition in, 982

as precursor to my work, 879

as probabilistic model, 1083

and randomness tests, 1085

undecidability in, 1138

see also Spin systems

Islam

and ornamental art, 872

as rejecting animism, 1195

Islamic art, 43

Isocorrelation textures, 1078

Isomers (variant molecular structures), 1194

Isotropic tensor, 980

Isotropy

in aggregation systems, 978

in biological growth, 1007, 1010

in code 746 CA, 334

of differences in 2D CAs, 950

in discrete systems, 980

in physics and CAs, 473

of random walks, 977

of sums of squares, 910

Iterated aliquot sums, 911

Iterated bitwise operations, 906

Iterated division

and continued fractions, 143

Iterated function systems, 191

and pictures of ferns, 1005

Iterated maps, 149-155

algebraic iterates in, 1098

attractors in, 961

of bit operations, 921

from CA densities, 953

on the Cantor set, 869

complex, 933

and computation universality, 1129

and computer experiments, 899

emulating discrete systems, 1129

as evidence of determinism, 972

and financial markets, 1015

and fluid flow, 998

history of, 918

and history of chaos, 971

and history of complexity, 49

of integers, 122

in Newton's method, 1101

periodic points in, 955

as precursors to my work, 879

and QCD, 1061

and recurrence relations, 906

spectra in, 1080

and substitution systems, 921

two-dimensional, 921

Iterated morphisms (substitution systems), 893

Iterated radicals, 915

and GoldenRatio, 891

Iterated rules

sizes of formulas for, 1096

Iterated run-length encoding, 905

Iteration

as basis for algorithms, 1141

compared to repetition, 990

examples of in *Mathematica*, 853

Iteration theory

and iterated maps, 918

$IterationLimit

and avoiding undecidability, 1138

Iterative automata

see Cellular automata

Iterative improvement

for engineering designs, 1193

in satisfying constraints, 344

IUPAC chemical nomenclature, 1194