Index



Floating-point computation
and arithmetic coding, 1071
and chaos experiments, 919

Flocks of birds
patterns in, 1011

Floor (integer below)
basic example of, 854
and digital slopes, 916
encoded as integer equation, 1160
and nesting in sine curves, 917
and three-body problem, 973

Flory exponents, 978

Flow of fluids, 376382
see also Fluid flow

Flowcharts
and causal networks, 1033
and computer interfaces, 1103
and defining complexity, 1069
and systems theory, 862

Flowering plants
growth of, 1004

Flowers
phyllotaxis in, 409, 1007
symmetries of, 1007

Floyd–Steinberg algorithm, 1077

Fluctuations
in cellular automata densities, 954
of entropies in class 4, 960
and initiating crystal growth, 992
in market prices, 429
order in universe as, 1020
in recursive sequences, 130
and shot noise, 968
spectrum of in turbulence, 997
in thermodynamics, 447
violating Second Law in rule 37R, 453

Fluid convection
and Lorenz equations, 971

Fluid flow, 376382
analog of in crowds, 1014
analog of in sand, 1001
as analogy for networks, 535
as analogy for quantum field theory, 1059
in bird songs, 826, 1180
in chaos toys, 1183
community studying, 1000
continuity of vs. space, 472
and continuous idealizations, 729
as continuous limit, 327
past cylinders, 998
discrete models for, 999
generalizations of, 1000
and intelligence, 822, 837
and memory, 823
minimal cellular automata showing continuity of, 464
as model for animal growth, 1010
and my work on CAs, 881
and random fertilization, 970
sensed by dolphins, 827
solving PDEs in, 924
two-dimensional, 999
and weather, 1177

Fluid turbulence, 376
and history of complexity, 862
see also Turbulence

Fluttering, 971

Flux tubes in QCD, 1061

Fluxions
invention of, 901

Fly eye
form of, 385

FM (frequency modulation)
in radio signals, 1188

FM synthesis
curves from, 918
sounds from, 1079

Foams
evolution of, 1039
model for ether as, 1027
and Voronoi diagrams, 987

Focusing
as origin of discreteness, 984

Fold
basic example of, 853
for computing factorial, 1110
and pairwise sorting, 1142
and paths in networks, 957
and primitive recursion, 907
in random recursive function, 908
and repeated squaring, 1094
and unwinding primitive recursion, 907

Folding
and forms of animals, 417

Folding map, 150

FoldList
basic example of, 853
and implementing proofs, 1155
and nested patterns, 931
and random walks, 977
and Sierpiński pattern, 931
understanding operation of, 1177

Folk theorem
in game theory, 1104

Fonts in this book, 852

Foods
odors in, 1105

Foot (animal)
development of, 419

For (For loop)
for computing factorial, 1110

Foraging
randomness in, 1002, 1011, 1192

ForAll ()
in predicate logic, 1151

Forces
and gauge invariance, 1045

Forcing
of nested patterns, 942
of operators, 1172

Forcing, method of
and unprovability, 1163

Forecasting
weather, 1178
see also Predictability

Forests of stunted trees
as additive cellular automata, 878

Forks
characteristic shapes of, 1183

Form
historical study of, 967
living vs. non-living, 1003
of organisms
see Growth

Form factors
and sizes of particles, 1044

Formal cause, 1185

Formal experiments
and philosophy of science, 1197
see also Computer experiments

Formal languages
and CA encodings, 1119
and constraint systems, 944
and my work on CAs, 881
of networks, 1040
and substitution systems, 893
undecidability in, 1137
see also Languages (abstract)

Formal logic, 1151
see also Logic

Formal power series
and regular languages, 957

Formal systems
as foundation of math, 1176
and foundations of science, 1197
in mathematics, 1150
transfinite hierarchy of, 1159

Formants
in speech sounds, 1079

Formatting hacks
and nested patterns, 932

Formula language
of Frege, 1149

Formulario project
of Peano, 1149

Formulas
analysis with, 606620
based on Nand, 1097
Boolean, 616, 1095
for cellular automata, 869, 1134
and computational irreducibility, 737
and computational reducibility, 1134
constraints on, 945
for primes, 909
and Principle of Computational Equivalence, 728
in three-body problem, 972
see also Exact solutions

Fortran
and chaos experiments, 919
and computer language history, 1104
as example of language, 1109
and history of computing, 1108
my use of, 854

Forts
nested architecture of, 874

Fortune-telling, 968, 1192

Fossil record
common features across, 395
and complexity in biology, 389
of early life, 1179
of leaf shapes, 1005
symmetries in, 1007

Foundations of mathematics, 772821
and history of universality, 1110
schools in, 1176
and SETI, 838

Foundations of modelling, 363

Foundations of science, 1196

Four-color printing
rosettes in, 1078

Four-Color Theorem
and coloring of networks, 1029
graph grammars in proof of, 1040
as having long proof, 779, 1156

Four-manifolds
equivalence of, 1051, 1138

Four squares problem, 910

Four-vectors
in relativity theory, 1042

Fourier, J. B. Joseph (France, 1768–1830)
and Fourier analysis, 1072

Fourier (Fourier transform), 1074
of 2D nested patterns, 1082
and data compression, 1074
implemented by diffraction, 1077
and JacobiSymbol, 1081
multiplication using, 1093
of number theory functions, 911
and power spectra, 969
and quantum computers, 1148
and random walks, 977
recursive algorithm for, 1142
and spectra, 1080

Fourier series, 917, 1072

Fowle, Frank F. (USA, 1877–1946)
and Walsh transforms, 1073

