# 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 Sierpinski 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, 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