Index
Li, Wentian (USA, 1959– )
and CA classes, 948
in Preface, xiii
Lichens
on Mars, 1180
Lichtenberg figures, 995
Lie groups
and additive systems, 953
and sphere packings, 987
Life
definition of, 557, 823, 1178
and definition of complexity, 1069
on Earth, 825
and history of complexity, 50
on Mars, 1179
origin of, 1179
Life, Game of
see Game of Life
Life force, 1178
Life insurance
and history of statistics, 1082
Lifeforms
alien, 825
LIFO (last-in first-out) stacks
and context-free languages, 939
Light
caustics in, 984
perception of, 577
and quantum history, 1056
Light bulb filaments, 842
Light cones, 519
for cellular automata, 949
differential geometry of, 1051
and random causal networks, 1052
Light levels
and object recognition, 1076
Lightning
and origin of life, 1179
pattern of from space, 1187
randomness in, 995
as source of radio emissions, 1187
Lights of cities
patterns of from space, 1187
Lily pads, 401
Limit cycles
for differential equations, 961
in iterated maps, 961
see also Repetitive behavior
Limit ordinals, 1162
Limitations of science, 6, 748, 846
and ultimate theory of physics, 471
Limited size systems, 255–260, 267
Limits
of cellular automaton rules, 948
and fractal dimensions, 933
of networks as space, 1030
undecidability of, 1138
see also Continuum limits
Lincoln cathedral, 873
Lincos language, 1189
Lindenmayer, Aristid (USA/Netherlands, 1925–1989)
and L systems, 893
and plant branching, 1005
in Preface, xiii
Lindgren, Kristian (Sweden, 1960– )
in Preface, xiii
and universal CAs, 1115
Line defects, 1045
Line-printer output
of my early cellular automata, 19
Linear algebra
and CA invariances, 1022, 1023
and dimensions of networks, 1031
and models of memory, 1101
Linear cellular automata
see also Additive cellular automata
see also Elementary cellular automata
Linear codes, 1101
Linear congruential generators, 318, 974
based on powers of 3, 903
and chaos on calculators, 920
cryptanalysis of, 1089
historical use of, 968
and randomized algorithms, 1085
as shift register analogs, 975
Linear differential equations
and time series, 1083
Linear differential operators, 953
Linear Diophantine equations, 944, 1164
and polynomial time, 1146
Linear equations, 940
as defining rationals, 916
and free field theories, 1061
Linear feedback shift registers
see Shift registers
Linear filters
in sound compression, 1080
and spectra, 1082
in visual perception, 1076
Linear models
and computational irreducibility, 1132
in statistics, 589
Linear predictive coding
in sound compression, 1080
Linear programming
NP completeness of integer, 1145
for optimizing designs, 1193
Linear recurrences, 891, 906
and additive CAs, 1018
and history of CAs, 878
and time series, 1083
see also Linear congruential generators
Linear stability analysis, 988
Linear systems
vs. nonlinear, 940
Linearity
compared to additivity, 952
in quantum mechanics, 541, 1060
LinearSolve
iterative algorithm for, 1141
and LFSR cryptanalysis, 1087
and linear systems, 940
and NC computations, 1149
Linguistics
see Languages (human)
Linial (Gulden), Samuel (USA, 1927–[2004])
and underivability of logic axioms, 1170
Linkages
in chaos toys, 1183
characteristic shapes of, 1183
and constructible reals, 1129
for randomness generation, 969
Linked lists
for Game of Life, 949
Linker
for register machines, 1114
Linnik's problem, 910
Linux
and creation of this book, 854
Liquid crystals
as components in technology, 1195
phase transitions in, 981
topological defects in, 1045
Liquid-gas phase transitions, 981
Liquids
flow of, 376
see also Fluid flow
Lisp (computer language)
grammar of, 1104
and network systems, 936
representing expressions in, 897
theorems about, 1158, 1168
Lissajous figures, 917
List manipulation
examples of in Mathematica, 853
Listable
and implementing CAs, 866
ListConvolve
and aggregation systems, 978
and autocorrelation, 1080
basic example of, 853
and CellularAutomaton, 886
and elementary CAs, 865
and fast evolution rules, 1094
and general CAs, 886
and hexagonal CAs, 992
and image processing, 1077
and integer multiplication, 1093
and Ising model, 981
and multidimensional CAs, 927
recursive algorithm for, 1142
in sandpile models, 989
and Sierpiński pattern, 931
and visual perception, 1076
ListCorrelate
and additive CAs, 870, 952
and visual feature extraction, 1077
ListPlay
and sound output, 1080
Lists
encoded as integers, 1120, 1127
see also Sequences
Lithic analysis, 1183
Little group (spacetime symmetries), 1046
Littlewood, John E. (England, 1885–1977)
and chaos theory, 971
and Goldbach's Conjecture, 911
and iterated maps, 919
and numbers of primes, 910
Livermore (Lawrence Radiation Laboratory), 864
Lizards
pigmentation patterns of, 426
Local conservation laws, 1023
see also Conservation laws
Local minima, 346
Localization
in class 1 and 2, 252
as origin of repetition, 355
Localization (of eigenstates)
and randomness tests, 1085
Localized structures
and 3n+1 problem, 904
in class 4 systems, 281–296
in code 20 CA, 285
in code 357 CA, 286
in code 1329 CA, 287
in continuous CAs, 160, 244
as engineering components, 678
finding in 2D CAs, 965
and long-range communication, 252
in network evolution, 525
origins of, 990
and particles in physics, 525
in PDEs, 164, 1129
in presence of randomness, 526
in QCD, 1061
from random initial conditions, 228
in reversible CAs, 440
in rule 30 CA, 700
in rule 37R CA, 455
in rule 45 CA, 701
and rule 110 axiom system, 1168
in rule 110 CA, 31, 292, 964
same in different 2D rules, 949
in three dimensions, 949
in turbulent fluids, 997
in Turing machines, 888
and universality, 692
see also Gliders
Locomotion in animals, 1011
Log (logarithm)
algebraic independence of, 1164
computation of nth digits in, 912
and computational reducibility, 744, 747
continued fractions for, 144
digits of, 141
leading digits in, 914
randomness in digits of, 967
as source of randomness, 968
uniform distribution mod 1, 904
and Weber's law, 1014
Log-periodic antennas, 1183
Logarithmic growth
of number representations, 1070
Logarithmic law
for leading digits, 914
Logarithmic series, 1134
Logarithmic spiral, 418
Logging
and messages to Moon, 1189
regular patterns of, 1187
Logic
as applied to math, 780
axioms for, 773, 808
and combinators, 711, 898
and communication, 1181
and computational irreducibility, 1196
and defining intelligence, 1178
difficult notation in, 1104
and discreteness in programs, 976
as example of lattice theory, 1153
as example of rules, 875
and finite set theory, 1171
as foundation of math, 1176
history of, 1097, 1099, 1151
history of notation for, 1182
and history of universality, 1109
in human languages, 1173
in human thinking, 627
implications for, 1197
interesting theorems in, 816
lengths of proofs in, 1175
machines for doing, 1107
multilayer, 1096
multivalued, 814, 1175
and natural science, 860
non-universality of basic, 784
as not mainstream math, 859
possible models of, 805
in practical computers, 1108
and quantum mechanics, 1058
reversible, 1097
shortest And, Or axioms for, 1174
shortest Nand axioms for, 808
ternary, 814
and Thue on substitution systems, 893
see also Predicate logic
Logic circuits
emulated by CAs, 662, 1112
emulated by Game of Life, 1117
and universality, 1119
Logic expressions
see Boolean expressions
Logic minimization, 1095
compared to searching, 1193
Logic programming languages, 1158
Logic Theory Machine, 1157
Logical depth
and defining complexity, 1069
for Turing machines, 1144
Logical functions
see Boolean functions
Logical positivism
and theories of communication, 1181
Logical rules
see Rules
Logicism
as foundation of math, 1176
LogIntegral (logarithmic integral li)
and distribution of primes, 133, 909
and Zeta, 918
Logistic differential equation
and iterated maps, 918
Logistic map, 920
closed forms for iterates of, 1098
and continuous CAs, 922
and history of chaos theory, 971
see also Iterated maps
Logistics
and causal networks, 1033
and complex systems, 862
Lognormal distribution
for human weights, 977, 1003
and multiplicative processes, 977
Logo (computer language)
and 2D TMs, 930, 931
Long division, 139
Long-term memory, 1102
Long-time tails
in molecular dynamics, 999
and shaking, 969
Longest paths
and NP completeness, 1146
Looms
and history of computer, 1107
Loop general relativity, 1048
Loop quantum gravity, 1054
and spin networks, 1055
Loop switching method
and network layout, 1031
Lorentz, Hendrik A. (Netherlands, 1853–1928)
and relativity theory, 1041
Lorentz contraction, 1041
Lorentz gas, 1022
Lorentz transformations, 1041, 1042
Lorentzian spaces, 1051
Lorenz, Edward N. (USA, 1917–[2008])
and chaos theory, 971
and complex ODE, 879
and experimental math, 899
and fluid turbulence, 998
in Preface, xiii
Lorenz equations
as giving strange attractor, 922
and history of chaos theory, 971
and Lissajous figures, 917
and weather prediction, 1178
Los Alamos
and history of CAs, 877
and my work on CAs, xiii, 880
Lossless data compression, 560
Lossy data compression, 572
Lotka, Alfred J. (USA, 1880–1949)
and oscillatory chemical reactions, 1013
Lotteries, 969
Lovelace, A. Ada (Byron) K. (England, 1815–1852)
and universality, 1110
Low-level languages
and practical computing, 1109
and register machines, 101
Löwenheim–Skolem theorem, 1172
Lower bounds
on computations, 761, 1143
on parity, 1096
on sorting algorithms, 1142
LPC
in sound compression, 1080
Lucas, F. Edouard A. (France, 1842–1891)
and binomials mod k, 870
Lucas–Lehmer test
for primes, 911
Lucas numbers, 891
Lucian (Greece, 120 – ~180 AD)
and inhabitants of Moon, 1190
Lucretius, Titus Carus (Italy, ~95 – ~55 BC)
and atomism, 876
and models based on rules, 860
Łukasiewicz, Jan (Poland, 1878–1956)
and axioms for logic, 1151
and multivalued logic, 1175
Łukasiewicz representation, 896
Lunes
and ornamental art, 872
theory of, 873
Lungs
branching in, 1008
Lyapunov exponents
in cellular automata, 950
and entropies, 960
in iterated maps, 921
probabilistic estimates of, 953