Fractal dimension, 933
of additive CAs, 870, 955, 1092
of Apollonian packing, 986
and defining complexity, 1069
as entropy, 959
of fracture surfaces, 995
of reversible CAs, 1018
of rule 90, 870
of strange attractors, 961
and texture discrimination, 1077
of Weierstrass functions, 918

Fractal geometry
and history of numbers, 901

Fractal network, 197

Fractals
and 1D substitution systems, 83
and 1/f noise, 969
in 2D cellular automata, 171
and 2D substitution systems, 187
in additive cellular automata, 270
and biological form, 1004
in cellular automata, 58
and complex maps, 933
and computer experiments, 899
in Cosmati mosaics, 873
and fluid turbulence, 997
and general study of form, 967
history of, 934
and history of complexity, 862
and history of modelling, 992
in landscape structure, 1001
and my work on CAs, 19
in network evolution, 509
origins of, 357360
and plant branching, 1005
as precursors to my work, 880
and price fluctuations, 1014
from random initial conditions, 273
in rule 90, 25
in self-gravitating systems, 1021
snowflake shapes as, 371
summary of relations to, 15
and texture generation, 1077
see also Nesting

Fraction systems, 1115

Fractional integration
and 1/f noise, 969

Fractional linear transformations
and continued fractions, 914
and nested patterns, 933

FractionalPart
and chaos theory, 308
and continuous CAs, 922
difficulty of evaluating, 1134
iterated map based on, 955
and Lorenz equations, 971
in model of boiling, 994
of powers, 121

Fractons, 1081

Fractran (universal fraction system), 1115

Fracture, 374375
history of, 995
models of, 995
phenomenology of, 994
as randomness source, 968
sound of, 1079

Fraenkel, Abraham A. (Germany/Israel, 1891–1965)
and set theory, 1154

FrameMaker
and layout of this book, 852

Frameworks
for mathematical proofs, 1177

Fraud detection
in random data, 1184

Freckles
coloration of, 1012

Fredkin, Edward (USA, 1934– )
and CA self-reproduction, 1179
and cellular automata, 877, 879
and discreteness of space, 1027
in Preface, xiii
and reversible CAs, 1018
and universe as CA, 1026

Free group
network for, 196

Free semigroup, 938

Free will, 750753
and chaos theory, 971
and computational irreducibility, 1132
and defining randomness, 1067
implications for, 1197
and randomness, 967

Freeways
and growth of cities, 1014

Freezing
of water, 370

Frege, F. L. Gottlob (Germany, 1848–1925)
and axioms for logic, 1151
and character of math, 1176
and foundations of math, 1149
and logic as basis for science, 860
and predicate logic, 1152

Frenet frames
and growth of shells, 1009

Frequencies
of blocks, 555, 1068, 1084
of leading digits, 914
in statistics, 589
of words, 1014

Frequency modulation (FM), 1188

Frequency spectra, 1080
and acoustic diffusers, 1183
in auditory perception, 585
in data compression, 1072
in human hearing, 1079
in musical notes, 917
in natural radio emissions, 1187
of noise, 968
of random walks, 977
and SETI, 835

Frequency test, 1084

FresnelC (Fresnel integral)
in half-plane diffraction, 1133

FresnelS (Fresnel integral)
and Cornu spiral, 1009

Freudenthal, Hans (Netherlands, 1905–1990)
and Lincos language, 1189

Friction
origins of, 996
randomness in, 970, 1193
and self-organization, 947

Friedberg, Richard M. (USA, 1935– )
and intermediate degrees, 1130

Friedman, William F. (USA, 1891–1969)
and cryptanalysis, 1086

Frogs
pigmentation patterns of, 426
and sound of Cantor set, 586

FromDigits
and additive CAs, 951
basic example of, 854
and carries, 1094
implementation of, 901
and recursive functions, 1121

Fronts (weather), 1178

Froths
evolution of, 1039

Fruit
packing of spherical, 986

Fruit flies
genetic programs of, 1002

Fuchsian groups
and hyperbolic space, 1050

Full shifts (in dynamical systems theory), 961

Fullerenes
and nanotechnology, 1193
as spherical networks, 1049
as synthesized molecules, 1194

FullForm
and axioms as strings, 1156
as parse tree, 1103

FullSimplify
and iterated maps, 1098
and proofs, 1158
and undecidability, 1138

Function
see Purpose

Function (pure function)
basic examples of, 853
and lambda calculus, 1121
and recursive functions, 907

Function evaluation
searches for optimal algorithms in, 1193

Functional analysis
and spectra, 1081

Functional equation
for additivity, 953
and function evaluation, 1134
for ModularLambda, 1093
and solving logistic map, 1098
for spectra, 1081

Functional integrals
see Path integrals

Functional iteration (iterated mapping), 149, 918

Functional languages
and combinators, 898

Functional operations
examples of in Mathematica, 853

FunctionExpand
and constructible reals, 1129

Functions
applied to digit sequences, 731
computed by TMs, 1144
history of concept of, 1109
mathematical, 145148
notion of in mathematics, 898
possible Boolean, 806
rapidly growing, 1162
standard in mathematics, 1091
structural representations of, 896
systems based on symbolic, 102
see also Mathematical functions

Fundamental domains
and repetition, 607

Fundamental groups (of manifolds), 1051

Fundamental theory
see Ultimate theory of physics

Fur
coloration of, 1012

Furrowing
in animal growth, 418

Fusion (S) combinator, 1121

Future, 1196
artifacts in, 829
data compression in, 836, 1069
extraterrestrials portrayed in, 1190
of science in this book, xi, 856
of technology, 1195
see also Predictability

Fuzzy arithmetic
and generalizing numbers, 1168

Fuzzy logic, 1083, 1175

Fuzzy searching, 623