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, 376–382
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, 376–382
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, 606–620
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
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, 772–821
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
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, 357–360
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, 374–375
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, 750–753
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, 145–148
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 searching, 623