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
|
Send a Message
