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

Likelihood
maximum, 589, 1083

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, 255260, 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, 281296
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

LZW compression, 565, 1069, 1072