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