# 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 *n*^{th} 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